Stacks and queues
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
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 to an empty stack.
"true" if and only if the stack S is empty, i.e., contains no
"true" if and only if the stack S has a bounded size and holds the
maximum number of elements it can. top(S);
the element at the top of the stack S, or error if the stack is empty.
character ch at the top of the stack S.
element from the top of the stack S. print(S);
elements of the stack S from top to bottom.
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
are used in a variety of applications. While some of these applications are
essentially "pedantic". Here is a list anyway.
processing nes ted structures, like checking for balanced parentheses,
evaluation of postfix expressions.
handling function calls and, in particular, recursion.
searching in special data structures (depth -first search in graphs and trees),
3. Implementations of the 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
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
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.