This section implements a dynamic stack class.
There is a problem in the Stack class. The elements of the stack are stored in an array with a fixed size 100 (see line 16 in Listing 12.4). So, you cannot store more than 100 elements in a stack. You could change 100 to a larger number, but if the actual stack is small, this would waste space. One way to resolve this dilemma is to allocate more memory dynamically when needed.
The size property in the Stack<T> class represents the number of elements in the stack. Let us add a new property named capacity that represents the current size of the array for storing the elements. The no-arg constructor of Stack<T> creates an array with capacity 16. When you add a new element to the stack, you may need to increase the array size in order to store the new element if the current capacity is full.
How do you increase the array capacity? You cannot do so, once the array is declared. To circumvent this restriction, you may create a new, larger array, copy the contents of the old array to this new one, and delete the old array.
The improved Stack<T> class is shown in Listing 12.7.
Listing 12.7 ImprovedStack.h
1 #ifndef IMPROVEDSTACK_H
2 #define IMPROVEDSTACK_H
3
4 template<typename T>
5 class Stack
6 {
7 public:
8 Stack();
9 Stack(const Stack&);
10 ~Stack();
11 bool empty() const;
12 T peek() const;
13 void push(T value);
14 T pop();
15 int getSize() const;
16
17 private:
18 T* elements;
19 int size;
20 int capacity;
21 void ensureCapacity();
22 };
23
24 template<typename T>
25 Stack<T>::Stack(): size(0), capacity(16)
26 {
27 elements = new T[capacity];
28 }
29
30 template<typename T>
31 Stack<T>::Stack(const Stack& stack)
32 {
33 elements = new T[stack.capacity];
34 size = stack.size;
35 capacity = stack.capacity;
36 for (int i = 0; i < size; i++)
37 {
38 elements[i] = stack.elements[i];
39 }
40 }
41
42 template<typename T>
43 Stack<T>::~Stack()
44 {
45 delete [] elements;
46 }
47
48 template<typename T>
49 bool Stack<T>::empty() const
50 {
51 return size == 0;
52 }
53
54 template<typename T>
55 T Stack<T>::peek() const
56 {
57 return elements[size – 1];
58 }
59
60 template<typename T>
61 void Stack<T>::push(T value)
62 {
63 ensureCapacity();
64 elements[size++] = value;
65 }
66
67 template<typename T>
68 void Stack<T>::ensureCapacity()
69 {
70 if (size >= capacity)
71 {
72 T* old = elements;
73 capacity = 2 * size;
74 elements = new T[size * 2];
75
76 for (int i = 0; i < size; i++)
77 elements[i] = old[i];
78
79 delete [] old;
80 }
81 }
82
83 template<typename T>
84 T Stack<T>::pop()
85 {
86 return elements[–size];
87 }
88
89 template<typename T>
90 int Stack<T>::getSize() const
91 {
92 return size;
93 }
94
95 #endif
Since the internal array elements is dynamically created, a destructor must be provided to properly destroy the array to avoid memory leak (lines 42-46). Note that the array elements in Listing 12.4, GenericStack.h, are not allocated dynamically, so there is no need to provide a destructor in that case.
The push(T value) function (lines 60-65) adds a new element to the stack. This function first invokes ensureCapacity() (line 63), which ensures that there is a space in the array for the new element.
The ensureCapacity() function (lines 67-81) checks whether the array is full. If it is, create a new array that doubles the current array size, set the new array as the current array, copy the old array to the new array, and delete the old array (line 79).
Please note that the syntax to destroy a dynamically created array is
delete [] elements; // Line 45
delete [] old; // Line 79
What happens if you mistakenly write the following?
delete elements; // Line 45
delete old; // Line 79
The program will compile and run fine for a stack of primitive-type values, but it is not correct for a stack of objects. The statement delete [] elements first calls the destructor on each object in the elements array and then destroys the array, whereas the statement delete elements calls the destructor only on the first object in the array.
Source: Liang Y. Daniel (2013), Introduction to programming with C++, Pearson; 3rd edition.