This section designs a class for modeling stacks.
Recall that a stack is a data structure that holds data in a last-in, first-out fashion, as shown in Figure 10.15.
Stacks have many applications. For example, the compiler uses a stack to process function invocations. When a function is invoked, its parameters and local variables are placed in an activation record that is pushed into a stack. When a function calls another function, the new function’s parameters and local variables are placed in a new activation record that is pushed into the stack. When a function finishes its work and returns to its caller, its activation record is released from the stack.
You can define a class to model stacks. For simplicity, assume the stack holds the int values. So, name the stack class StackOfIntegers. The UML diagram for the class is shown in Figure 10.16.
Suppose that the class is available, as defined in Listing 10.14. Let us write a test program in Listing 10.15 that uses the class to create a stack (line 7), stores ten integers 0, 1, 2, . . . , and 9 (lines 9-10), and displays them in reverse order (lines 12-13).
Listing 10.14 StackOfIntegers.h
1 #ifndef STACK_H
2 #define STACK_H
3
4 class StackOfIntegers
5 {
6 public:
7 StackOfIntegers();
8 bool isEmpty() const;
9 int peek() const;
10 void push(int value);
11 int pop();
12 int getSize() const;
13
14 private:
15 int elements[100];
16 int size;
17 };
18
19 #endif
LisTing 10.15 TestStackOfIntegers.cpp
1 #include <iostream>
2 #include “StackOfIntegers.h”
3 using namespace std;
4
5 int main()
6 {
7 StackOfIntegers stack;
8
9 for (int i = 0; i < 10; i++)
10 stack.push(i);
11
12 while (!stack.isEmpty())
13 cout << stack.pop() << ” “;
14
15 return 0;
16 }
How do you implement the StackOfIntegers class? The elements in the stack are stored in an array named elements. When you create a stack, the array is also created. The no-arg constructor initializes size to 0. The variable size counts the number of elements in the stack, and size – 1 is the index of the element at the top of the stack, as shown in Figure 10.17. For an empty stack, size is 0.
The StackOfIntegers class is implemented in Listing 10.16.
LisTing 10.16 StackOfIntegers.cpp
1 #include “StackOfIntegers.h”
2
3 StackOfIntegers::StackOfIntegers()
4 {
5 size = 0;
6 }
7
8 bool StackOfIntegers::isEmpty() const
9 {
10 return size == 0;
11 }
12
13 int StackOfIntegers::peek() const
14 {
15 return elements[size – 1];
16 }
17
18 void StackOfIntegers::push(int value)
19 {
20 elements[size++] = value;
21 }
22
23 int StackOfIntegers::pop()
24 {
25 return elements[–size];
26 }
27
28 int StackOfIntegers::getSize() const
29 {
30 return size;
31 }
Source: Liang Y. Daniel (2013), Introduction to programming with C++, Pearson; 3rd edition.