Stack ADT and its applications, Applications, Implementations

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.