Write an implementation of the ADT stack that uses a resizable array to represent the stack items. Anytime an attempt is made to push when the stack is full, double the size of the array. After the first doubling of the array, halve the size of the array when a pop results in fewer than half of the array's locations being occupied by current stack items. Maintain the stack's bottom entry at the beginning of the array.
Your stack implementation should be inherited from the stack interface given below. You should start with the ArrayStack class given below. To make the array resizable, you'll need to replace it with a dynamic array. Your submitted class should have the const DEFAULT_CAPACITY set to 1.
In order to do this you'll need to introduce a new data member named "capacity". You'll also need to delete the CapacityExceededError. Don't forget that you'll need to provide the big-3, since you'll be using dynamic memory.
Note that to avoid some complexities that arise with templated classes, we will not be dividing the class into two files as we have in the past. Both the class declaration and the class implementation have been combined into one file, ArrayStack.h
To resize the array, you'll need to start by allocating a new dynamic array that is the desired size, then copy all of the elements from the old dynamic array into the new dynamic array. I'll leave the rest of the details for you to figure out.
Here is an explanation of how DEFAULT_CAPACITY, capacity, and numItems will work together:
DEFAULT_CAPACITY is just the capacity that the stack will have initially.
The capacity data member will always keep track of the current capacity of the stack (in other words, the size of the array).
numItems is just the number of items that are actually in the stack.
So, for example, DEFAULT_CAPACITY could be equal to 1, capacity could be equal to 32 because we've been adding items to the stack, but numItems could be equal to, say, 19, because there are actually 19 items in the stack. If we keep adding items to the stack, numItems would eventually become 32, and then if we add one more item, numItems would become 33 while capacity would become 64.
Here are the files you will need to get started:
For documentation, you must provide function documentation for any new functions that you are writing (the big-3). No other documentation is required.