Requirement
Implement a templated Stack class. It must implement the following interface (abstract class), which you should inherit from. In other words, create a file IStack.h which contains this definition, and then your own class (which may be called something like ListStack or ArrayStack or other, depending on how you impement it) should inherit publicly from IStack.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22template <class T>
class IStack
{
public:
/* returns whether the stack contains any elements */
virtual bool isEmpty() const = 0;
/* adds a value to the top of the stack */
virtual void push(const T& val) = 0;
/* deletes the top value from the stack.
Throws EmptyStackException if stack was empty.
However, you should avoid having this exception thrown,
by checking whether the stack is empty before calling it. */
virtual void pop() = 0;
/* returns the top value on the stack.
Throws EmptyStackException if stack was empty.
However, you should avoid having this exception thrown,
by checking whether the stack is empty before calling it. */
virtual const T& top() const = 0;
};
Your implementation can reuse some of your earlier linked list code, or you can build it on top of an array (which you dynamically allocate) - your choice. You must ensure that all functions run in time O(1) (amortized time O(1) if you use an array implementation), and should give an explanation with your code for why your code runs in O(1) time.
Your solution to this problem absolutely cannot use STL container classes (so no stack or vector or deque or list or such provided by STL).