Software Design Using C++StacksWhat is a Stack?Intuitively, a stack is like a pile of plates where we can only remove a plate from the top and can only add a new plate on the top. In computer science we commonly place numbers on a stack, or perhaps place records on the stack. The following snippet of code from lstclass.h shows the typical stack operations that we plan to use (other than the automatically available constructor and destructor).
The A stack is called a "last in, first out" (LIFO) data structure since the last item pushed onto a stack will be the first one popped off. It can also be called a "first in, last out" (FILO) data structure since the first item pushed onto it will be the last one popped off. Because of these features, a stack is the ideal data structure to use in reversing a sequence of items. A section of code for doing this follows:
Note how simple this algorithm is! One pushes the numbers one by one onto the stack. Then one pops numbers off, printing each number popped, until the stack is empty. A LinkedList ImplementationSince our picture of a stack essentially shows a sequence of data items, it should be easy to hold the data for a stack in a linked list. After all, we would only need to directly access the data at one end of the list, the front, which would represent the top of the stack. The group of files given below contains a linkedlist implementation of a class called LstStackClass as well as a test program that reverses a sequence of numbers using the algorithm just examined. The first file sets up the type name ItemType for whatever kind of data we want to place
on our stacks. The next four files are almost the same ones that we used in the
section on lists to create a class called ListClass . The only significant
change is to the GetNode function in list.cpp. This function has been changed to use
new inside of a try...catch when it tries to allocate a new node, whereas we formerly
used the nothrow option to return a NULL pointer if the new operation failed to allocate
the desired memory space. The use of the try...catch is a more modern way to handle
the failure to allocate memory. The last file contains the test program itself.
LstStackClass , which is repeated here for convenience:
There is only one data field, and it is private, as usual. This field contains
a The lststack.cpp file contains the code for our stack operations. This is really easy, because all of the work is done by using the appropriate list functions, which have already been implemented. Thus, the function to see if a stack is empty just checks if the embedded list is empty. Similarly, to push a data item onto the stack, we just insert it at the front of the list as follows:
Finally, the pop operation is carried out by removing the front data item
from the embedded list. Look though all of the source code files
given above for the complete details on this example. Note that our
Alternative Stack ImplememtationThis implementation also uses an embedded linked list, but derives the LstStackClass from the following abstract base class. This abstract base class shows the typical stack operations that we plan to use (other than the automatically available constructor and destructor). An abstract base class cannot be used for the creation of objects. Rather, it is just an outline of sorts, from which we derive by inheritance a class that actually implements the operations and with which we can create objects.
The term
The
The group of files given below contains a linkedlist implementation of
a class called LstStackClass as well as a test program that reverses a sequence
of numbers, much like we did with our previous stack implementation. The first file sets up the
type name LstStackClass , which is repeated here for convenience:
Note that the new class is derived by public inheritance from
There is only one data field, and it is private, as usual. This field contains
a The lststack.cpp file contains the code for our stack operations. This works the same way as in our previous implementation of a stack. If you look through the files that comprise this implementation of a stack, the only real difference is that LstStackClass is derived by public inheritance from an abstract base class. Everything else is the same. Evaluating a Postfix ExpressionYou may be asking what a stack is good for, other than reversing a sequence of data items. One common application is to convert an infix expression to postfix. Another is to find the value of a postfix expression. We will not look at the conversion algorithm here, but we will examine the algorithm to evaluate a postfix expression.
First, let's explain the terminology. An infix expression is the type
that we are used to in ordinary algebra, such as
A postfix expression, in contrast, places each operator after the two values
to which it applies. (Post means "after", right?) The above
expression would be Here are a few more examples in the following table. The infix form is shown on the left, and the postfix form is given on the right.
Note that postfix expressions do not use parentheses for grouping; parentheses are not needed! Infix sometimes requires parentheses to force a certain order of evaluation. For example, in the second example above, parentheses were needed to indicate that the addition should be done before the multiplication. Without the parentheses you get the third example, where the multiplication is done before the addition (using the precedence rules from ordinary arithmetic, or from C++, for that matter). Arithmetic expressions like the above can of course be much longer.
We could also allow other operators, such as ^ for exponentiation, or
perhaps a unary minus. A sample infix expression that uses exponentiation
is
The algorithm to evaluate a postfix expression works like this: Start with
an empty stack of floats. Scan the postfix expression from left to right.
Whenever you reach a number, push it onto the stack. Whenever you reach
an operator (call it Op perhaps), pop two items,
say
Let's look at the postfix expression evaluation algorithm by way of example.
Consider the postfix expression
Let's evaluate another postfix expression, say When one reaches an operator in this algorithm, it is important to get the order right for the values to which it applies. The second item popped off should go in front of the operator, while the first one popped off goes after the operator. You can easily see that with subtraction and division the order does matter. A good exercise for the reader is to develop a program that repeatedly evaluates postfix expressions. In fact, with enough work, it can be turned into a reasonable postfix calculator. An Array ImplementationA stack can also be implemented using an arraybased approach. Look at the example contained in the following list of files. As in our second listbased implementation, a new class is derived from the abstract base class named StackBaseClass . However, this time, instead of using
an embedded list object, the data fields consist on an integer Top
and an array Info .
Top holds the index of the top of stack
item, which is stored in the Info array. To push a new item
onto a stack, Top is simply incremented and the new item placed
into the array at that index. To pop an item from the stack, the item at
index Top is sent back and Top itself is decremented.
Since a value of zero in Top indicates a stack with one item (at
index 0), a value of 1 in Top indicates an empty stack.
The following drawing shows you a picture of an arraybased stack with 3
items in it. Note that a Related Items
