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.

OperationHow?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.

OperationHow?Time
pushadd to end: arr[numElement++]$O(1)$
popdelete from end: numElement--$O(1)$
topreturn last: arr[numElement - 1]$O(1)$
emptycheck if numElement == 0$O(1)$