DSA · Core pattern
Stacks & Queues
Stack = last in, first out (LIFO). Queue = first in, first out (FIFO). Both show up in parsing, BFS, and undo features.
Simple summary: A stack is last-in-first-out; a queue is first-in-first-out.
Example: match brackets with a stack; walk a tree level-by-level with a queue.
1. Stack operations
push(x)— add on top, O(1)pop()— remove top, O(1)peek()— see top without removing, O(1)
Example — valid parentheses "({[]})":
see '(' → push
see '{' → push
see '[' → push
see ']' → pop must be '[' ✓
see '}' → pop must be '{' ✓
see ')' → pop must be '(' ✓
stack empty at end → valid
2. Classic stack problems
- Valid Parentheses — push openers, match closers.
- Min Stack — extra stack tracks current minimum.
- Daily Temperatures — monotonic stack finds next greater element.
- Evaluate Reverse Polish Notation — push numbers, apply operators.
3. Queue operations
enqueue(x)— add at back, O(1)dequeue()— remove from front, O(1)
BFS uses a queue: process a node, then enqueue all unvisited neighbors.
BFS shortest path in unweighted graph:
queue ← start
while queue not empty:
node = dequeue()
for neighbor in node.neighbors:
if not visited: enqueue(neighbor)
4. Deque (double-ended queue)
Add/remove from both ends in O(1). Useful for sliding window maximum when you need to drop from front and back.
5. When to pick which
| Need | Structure |
|---|---|
| Undo / backtracking / DFS iteratively | Stack |
| BFS, scheduling FIFO | Queue |
| Next greater/smaller in array scan | Monotonic stack |
| Sliding window max/min | Deque |
Quick revision
- Stack LIFO — brackets, DFS, monotonic stack.
- Queue FIFO — BFS, task scheduling.
- All basic ops O(1) with array + pointers or linked list.
- Monotonic stack: keep decreasing/increasing order for "next greater" patterns.