Stacks
In this chapter, we will take a look at the various implementation choices for stacks and queues and their tradeoffs.
A stack should support the following operations with the following resource usage. The space complexity is the additional space needed to implement the operation and does not consider the space used by the stack itself.
| Operation | Time | Space | Description |
|---|---|---|---|
| empty() | O(1) | O(1) | Create an empty stack. |
| push(s, e) | O(1) | O(1) | Push e into stack s. |
| pop(s) | O(1) | O(1) | Pop and return the top element from s. |
| is_empty(s) | O(1) | O(1) | Return whether or not s is an empty stack. |
For any stack s, we have pop(push(s, e)) == e. An alternate choice of stack operations is to implement a top(s) operation that returns the top element in the stack and a popv(s) operation that removes the top element in the stack without returning anything. This implementation is more fine-grained than the one above. i.e., you can implement the above pop(s) operation using top(s) and popv(s). Indeed, it is also possible to implement popv(s) and top(s) using push() and pop(). So both choices are equivalent.
Array-based stacks #
An array-based implementation uses an array to store the elements of the stack and an index to store the index of the top element of the stack.
Linked-list based stacks #
We use a singly-linked list where the elements of the stack are stored from top to bottom from the head of the list. This implementation can also support copy(s), which creates an independent copy of the stack s in O(1) time.