Stack
easyPush and pop both touch the top, so nothing underneath ever moves. The call stack is one of these, which is why any recursion can be rewritten with an explicit stack.
O(1) push/pop/peekSpace O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How stack works
A stack allows one thing: activity at the top. push writes there, pop removes from there, peek reads it. Because nothing underneath ever moves, all three are O(1) with no bookkeeping beyond a single index - data[top] = v and top = top + 1 is the entire push.
Restricting yourself to one end is what buys the guarantee. The discipline that falls out is last in, first out: pop always returns the most recently pushed survivor. Push 14, 27, 8 and the pops return 8, 27, 14 - insertion order exactly reversed.
The call stack is one of these, which is why any recursion can be rewritten with an explicit stack - converting recursive DFS to iterative just builds that stack by hand, and sidesteps stack overflow on deep inputs. Bracket matching is the other canonical use: push openers, pop and compare on closers.
Step by step
- Start with 14 then 27 pushed - 27 sits on top, and the top is the only reachable element.
- push(8): write 8 at the top slot and bump the index. 14 and 27 are untouched underneath.
- peek: return 8 but leave it in place - the stack still holds all three values.
- pop: 8 comes back out - the last value in is the first out. Size drops to two.
- pop twice more: 27, then 14. The drain replays the pushes in exact reverse order.
- One more pop hits the empty case - underflow, the branch every real implementation must guard explicitly.
Complexity
| Worst case time | O(1) push/pop/peek |
|---|---|
| Space | O(n) |
Reference implementation
Python
stack = []
stack.append(x) # push - amortised O(1)
top = stack[-1] # peek
x = stack.pop() # pop - O(1)
def is_balanced(s):
"""The canonical stack problem."""
pairs = {")": "(", "]": "[", "}": "{"}
st = []
for ch in s:
if ch in "([{":
st.append(ch)
elif ch in pairs:
if not st or st.pop() != pairs[ch]:
return False
return not stJavaScript
const stack = [];
stack.push(x); // O(1)
const top = stack.at(-1);
stack.pop(); // O(1)
// Array.shift() is O(n) - for a real queue use two stacks,
// a ring buffer, or a linked list.Worth noticing
LIFO falls out of using one end only
Push and pop both touch the top, so nothing below ever moves. That is why both are O(1) and why the structure needs no bookkeeping beyond a single index.
Any recursion can be rewritten with an explicit stack
The call stack is a stack. Converting a recursive DFS into an iterative one is just building that stack yourself - which is how you avoid a stack overflow on deep inputs.
Common pitfalls
- Popping an empty stack: underflow crashes or returns garbage, and the guard is one easily forgotten if statement.
- Confusing peek and pop mid-algorithm: one mutates and one does not, and swapping them silently corrupts the loop's state.
- In bracket matching, a closer arriving on an empty stack must fail immediately - popping without the emptiness check crashes instead.
- Bounded array stacks: pushing past capacity is overflow, and growing on demand makes that one push O(n) - which is why push is amortised O(1).
- Rewriting recursion iteratively but pushing children in the wrong order, so they come off the stack reversed relative to the recursive visit.
Where it is used
- The call stack itself - every function call pushes a frame, every return pops one.
- Undo in editors: each action pushes its inverse, and undo pops.
- Parsing - matching brackets, evaluating postfix expressions, shunting-yard operator handling.
- Iterative DFS, where an explicit stack replaces recursion on deep graphs.
Frequently asked questions
What is the time complexity of stack operations?
push, pop and peek are all O(1) worst case - each touches only the top slot and adjusts a single index, so nothing below ever moves. The stack occupies O(n) space for n elements. Growable array stacks make push amortised O(1) rather than strictly constant.
What does LIFO actually mean?
Last in, first out: pop always returns the most recently pushed element still present. It is not a rule layered on top - it falls out mechanically from allowing writes and removals at one end only, which is also exactly why both stay O(1).
How does a stack check balanced parentheses?
Scan the string, pushing every opener. On a closer, the stack must be non-empty and its top must be the matching opener - pop and compare. Any mismatch fails, a closer on an empty stack fails, and leftover openers at the end fail. One pass, O(n).
How do I convert recursion into an explicit stack?
Push what you would have passed as arguments, then loop while the stack is non-empty, popping and processing. The call stack is itself a stack, so any recursion can be rewritten this way - usually to avoid stack overflow on deep inputs.