Home | | **Object Oriented Programming and Data Structures** | Stack ADT and its applications, Applications, Implementations

Stacks and queues are special kinds of ordered lists in which insertion and deletion are restricted only to some specific positions. They are very important tools for solving many useful computational problems.

**Stacks and queues**

Stacks
and queues are special kinds of ordered lists in which insertion and deletion
are restricted only to some specific positions. They are very important tools
for solving many useful computational problems. Since we have already
implemented ordered lists in the most general form, we can use these to
implement stacks and queues. However, because of the special insertion and
deletion patterns for stacks and queues, the ADT functions can be written to be
much more efficient than the general functions. Given the importance of these
new ADTs, it is worthwhile to devote time to these special implementations.

**1. The stack ADT and its
applications**

A stack
is an ordered list of elements in which elements are always inserted and
deleted at one end, say the beginning. In the terminology of stacks, this end
is called the **top** of the stack,
whereas the other end is called the **bottom**
of the stack. Also the insertion operation is called **push **and the deletion operation is called** pop**. The element at the top of a stack is frequently** **referred, so we highlight this special
form ofgetElement. A stack ADT can be specified by the following basic
operations. Once again we assume that we are maintaining a stack of characters.
In practice, the data type for each element of a stack can be of any data type.
Characters are chosen as place-holders for simplicity.

S =
init();

Initialize
S to an empty stack.

isEmpty(S);

Returns
"true" if and only if the stack S is empty, i.e., contains no
elements.

isFull(S);

//Returns
"true" if and only if the stack S has a bounded size and holds the
maximum number of elements it can. top(S);

Return
the element at the top of the stack S, or error if the stack is empty.

S =
push(S,ch);

Push the
character ch at the top of the stack S.

S =
pop(S);

Pop an
element from the top of the stack S. print(S);

Print the
elements of the stack S from top to bottom.

An
element popped out of the stack is always the last element to have been pushed
in. Therefore, a stack is often called a **Last-In-First-Out**
or a **LIFO** list.

**2. Applications of stacks**

Stacks
are used in a variety of applications. While some of these applications are
"natural", most

other are
essentially "pedantic". Here is a list anyway.

• For
processing nes ted structures, like checking for balanced parentheses,
evaluation of postfix expressions.

• For
handling function calls and, in particular, recursion.

• For
searching in special data structures (depth -first search in graphs and trees),
for example,

for
implementing backtracking.

**3. Implementations of the stack
ADT**

A stack
is specified by the ordered collection representing the content of the stack
together with the choice of the end of the collection to be treated as the top.
The top should be so chosen that pushing and popping can be made as far
efficient as possible.

**3.1. Using static arrays**

Static
arrays can realize stacks of a maximum possible size. If we assume that the
stack elements are stored in the array starting from the index 0, it is
convenient to take the top as the maximum index of an element in the array. Of
course, the other choice, i.e., the other boundary 0, can in principle be
treated as the top, but insertions and deletions at the location 0 call for too
many relocations of array elements. So our original choice is definitely
better.

**3.2. Using dynamic linked lists**

As we have
seen earlier, it is no big deal to create and maintain a dynamic list of
elements. The only consideration now is to decide whether the beginning or the
end of the list is to be treated as the top of the stack. Deletion becomes
costly, if we choose the end of the list as the top. Choosing the beginning as
the top makes the implementations of both push and pop easy. So we stick to
this convention. As usual, we maintain a dummy node at the top (beginning) for
simplifying certain operations.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Object Oriented Programming and Data Structure : Linear Data Structures : Stack ADT and its applications, Applications, Implementations |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.