Implement Stack using Arrays
Implement Stack using Arrays: build a stack — push, pop, top, size — on a fixed array.
- 1 <= capacity <= 10⁵
- Operations: push, pop, top, size
- Pop or top on an empty stack must be handled explicitly
Intuition
To implement stack using arrays you need LIFO behaviour: the last element pushed is the first one popped. What makes this the easiest of the container-implementation problems is that the newest element is always the one at the end, and the end of an array is the cheapest place to work.
So the entire structure is an array plus a single integer. Call it top, holding the index of the last stored element. Push writes at top + 1 and increments; pop reads at top and decrements. Nothing ever shifts, which is precisely why every operation is O(1) — compare this with a queue on an array, where a naive dequeue moves every remaining element.
Using −1 for the empty state is the convention worth adopting:
- top == -1 means empty, so the first push lands at index 0 with no special case.
The part that actually needs care is the boundaries. Popping or peeking an empty stack is underflow, and pushing onto a full fixed array is overflow. Both must be checked before touching the array, because both would otherwise read or write outside the valid range — the kind of bug that corrupts data silently rather than failing loudly.
The foundational exercise: a stack is an array plus one index. Everything interesting is in the boundary conditions — top == -1 means empty, top == capacity - 1 means full. Getting those two right is the whole problem, and they're the same two checks every fixed-capacity structure needs.
Approach
Before reading on: price up what enumerating every case costs here, then ask what unresolved thing you are holding, and what event finally resolves it. Aim for O(1) per op time and O(cap) space.
Track a single index
Store a fixed-capacity array and an integer top, initialised to −1 for empty. That one variable is the complete state of the stack — no head pointer, no count, no wrapping arithmetic.
Push at the next slot
Increment top, then write the value at a[top]. The new element is the newest and belongs at the end, which is exactly where the array is cheapest to modify. One increment and one write, always O(1).
Pop from the current slot
Read a[top], then decrement top. There is no need to erase the old value — it sits above the new top and is unreachable through the stack interface, and the next push will overwrite it.
Guard underflow and overflow
Return an error or sentinel when popping or peeking with top == -1, and when pushing with top == capacity - 1. Both checks must come before the array access, since either would otherwise index outside the array and corrupt memory in a language that permits it.
Grow the array for a dynamic stack
If the capacity should not be fixed, allocate a larger array on overflow — typically double the size — and copy the elements across. Copying is O(n) but happens rarely enough that pushes stay amortised O(1). This is exactly how Python's list.append and C++'s vector::push_back behave.
Solution & live demo
Common pitfalls
Incrementing the index after writing
self.a[self.top] = x self.top += 1
self.top += 1 self.a[self.top] = x
With top starting at −1 as the empty marker, writing first targets index −1, which in Python silently overwrites the last slot of the array. Advance to the new position, then write to it.
Checking overflow against the wrong bound
if self.top == len(self.a): raise OverflowError
if self.top == len(self.a) - 1: raise OverflowError
top is the index of the last stored item, so a full array has top == capacity - 1. Comparing against capacity lets one extra push run off the end.
Returning a value after decrementing
self.top -= 1 return self.a[self.top]
v = self.a[self.top] self.top -= 1 return v
Decrementing first returns the element below the top — the one that should survive the pop. Read the value while the index still points at it.
Edge cases
Explicit underflow check; raise or return sentinel.
top bounces at the boundary; indices never leak past it.