5.0 Stacks and Queues

Stacks and Queues

Used to maintain temporal or order-based state. Common in parsing, monotonic operations, and backtracking patterns.

1.0 Stack Fundamentals

1. LIFO principle and implementation via arrays or LL
2. Expression parsing and evaluation
3. Reversing structures

2.0 Validity Checking Patterns

1. Valid parentheses/brackets
2. Minimum add to make valid
3. Remove invalid parentheses (generate all)

3.0 Monotonic Stack Patterns

1. Next greater/smaller element
2. Nearest smaller to left/right
3. Histogram problems (max rectangle area)

4.0 Min/Max Stack Variants

1. Stack with min in O(1)
2. Design stack with constant-time retrievals
3. Max Stack or Stack of Stacks

5.0 Backtracking and Undo Stack

1. Evaluate Reverse Polish Notation
2. Path simplification (../, ./)
3. Browser-like undo/redo patterns

6.0 Queue Fundamentals

1. FIFO queue basics and circular queue
2. Implementation with 2 stacks
3. Multi-producer consumer simulation

7.0 Monotonic Queue & Sliding Window

1. Sliding window max/min
2. 1D DP optimizations with queue (jump game, rotten oranges)
3. Using deque for state preservation

8.0 Design Problems with Queue

1. Implement Stack using Queue
2. Implement Queue using Stack
3. LRU cache with deque
4. Moving average / time-based hit counter

9.0 Priority Queue (Heap-backed)

1. Top K elements
2. Merge K sorted streams
3. Frequency sorting
4. Custom comparators

10.0 Special Mentions

1. Stack of stacks
2. Balanced binary expression evaluator
3. Largest rectangle in histogram
4. Implement circular deque
5. Wait time problems (stock span, daily temps)