What you'll learn
A stack is a list with a rule: you can only add or remove at one end, the top. That's LIFO — last in, first out. It sounds restrictive, but it's exactly the behavior behind undo, the call stack, and parsing.
By the end you'll be able to:
- Use the three stack operations:
push,pop,peek - Implement a stack on an array or a linked list — all
O(1) - Solve a real problem (bracket matching) with a stack
LIFO: push, pop, peek
Think of a stack of plates: you add to the top (push), take from the top (pop), or glance at the top (peek). Every operation touches only the top, so every operation is O(1). Step through it:
Key idea
Application: bracket matching
Stacks are the natural tool whenever the most recent thing must be resolved first. Checking whether brackets are balanced is the classic example: push every opener, and on each closer make sure it matches the opener on top.
def is_balanced(s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in "([{":
stack.append(ch)
elif ch in ")]}":
if not stack or stack.pop() != pairs[ch]:
return False
return len(stack) == 0In code
You rarely build a stack from scratch — a dynamic array (or the language's stack/deque type) already gives youO(1) push and pop at the end:
stack = []
stack.append("A") # push
stack.append("B")
top = stack[-1] # peek -> "B"
stack.pop() # pop -> removes "B"
print(top, len(stack))Complexity & uses
| Operation | Time | Common uses |
|---|---|---|
push | O(1) | Undo/redo history |
pop | O(1) | The function call stack |
peek | O(1) | Expression evaluation & parsing |
search | O(n) | Backtracking (DFS, mazes) |
Recap & quick check
Key takeaways
- A stack is LIFO: add and remove only at the top.
- push, pop, and peek are all O(1).
- The call stack, undo history, and backtracking all rely on stack behavior.
- Bracket matching: push openers, and each closer must match the top.
- A dynamic array or the built-in stack/deque type implements it directly.
Quick check
1. What does LIFO stand for?
2. Which operation looks at the top without removing it?
3. push and pop on a stack are:
4. In bracket matching, when do you know the string is unbalanced?
Flip the rule — remove from the other end — and you get the stack's equally useful sibling. Next up: Module 8 — Queues, Deques & Circular Buffers.