Rogue Wave banner
Previous fileTop of DocumentContentsIndexNext file

10.2 The stack Data Abstraction

As a data abstraction, a stack is traditionally defined as any object that implements the operations defined in Table 16:

Table 16 -- Stack operations

FunctionImplemented operation
empty()
Returns true if the collection is empty
size()
Returns number of elements in collection
top()
Returns (but does not remove) the topmost element in the stack
push(newElement)
Pushes a new element onto the stack
pop()
Removes (but does not return) the topmost element from the stack

Note that accessing the front element and removing the front element are separate operations.

10.2.1 Include Files

Programs that use the stack data abstraction should include the file stack:

10.2.2 Declaration and Initialization of stack

A declaration for a stack must specify the underlying element type; it can also specify the container that will hold the elements. For a stack the default container is a deque, but a list or vector can also be used. The vector version is generally smaller, while the deque version may be slightly faster.

The following are sample declarations for a stack:

The last example creates a stack from a user-defined type named Customer.


NOTE: On most compilers it is important to leave a space between the two right angle brackets in the declaration of a stack, as shown in the example, or they are interpreted by the compiler as a right shift operator.

10.2.3 Example Program: An RPN Calculator

A classic application of a stack is in the implementation of this calculator.


NOTE: This program is in the file calc.cpp.

Input to the calculator consists of a text string that represents an expression written in reverse polish notation (RPN). Operands, called integer constants, are pushed on a stack of values. As operators are encountered, the appropriate number of operands are popped off the stack, the operation is performed, and the result is pushed back on the stack.

We can divide the development of our stack simulation into two parts, a calculator engine and a calculator program. A calculator engine is concerned with the actual work involved in the simulation, but does not perform any input or output operations. The name is intended to suggest an analogy to a car engine or a computer processor: the mechanism performs the actual work, but the user of the mechanism does not normally directly interact with it. Wrapped around this is the calculator program, which interacts with the user and passes appropriate instructions to the calculator engine.

We can use the following class definition for our calculator engine. Inside the class declaration we define an enumerated list of values to represent each of the possible operators that the calculator is prepared to accept. We have made two simplifying assumptions: all operands will be integer values, and only binary operators will be handled.

The member function doOperator() performs the actual work. It pops values from the stack2, performs the operation, then pushes the result back onto the stack:

The main program reads values in reverse polish notation, invoking the calculator engine to do the actual work:


Previous fileTop of DocumentContentsIndexNext file

OEM Edition, ©Copyright 1999, Rogue Wave Software, Inc.
Contact Rogue Wave about documentation or support issues.