Recap — Stack and Queue Patterns

# Stack and Queue Patterns Stack (LIFO) and queue (FIFO) seem simple, but unlock specific problem patterns. Stack especially is more versatile than students realize. ## Stack basics Last-in, first-out. Operations: - push: add to top — O(1) - pop: remove from top — O(1) - peek: see top without removing — O(1) Python: `stack = []; stack.append(x); stack.pop()`. ### Pattern 1: Matching brackets ```python def valid_parens(s): stack = [] pairs = {')': '(', ']': '[', '}': '{'} for ch in s: if ch in '([{': stack.append(ch) elif ch in ')]}': if not stack or stack.pop() != pairs[ch]: return False return not stack ``` Most "is this valid?" or "is this balanced?" problems use a stack. ### Pattern 2: Reverse order processing ```python def reverse_words(s): stack = s.split() return ' '.join(stack[::-1]) ``` (Trivial; but more complex problems like "evaluate reverse polish notation" use this pattern with stack.) ### Pattern 3: Backtracking state ```python def simplify_path(path): stack = [] for part in path.split('/'): if part == '..': if stack: stack.pop() elif part and part != '.': stack.append(part) return '/' + '/'.join(stack) ``` Anywhere you need "go back" semantics: stack. ## Monotonic stack A stack where elements are kept in monotonic (increasing or decreasing) order. Used for "next greater/smaller element" style problems. ### Problem: Next greater element ```python def next_greater(arr): result = [-1] * len(arr) stack = [] # stack of indices, values decreasing for i, x in enumerate(arr): while stack and arr[stack[-1]] < x: j = stack.pop() result[j] = x stack.append(i) return result ``` Walkthrough on `arr = [2, 1, 3]`: - i=0, x=2: stack empty, push 0. Stack: [0]. - i=1, x=1: arr[0]=2 ≥ 1, don't pop. Push 1. Stack: [0, 1]. - i=2, x=3: arr[1]=1 < 3, pop 1, result[1]=3. arr[0]=2 < 3, pop 0, result[0]=3. Push 2. Stack: [2]. Result: [3, 3, -1]. Each element is pushed and popped at most once → O(N) total. ### When monotonic stack applies - "Next greater/smaller element" - "Daily temperatures" (next warmer day) - "Largest rectangle in histogram" - "Trapping rain water" - "Stock span" All "for each element, find the nearest larger/smaller in some direction" problems. ## Queue basics First-in, first-out. Operations: - enqueue: add to back — O(1) - dequeue: remove from front — O(1) with `collections.deque` Python: use `collections.deque`, not `list` (popping from front of list is O(N)). ```python from collections import deque q = deque() q.append(x) # enqueue q.popleft() # dequeue ``` ### Pattern: BFS (Breadth-first search) The single most common use of a queue: ```python def bfs(graph, start): visited = {start} q = deque([start]) while q: node = q.popleft() process(node) for nb in graph[node]: if nb not in visited: visited.add(nb) q.append(nb) ``` Used for shortest path in unweighted graph, level-order tree traversal, etc. ### Pattern: Sliding window maximum (deque-based) ```python def sliding_window_max(nums, k): result = [] q = deque() # stores indices; values decreasing for i, x in enumerate(nums): while q and q[0] = k - 1: result.append(nums[q[0]]) return result ``` Monotonic deque — like monotonic stack but allows removal from both ends. ## Stack vs queue vs deque | Need | Use | |---|---| | LIFO (last in, first out) | stack (Python list) | | FIFO (first in, first out) | queue (deque) | | Both ends in O(1) | deque | | Priority order | heap (separate topic) | ## Common mistakes 1. **Using `list.pop(0)` for queue.** O(N) — use `deque.popleft()`. 2. **Forgetting empty-stack check.** `stack.pop()` on empty raises IndexError. 3. **Confusing stack with queue.** "Last in" → stack. "First in" → queue. 4. **Pushing values instead of indices in monotonic stack.** Index gives you position info too. ## Takeaway Stack: LIFO. Used for balanced-brackets, reverse-order, backtracking, monotonic-stack patterns. Queue: FIFO. Used for BFS and level-order traversals. Monotonic stack: O(N) solution to "next greater/smaller" style problems. Use `deque` in Python for both ends in O(1). Recognize by pattern: matching → stack; "next greater" → monotonic stack; "shortest unweighted path" → queue (BFS).