Define a class called UndoStack using inheritance as described below.
Suppose that an existing class named ArrayStack has already been written.
An ArrayStack is an implementation of a stack of integers using an array as its internal representation.
It has the following implementation:
class ArrayStack {
public:
ArrayStack(); // construct empty stack
~ArrayStack(); // free memory
virtual bool isEmpty() const; // true if stack has no elements
virtual int peek() const; // return top element (error if empty)
virtual int pop(); // remove/return top element (error if empty)
virtual void push(int n); // add to top of stack, resizing if needed
private:
int* elements; // array of stack data (index 0 = bottom)
int size; // number of elements in stack
int capacity; // length of array
};
ostream& operator <<(const ArrayStack& stack); // prints a stack
Define a new class called UndoStack that extends ArrayStack through inheritance.
You should provide the same member functions as the superclass, as well as the following new public member function:
virtual void undo();
Your subclass represents a stack of integers that allows the user to "undo" the most recent single push or pop action that has been performed on the stack.
That is, if the most recent modification made to the stack was to push an element, you should remove that element from the stack; if the most recent modification made to the stack was to pop an element, you should put that element back onto the top of the stack.
(If the last action was an undo, and you undo again, you should undo-the-undo and redo the action that was undone.)
Your class should provide the same member functions as the superclass.
Your code must work with the existing ArrayStack class as shown, unmodified.
For example, if the following calls are made on an empty UndoStack, the resulting stack contents are shown at right:
UndoStack stack; // bottom --> top
stack.push(10); // {10}
stack.push(33); // {10, 33}
stack.push(24); // {10, 33, 24}
stack.undo(); // {10, 33} (undo last push)
stack.push(45); // {10, 33, 45}
stack.push(58); // {10, 33, 45, 58}
stack.pop(); // {10, 33, 45}
stack.undo(); // {10, 33, 45, 58} (undo last pop)
stack.push(99); // {10, 33, 45, 58, 99}
stack.push(77); // {10, 33, 45, 58, 99, 77}
stack.undo(); // {10, 33, 45, 58, 99} (undo last push)
stack.undo(); // {10, 33, 45, 58, 99, 77} (undo last undo)
stack.undo(); // {10, 33, 45, 58, 99} (undo last undo)
If the stack has just been created and the client tries to call undo, there has not ever been any element pushed or popped from the stack, so you should throw a string exception.
Recall that subclasses are not able to directly access private members of the superclass.
Your stack itself is a data structure, but you should not create any other auxiliary data structures (arrays, vectors, queues, maps, sets, etc.) in your code.
