Stacks
Last in, first out. Push and pop at one end in constant time — the structure behind calls, undo, and depth-first search.
Level: beginner
What is it?
A stack allows two main operations: push adds an element to the top and pop removes the top element. The last item in is the first out (LIFO). It can be built on an array or a linked list, and both make push, pop, and peek O(1).
Why does it matter?
Whenever something must be undone in reverse order, a stack is the natural shape: function calls, undo history, backtracking, expression parsing, and depth-first search all reduce to one. The program's call stack is a literal instance.
Mental model
A stack of plates in a cafeteria. You put a clean one on top and take one from the top. You never dig to the middle, and the plate placed last is the first you use.
How it works
- Operations: push, pop, peek, is_empty — each O(1).
- The call stack is a stack of frames; recursion is an implicit use of it.
- Matching brackets, evaluating postfix expressions, and parsing use an explicit stack.
- Depth-first search replaces recursion with an explicit stack to avoid recursion limits.
- A monotonic stack keeps elements sorted as you push, solving 'next greater element' problems in O(n).
Steps
- Push onto the top
- Peek at the top
- Pop from the top
- Repeat until empty
- Underflow means an unmatched pop
Code example: Balanced brackets with a stack
def balanced(s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in "([{":
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
print(balanced("{[()]}"), balanced("([)]")) # True FalseComplexity and trade-offs
Time: Push, pop, peek O(1)
Space: O(n)
Trade-offs
- Simple and fast
- Access is limited to the top; no random access or search
Real-world usage
- Call stacks and undo/redo
- Expression evaluation and parsers
- Depth-first search and backtracking
Common mistakes
- Popping from an empty stack without checking.
- Forgetting to check that the stack is empty at the end (unmatched openers).
- Using recursion where a stack would avoid the depth limit.
Interview questions
Why are stacks used for expression evaluation?
Operators and operands must be resolved in reverse order of appearance, with inner expressions finishing first. A stack holds pending operands and operators until their partners arrive.
How do you implement a stack with an array?
Keep an array and a top index or length. Push writes at the end (growing if needed) and pop removes from the end, both O(1) amortized.
How is recursion related to a stack?
Each call pushes a frame onto the call stack, and each return pops it. Any recursion can be rewritten as a loop with an explicit stack.