PART 4 · DSA AND COMPLEXITY · CHAPTER 21

Stacks and queues: brackets, monotonic stacks

FreeLesson 46 of 78

A stack is last in, first out, like a pile of plates. A queue is first in, first out, like a ticket line. Picking the right one is usually the whole trick.

BALANCED BRACKETSPYTHON 3.12

def balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack                   # nothing left open

print(balanced('{"a": [1, 2, {"b": (3)}]}'),
      balanced('{"a": [1, 2}'), balanced("(("))

Output

True False False

MONOTONIC STACK: DAYS UNTIL A HIGHER VALUEPYTHON 3.12

def days_until_higher(revenue):
    answer = [0] * len(revenue)
    stack = []                        # indices still waiting
    for i, r in enumerate(revenue):
        while stack and revenue[stack[-1]] < r:
            j = stack.pop()
            answer[j] = i - j           # day j finally beaten
        stack.append(i)
    return answer

print(days_until_higher([1994, 2847, 7291, 6840, 7500, 3000, 3100]))

Output

[1, 1, 2, 1, 0, 1, 0]

A QUEUE: LIST A FOLDER TREE LEVEL BY LEVELPYTHON 3.12

from collections import deque

lake = {"raw": {"orders": ["01.csv", "02.csv"],
                "events": ["a.jsonl"]},
        "README.md": None}

q, files = deque([("", lake)]), []
while q:
    path, node = q.popleft()           # FIFO: shallow first
    for name, child in node.items():
        full = f"{path}/{name}"
        if isinstance(child, dict):
            q.append((full, child))        # a folder: visit later
        elif child is None:
            files.append(full)
        else:
            files += [f"{full}/{f}" for f in child]
print(files)

Output

['/README.md', '/raw/orders/01.csv', '/raw/orders/02.csv', '/raw/events/a.jsonl']

Queues drive BFS (pages 53 and 54), task schedulers and buffers between pipeline stages. Always a deque, never list.pop(0) (page 44).

Use a stack (list: append / pop) when	Use a queue (deque: append / popleft) when
The most recent item must be handled first: brackets, undo, nested parsing	Items must be handled in arrival order: tasks, messages, buffers
You go deep first: DFS, backtracking, recursion turned into a loop	You go level by level: BFS, shortest path when every step costs 1
You wait for "the next bigger/smaller value": monotonic stack	You keep a time window: last 30 minutes of events

Practice before you move on

Extend the bracket checker so it reports the position of the first unmatched bracket.
Load events.jsonl into a deque in arrival order and print the third event.