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

 

 processing an integer Stack
 The list is: 0

 The list is: 1 0

 The list is: 2 1 0

 2 popped from stack
 The list is: 1 0

 1 popped from stack
 The list is: 0

 0 popped from stack
 The list is empty

 processing a double Stack
 The list is: 1.1

 The list is: 2.2 1.1

 The list is: 3.3 2.2 1.1

 3.3 popped from stack
 The list is: 2.2 1.1

 2.2 popped from stack
 The list is: 1.1

 1.1 popped from stack
 The list is empty

 All nodes destroyed

 All nodes destroyed

 

---

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