Stack and Queue Patterns
Monotonic stacks, parentheses matching, BFS-on-deque, sliding-window maximum. Stack and queue as algorithmic primitives, not data structures.
- Chapters
- 5
- Hours
- 2
- Difficulty
- Intermediate
- 4.0intermediate
Monotonic stack
Push indices, pop while the incoming value violates a monotone order. The data structure designed for the intersection of nearest-greater queries and one-pass linear scans.
- 4.1intermediate
Monotonic deque
Pop from both ends to maintain a windowed running max or min in O(1) amortized per slide. The structure that makes sliding-window-extremum problems linear instead of n log k.
- 4.2intermediate
Min and max stacks
Augment a stack with an O(1) aggregate query by pinning a parallel auxiliary stack to it; scale the technique from running min to lazy bulk-update to frequency tracking.
- 4.3intermediate
Expression evaluation and parsing
Stacks suspend operators until their right operand exists. The shunting-yard rhythm and the LeetCode 224/227/772 family where the order characters arrive in is not the order arithmetic should happen.
- 4.4intermediate
Queue from stacks
Implement a queue using only stack primitives. The two-stack lazy-transfer trick, amortized O(1) on every operation, and why the LIFO-from-FIFO inverse has no symmetric construction.