19.4 Stacks
You learned the concept of a stack in Section 6.11, Section 15.7.1 (stack adapter) and Section 18.2. Recall that a node can be added to a stack and removed from a stack only at its top, so 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 nullptr 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’s passed to the calling function and returns true if the pop operation was successful (false otherwise).
Applications of Stacks
Stacks have many interesting applications:
In Section 6.11, you learned that 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.
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.
19.4.1 Taking Advantage of the Relationship Between Stack and List
We’ll take advantage of the close relationship between lists and stacks to implement a stack class primarily by reusing our List class template. First, we’ll implement the Stack class template via private inheritance from our List class template. Then we’ll implement an identically performing Stack class template through composition by including a List object as a private member of a Stack class template.
19.4.2 Implementing a Class Template Stack Class Based By Inheriting from List
The program of Figs. 19.13–19.14 creates a Stack class template (Fig. 19.13) primarily through private inheritance (line 9) of the List class template of Fig. 19.5. We want the Stack to have member functions push (Fig. 19.13, lines 12–14), pop (lines 17–19), isStackEmpty (lines 22–24) and printStack (lines 27–29). 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 class—push calls insertAtFront (line 13), pop calls removeFromFront (line 18), isStackEmpty calls isEmpty (line 23) and printStack calls print (line 28)—this is referred to as delegation.
Fig. 19.13 Stack class-template definition.
Alternate View
1 // Fig. 19.13: Stack.h
2 // Stack class-template definition.
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 public:
11 // push calls the List function insertAtFront
12 void push(const STACKTYPE& data) {
13 insertAtFront(data);
14 }
15
16 // pop calls the List function removeFromFront
17 bool pop(STACKTYPE& data) {
18 return removeFromFront(data);
19 }
20
21 // isStackEmpty calls the List function isEmpty
22 bool isStackEmpty() const {
23 return this->isEmpty();
24 }
25
26 // printStack calls the List function print
27 void printStack() const {
28 this->print();
29 }
30 };
31
32 #endif
19.4.3 Dependent Names in Class Templates
The explicit use of this on lines 23 and 28 is required so the compiler can properly resolve identifiers in template definitions. A dependent name is an identifier that depends on a template parameter. For example, the call to removeFromFront (line 18) depends on the argument data which has a type that’s dependent on the template parameter STACKTYPE. Resolution of dependent names occurs when the template is instantiated.
In contrast, the identifier for a function that takes no arguments like isEmpty or print in the List superclass is a non-dependent name. Such identifiers are normally resolved at the point where the template is defined. If the template has not yet been instantiated, then the code for the function with the non-dependent name does not yet exist and some compilers will generate compilation errors. Adding the explicit use of this-> in lines 23 and 28 makes the calls to the base class’s member functions dependent on the template parameter and ensures that the code will compile properly.
19.4.4 Testing the Stack Class Template
The stack class template is used in main (Fig. 19.14) to instantiate integer stack intStack of type Stack<int> (line 8). Integers 0 through 2 are pushed onto intStack (lines 13–16), then popped off intStack (lines 21–25). The program uses the Stack class template to create doubleStack of type Stack<double> (line 27). Values 1.1, 2.2 and 3.3 are pushed onto doubleStack (lines 33–37), then popped off doubleStack (lines 42–46).
Fig. 19.14 A simple stack program.
Alternate View
1 // Fig. 19.14: fig19_14.cpp
2 // A simple stack program.
3 #include <iostream>
4 #include "Stack.h" // Stack class definition
5 using namespace std;
6
7 int main() {
8 Stack<int> intStack; // create Stack of ints
9
10 cout << "processing an integer Stack" << endl;
11
12 // push integers onto intStack
13 for (int i{0}; i < 3; ++i) {
14 intStack.push(i);
15 intStack.printStack();
16 }
17
18 int popInteger; // store int popped from stack
19
20 // pop integers from intStack
21 while (!intStack.isStackEmpty() ) {
22 intStack.pop(popInteger);
23 cout << popInteger << " popped from stack" << endl;
24 intStack.printStack();
25 }
26
27 Stack<double> doubleStack; // create Stack of doubles
28 double value{1.1};
29
30 cout << "processing a double Stack" << endl;
31
32 // push floating-point values onto doubleStack
33 for (int j{0}; j < 3; ++j) {
34 doubleStack.push(value);
35 doubleStack.printStack();
36 value += 1.1;
37 }
38
39 double popDouble; // store double popped from stack
40
41 // pop floating-point values from doubleStack
42 while (!doubleStack.isStackEmpty() ) {
43 doubleStack.pop(popDouble);
44 cout << popDouble << " popped from stack" << endl;
45 doubleStack.printStack();
46 }
47 }
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
19.4.5 Implementing a Class Template Stack Class With Composition of a List Object
Another way to implement a Stack class template is by reusing the List class template through composition. Figure 19.15 is a new implementation of the Stack class template that contains a List<STACKTYPE> object called stackList (line 33). This version of the Stack class template uses class List from Fig. 19.5. To test this class, use the driver program in Fig. 19.14, but include the new header—Stackcomposition.h—in line 4. The output of the program is identical for both versions of class Stack.
Fig. 19.15 Stack class template with a composed List object.
Alternate View
1 // Fig. 19.15: Stackcomposition.h
2 // Stack class template with a 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 public:
11 // no constructor; List constructor does initialization
12
13 // push calls stackList object"s insertAtFront member function
14 void push(const STACKTYPE& data) {
15 stackList.insertAtFront(data);
16 }
17
18 // pop calls stackList object"s removeFromFront member function
19 bool pop(STACKTYPE& data) {
20 return stackList.removeFromFront(data);
21 }
22
23 // isStackEmpty calls stackList object"s isEmpty member function
24 bool isStackEmpty() const {
25 return stackList.isEmpty();
26 }
27
28 // printStack calls stackList object"s print member function
29 void printStack() const {
30 stackList.print();
31 }
32 private:
33 List<STACKTYPE> stackList; // composed List object
34 };
35
36 #endif