Stacks & Queues

Stack (LIFO — Last In First Out): push/pop from the same end. Use Python list as stack (append/pop are O(1)).

Queue (FIFO — First In First Out): enqueue at back, dequeue from front. Use collections.deque — O(1) from both ends. Never use list.pop(0) — that's O(n).

Monotonic Stack: a stack that maintains elements in sorted order (increasing or decreasing). Used for "next greater element", "largest rectangle", "trapping rain water" problems.

When to use stack:
• Matching brackets/parentheses → push open, pop on close
• Undo operations, browser history
• DFS (iterative)
• Expression evaluation
• Next Greater Element pattern

When to use queue:
• BFS (level-order traversal)
• Sliding window maximum
• Task scheduling

1from collections import deque
2
3# ── Valid Parentheses ─────────────────────────────────────────────
4def is_valid(s: str) -> bool:
5    stack = []
6    pairs = {')': '(', '}': '{', ']': '['}
7    for ch in s:
8        if ch in '([{':
9            stack.append(ch)
10        elif not stack or stack[-1] != pairs[ch]:
11            return False
12        else:
13            stack.pop()
14    return not stack
15
16# ── Next Greater Element ──────────────────────────────────────────
17def next_greater_element(nums: list[int]) -> list[int]:
18    result = [-1] * len(nums)
19    stack  = []   # stores indices (monotonic decreasing)
20    for i, num in enumerate(nums):
21        while stack and nums[stack[-1]] < num:
22            idx = stack.pop()
23            result[idx] = num
24        stack.append(i)
25    return result
26
27# ── Daily Temperatures (classic monotonic stack) ──────────────────
28def daily_temperatures(temps: list[int]) -> list[int]:
29    result = [0] * len(temps)
30    stack  = []   # indices of unresolved days
31    for i, temp in enumerate(temps):
32        while stack and temps[stack[-1]] < temp:
33            j = stack.pop()
34            result[j] = i - j   # days to wait
35        stack.append(i)
36    return result
37
38# ── BFS with deque ────────────────────────────────────────────────
39def bfs(graph: dict, start: int) -> list[int]:
40    visited = set([start])
41    queue   = deque([start])
42    order   = []
43    while queue:
44        node = queue.popleft()    # O(1) — always use deque, never list.pop(0)
45        order.append(node)
46        for neighbor in graph.get(node, []):
47            if neighbor not in visited:
48                visited.add(neighbor)
49                queue.append(neighbor)
50    return order
51
52# ── Sliding Window Maximum (deque as monotonic queue) ─────────────
53def max_sliding_window(nums: list[int], k: int) -> list[int]:
54    dq     = deque()   # stores indices, decreasing order of values
55    result = []
56    for i, num in enumerate(nums):
57        while dq and nums[dq[-1]] < num:
58            dq.pop()
59        dq.append(i)
60        if dq[0] < i - k + 1:   # remove elements outside window
61            dq.popleft()
62        if i >= k - 1:
63            result.append(nums[dq[0]])
64    return result
65
66print(is_valid("()[]{}" ))                       # True
67print(next_greater_element([2, 1, 2, 4, 3]))    # [4, 2, 4, -1, -1]
68print(daily_temperatures([73,74,75,71,69,72,76,73]))  # [1,1,4,2,1,1,0,0]
69print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))    # [3,3,5,5,6,7]