Using an Array to Implement a Stack

We will implement the Stack interface using an array (ArrayStack) and a linked list (LinkedStack). We will start with the array-based implementation, and before writing any code, we will design the implementation by writing down the algorithm for each method (at a high level) and analyzing its complexity.

Which End of the Array Holds the Top

The first design choice we need to make is which end of the array will represent the top of the stack. We have two options:

The top of the stack is at the end of the array (the last index).
The top of the stack is at the beginning of the array (the first index).

Take the second option first. If the top is at index 0, then a push has to make room at index 0, which means shifting every item one slot to the right. A pop has to close the gap at index 0, which means shifting every item one slot to the left. Both are $O (n)$ .

Now the first option. If the top is at the last used index, a push writes into the slot after it and a pop removes the last slot. In neither case does any other item move, so both are $O (1)$ .

So we choose the first option: the top of the stack will be at the end of the array.

Operations and Complexity

Now we can say what an ArrayStack holds. It holds a backing array and a count of how many items are on the stack, the same two fields as our ArrayList.

isEmpty(): The stack is empty exactly when the count is zero, so we only have to check the count. This is $O (1)$ .

top(): This operation returns the item at the last used index (the top of the stack). Since we can access any index in an array in $O (1)$ time, this operation also has a time complexity of $O (1)$ .

pop(): This operation removes the item at the last used index (the top of the stack). Removing it means decrementing the count, which takes the last slot out of the stack, and then setting that slot to null so that Java can reclaim the object we no longer need. Both are single steps that do not depend on the number of items, so pop is $O (1)$ .

push(T item): This operation adds an item to the slot after the last used index. When the array is full, push grows it first, exactly as add does in our ArrayList, so push is amortized $O (1)$ for the same reason.

So every operation is $O (1)$ , and push is amortized $O (1)$ .