www.gibmonks.com

Main Page




Previous Page
Next Page

[Page 1016 (continued)]

21.5. 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.


[Page 1017]

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.


[Page 1018]
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 <iostream>
 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



[Page 1020]

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


Previous Page
Next Page