Array Implementation of Stack
We want to implement the Stack interface using an array as an internal data storage.
Exercise Think about how to implement a stack using an array such that the core operations are constant time. Assume the array is sufficiently large.
| Operation | How? | Time |
|---|---|---|
push | $O(1)$ | |
pop | $O(1)$ | |
top | $O(1)$ | |
empty | $O(1)$ |
Solution
Consider the "top" of the stack as the "end" of the array. Thus, elements can be added at the end of the collection in constant time.
Assume there is a variable numElement. It is initialized to $0$ when the stack is constructed (and it is therefore empty). The numElement is incremented/decremented as data is pushed to/popped from the stack. Therefore, the numElement continuously points to the next empty slot in the array. Thus, we can use it to index into the collection.
| Operation | How? | Time |
|---|---|---|
push | add to end: arr[numElement++] | $O(1)$ |
pop | delete from end: numElement-- | $O(1)$ |
top | return last: arr[numElement - 1] | $O(1)$ |
empty | check if numElement == 0 | $O(1)$ |