Stacks
In Chapter 14, Templates, we explained the notion of a stack class template with an underlying array implementation. In this section, we use an underlying pointer-based linked-list implementation. We also discuss stacks in Chapter 23, Standard Template Library (STL).
A stack data structure allows nodes to be added to the stack and removed from the stack only at the top. For this reason, a stack is referred to as a last-in, first-out (LIFO) data structure. One way to implement a stack is as a constrained version of a linked list. In such an implementation, the link member in the last node of the stack is set to null (zero) to indicate the bottom of the stack.
The primary member functions used to manipulate a stack are push and pop. Function push inserts a new node at the top of the stack. Function pop removes a node from the top of the stack, stores the popped value in a reference variable that is passed to the calling function and returns true if the pop operation was successful (false otherwise).
Stacks have many interesting applications. For example, when a function call is made, the called function must know how to return to its caller, so the return address is pushed onto a stack. If a series of function calls occurs, the successive return values are pushed onto the stack in last-in, first-out order, so that each function can return to its caller. Stacks support recursive function calls in the same manner as conventional nonrecursive calls. Section 6.11 discusses the function call stack in detail.
Stacks provide the memory for, and store the values of, automatic variables on each invocation of a function. When the function returns to its caller or throws an exception, the destructor (if any) for each local object is called, the space for that function's automatic variables is popped off the stack and those variables are no longer known to the program.
Stacks are used by compilers in the process of evaluating expressions and generating machine-language code. The exercises explore several applications of stacks, including using them to develop your own complete working compiler.
We will take advantage of the close relationship between lists and stacks to implement a stack class primarily by reusing a list class. First, we implement the stack class through private inheritance of the list class. Then we implement an identically performing stack class through composition by including a list object as a private member of a stack class. Of course, all of the data structures in this chapter, including these two stack classes, are implemented as templates to encourage further reusability.
The program of Figs. 21.1321.14 creates a Stack class template (Fig. 21.13) primarily through private inheritance (line 9) of the List class template of Fig. 21.4. We want the Stack to have member functions push (lines 1316), pop (lines 1922), isStackEmpty (lines 2528) and printStack (lines 3134). Note that these are essentially the insertAtFront, removeFromFront, isEmpty and print functions of the List class template. Of course, the List class template contains other member functions (i.e., insertAtBack and removeFromBack) that we would not want to make accessible through the public interface to the Stack class. So when we indicate that the Stack class template is to inherit from the List class template, we specify private inheritance. This makes all the List class template's member functions private in the Stack class template. When we implement the Stack's member functions, we then have each of these call the appropriate member function of the List classpush calls insertAtFront (line 15), pop calls removeFromFront (line 21), isStackEmpty calls isEmpty (line 27) and printStack calls print (line 33)this is referred to as delegation.
Figure 21.13. Stack class-template definition.
(This item is displayed on pages 1017 - 1018 in the print version)
|
1 // Fig. 21.13: Stack.h 2 // Template Stack class definition derived from class List. 3 #ifndef STACK_H 4 #define STACK_H 5 6 #include "List.h" // List class definition 7 8 template< typename STACKTYPE > 9 class Stack : private List< STACKTYPE > 10 { 11 public: 12 // push calls the List function insertAtFront 13 void push( const STACKTYPE &data ) 14 { 15 insertAtFront( data ); 16 } // end function push 17 18 // pop calls the List function removeFromFront 19 bool pop( STACKTYPE &data ) 20 { 21 return removeFromFront( data ); 22 } // end function pop 23 24 // isStackEmpty calls the List function isEmpty 25 bool isStackEmpty() const 26 { 27 return isEmpty(); 28 } // end function isStackEmpty 29 30 // printStack calls the List function print 31 void printStack() const 32 { 33 print(); 34 } // end function print 35 }; // end class Stack 36 37 #endif |
The stack class template is used in main (Fig. 21.14) to instantiate integer stack intStack of type Stack< int > (line 11). Integers 0 through 2 are pushed onto intStack (lines 1620), then popped off intStack (lines 2530). The program uses the Stack class template to create doubleStack of type Stack< double > (line 32). Values 1.1, 2.2 and 3.3 are pushed onto doubleStack (lines 3843), then popped off doubleStack (lines 4853).
Figure 21.14. A simple stack program.
(This item is displayed on pages 1018 - 1020 in the print version)
|
1 // Fig. 21.14: Fig21_14.cpp 2 // Template Stack class test program. 3 #include 4 using std::cout; 5 using std::endl; 6 7 #include "Stack.h" // Stack class definition 8 9 int main() 10 { 11 Stack< int > intStack; // create Stack of ints 12 13 cout << "processing an integer Stack" << endl; 14 15 // push integers onto intStack 16 for ( int i = 0; i < 3; i++ ) 17 { 18 intStack.push( i ); 19 intStack.printStack(); 20 } // end for 21 22 int popInteger; // store int popped from stack 23 24 // pop integers from intStack 25 while ( !intStack.isStackEmpty() ) 26 { 27 intStack.pop( popInteger ); 28 cout << popInteger << " popped from stack" << endl; 29 intStack.printStack(); 30 } // end while 31 32 Stack< double > doubleStack; // create Stack of doubles 33 double value = 1.1; 34 35 cout << "processing a double Stack" << endl; 36 37 // push floating-point values onto doubleStack 38 for ( int j = 0; j < 3; j++ ) 39 { 40 doubleStack.push( value ); 41 doubleStack.printStack(); 42 value += 1.1; 43 } // end for 44 45 double popDouble; // store double popped from stack 46 47 // pop floating-point values from doubleStack 48 while ( !doubleStack.isStackEmpty() ) 49 { 50 doubleStack.pop( popDouble ); 51 cout << popDouble << " popped from stack" << endl; 52 doubleStack.printStack(); 53 } // end while 54 55 return 0; 56 } // end main
|
Another way to implement a Stack class template is by reusing the List class template through composition. Figure 21.15 is a new implementation of the Stack class template that contains a List< STACKTYPE > object called stackList (line 38). This version of the Stack class template uses class List from Fig. 21.4. To test this class, use the driver program in Fig. 21.14, but include the new header fileStackcomposition.h in line 6 of that file. The output of the program is identical for both versions of class Stack.
Figure 21.15. Stack class template with a composed List object.
(This item is displayed on pages 1020 - 1021 in the print version)
|
1 // Fig. 21.15: Stackcomposition.h 2 // Template Stack class definition with composed List object. 3 #ifndef STACKCOMPOSITION_H 4 #define STACKCOMPOSITION_H 5 6 #include "List.h" // List class definition 7 8 template< typename STACKTYPE > 9 class Stack 10 { 11 public: 12 // no constructor; List constructor does initialization 13 14 // push calls stackList object's insertAtFront member function 15 void push( const STACKTYPE &data ) 16 { 17 stackList.insertAtFront( data ); 18 } // end function push 19 20 // pop calls stackList object's removeFromFront member function 21 bool pop( STACKTYPE &data ) 22 { 23 return stackList.removeFromFront( data ); 24 } // end function pop 25 26 // isStackEmpty calls stackList object's isEmpty member function 27 bool isStackEmpty() const 28 { 29 return stackList.isEmpty(); 30 } // end function isStackEmpty 31 32 // printStack calls stackList object's print member function 33 void printStack() const 34 { 35 stackList.print(); 36 } // end function printStack 37 private: 38 List< STACKTYPE > stackList; // composed List object 39 }; // end class Stack 40 41 #endif |