4. Stacks & Queues

Key Insight

Use a stack when you need LIFO access — specifically for "nearest greater/smaller element" problems via a monotonic stack. Use a deque when you need O(1) both-end access — specifically for sliding window maximum/minimum.

Complexity

Operation	list (stack)	collections.deque
Push / append right	$O(1)$ amortized	$O(1)$
Pop right	$O(1)$ amortized	$O(1)$
Pop left	$O(n)$ ❌	$O(1)$ ✓
Peek	$O(1)$	$O(1)$

---

4.1 Stack Templates

# --- Valid parentheses ---
def is_valid(s: str) -> bool:
    stack = []
    match = {')': '(', '}': '{', ']': '['}
    for c in s:
        if c in '([{':
            stack.append(c)
        elif not stack or stack[-1] != match[c]:
            return False
        else:
            stack.pop()
    return not stack

# --- Evaluate Reverse Polish Notation ---
def eval_rpn(tokens: list[str]) -> int:
    stack = []
    ops = {'+': lambda a,b: a+b, '-': lambda a,b: a-b,
           '*': lambda a,b: a*b, '/': lambda a,b: int(a/b)}
    for t in tokens:
        if t in ops:
            b, a = stack.pop(), stack.pop()
            stack.append(ops[t](a, b))
        else:
            stack.append(int(t))
    return stack[0]

---

4.2 Monotonic Stack

Decreasing monotonic stack: maintains elements in decreasing order — used to find next greater element.
Increasing monotonic stack: used to find next smaller element or largest rectangle in histogram.

# --- Next Greater Element (to the right) ---
def next_greater(arr: list[int]) -> list[int]:
    n = len(arr)
    res = [-1] * n
    stack = []  # stores indices, decreasing by value
    for i, x in enumerate(arr):
        while stack and arr[stack[-1]] < x:
            idx = stack.pop()
            res[idx] = x
        stack.append(i)
    return res

# --- Daily Temperatures (days until warmer) ---
def daily_temperatures(temps: list[int]) -> list[int]:
    res = [0] * len(temps)
    stack = []  # indices
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            res[j] = i - j
        stack.append(i)
    return res

# --- Largest Rectangle in Histogram --- O(n)
def largest_rectangle(heights: list[int]) -> int:
    stack = []  # increasing monotonic (index, height)
    max_area = 0
    for i, h in enumerate(heights):
        start = i
        while stack and stack[-1][1] > h:
            idx, height = stack.pop()
            max_area = max(max_area, height * (i - idx))
            start = idx
        stack.append((start, h))
    for idx, height in stack:
        max_area = max(max_area, height * (len(heights) - idx))
    return max_area

# --- Trapping Rain Water --- O(n)
def trap(height: list[int]) -> int:
    stack = []
    water = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()
            if not stack:
                break
            width = i - stack[-1] - 1
            bounded_h = min(height[stack[-1]], h) - height[bottom]
            water += width * bounded_h
        stack.append(i)
    return water

---

4.3 Deque & Sliding Window Maximum

from collections import deque

# --- Sliding Window Maximum (size k) --- O(n)
def sliding_window_max(nums: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()  # stores indices, decreasing by value
    res = []
    for i, x in enumerate(nums):
        # remove elements outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # maintain decreasing order
        while dq and nums[dq[-1]] < x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

# --- BFS queue template ---
from collections import deque
def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

---

4.4 Key CP Patterns

Problem	Structure	Invariant
Next greater/smaller element	Monotonic stack	Decreasing / increasing
Largest rectangle	Monotonic stack (increasing)	Pop when smaller found
Sliding window max/min	Monotonic deque	Decreasing / increasing
BFS shortest path	deque	FIFO
Expression evaluation	Two stacks (ops + vals)	Operator precedence

---