Stacks and queues cheat sheet

Do the brackets in a line balance?

Push each opening bracket onto a stack. On a closing bracket, the top of the stack must be its partner; pop it, or fail if the stack is empty or holds the wrong kind. At the end the stack must be empty. O(n) time, O(n) space in the worst case.

PAIRS = {")": "(", "]": "[", "}": "{"}


def brackets_balance(line: str) -> bool:
    opened: list[str] = []
    for ch in line:
        if ch in "([{":
            opened.append(ch)
        elif ch in PAIRS:
            if not opened or opened.pop() != PAIRS[ch]:
                return False
    return not opened

How many days until a warmer day?

Keep a stack of days still waiting for a warmer day; their temperatures decrease from bottom to top. For each new day, pop every waiting day that is colder and record the gap, then push the new day. Each day is pushed and popped at most once: O(n) time, O(n) space.

def wait_for_warmer(temps: list[int]) -> list[int]:
    wait = [0] * len(temps)
    pending: list[int] = []  # days still waiting, colder at the top
    for day, t in enumerate(temps):
        while pending and temps[pending[-1]] < t:
            earlier = pending.pop()
            wait[earlier] = day - earlier
        pending.append(day)
    return wait

A stack that also reports its minimum

Store pairs on the stack: the value and the smallest value at or below it. Pushing computes the new minimum from the pair underneath; popping removes the pair, which restores the previous minimum automatically. Every operation is O(1) time; space is O(n).

def run_min_stack(ops: list[str]) -> list[int]:
    stack: list[tuple[int, int]] = []  # (value, smallest so far)
    out = []
    for op in ops:
        if op.startswith("push "):
            v = int(op[5:])
            stack.append((v, min(v, stack[-1][1]) if stack else v))
        elif op == "pop":
            stack.pop()
        elif op == "top":
            out.append(stack[-1][0])
        else:  # "min"
            out.append(stack[-1][1])
    return out

Evaluate an expression written in postfix order

Scan the tokens with a stack of numbers. A number is pushed. An operator pops the right operand, then the left, applies the operation and pushes the result. At the end the stack holds exactly one number: the answer. O(n) time and space.

Apply the backspaces in typed text

Use a list as a stack of characters: push normal characters, pop on '#' when the stack is not empty. Join at the end. O(n) time and space. Reading from the right with a skip counter gives O(1) extra space if you only need to compare two logs.

def apply_backspaces(typed: str) -> str:
    kept: list[str] = []
    for ch in typed:
        if ch != "#":
            kept.append(ch)
        elif kept:
            kept.pop()
    return "".join(kept)

Build a queue out of two stacks

Push onto an 'inbox' stack. To pop or peek, take from an 'outbox' stack; if it is empty, move everything from the inbox to the outbox first, which reverses the order so the oldest item ends on top. Each item moves at most once, so every operation is amortised O(1); the two stacks take O(n) space.

def run_two_stack_queue(ops: list[str]) -> list[int]:
    inbox: list[int] = []
    outbox: list[int] = []
    out = []
    for op in ops:
        if op.startswith("push "):
            inbox.append(int(op[5:]))
            continue
        if not outbox:
            while inbox:
                outbox.append(inbox.pop())
        out.append(outbox.pop() if op == "pop" else outbox[-1])
    return out

Tidy a file path with . and .. parts

Split on '/', and walk the parts with a stack of folder names. Skip empty parts and '.'; on '..' pop if the stack is not empty; otherwise push the part. Join the stack with '/' and add the leading slash. O(n) time and space.

def tidy_path(path: str) -> str:
    folders: list[str] = []
    for part in path.split("/"):
        if part == "..":
            if folders:
                folders.pop()
        elif part and part != ".":
            folders.append(part)
    return "/" + "/".join(folders)

Largest poster that fits under a skyline

For each building, the best poster using its full height stretches left and right until a shorter building. A monotonic stack of increasing heights finds both limits: when a shorter building arrives, pop taller ones; the popped building's poster ends here on the right and at the new stack top on the left. Each building is pushed and popped once: O(n) time, and the stack takes O(n) space.

def largest_poster(heights: list[int]) -> int:
    rising: list[int] = []  # indexes with increasing heights
    best = 0
    for i, h in enumerate(heights + [0]):
        while rising and heights[rising[-1]] >= h:
            tall = heights[rising.pop()]
            left = rising[-1] + 1 if rising else 0
            best = max(best, tall * (i - left))
        rising.append(i)
    return best

How many requests arrived in the recent window?

Keep a queue of recent request times. For each new time t, append it and drop times from the front while they are older than t - w. The queue length is the answer for t. Each time enters and leaves once: O(n) time, O(w) space at most.

from collections import deque


def recent_counts(times: list[int], w: int) -> list[int]:
    recent: deque[int] = deque()
    counts = []
    for t in times:
        recent.append(t)
        while recent[0] < t - w:
            recent.popleft()
        counts.append(len(recent))
    return counts

Stack or queue: LIFO and FIFO

A stack is last in, first out: the newest item leaves first (undo, matching brackets, depth-first search). A queue is first in, first out: the oldest item leaves first (BFS, scheduling, buffering). In Python use a list as a stack and collections.deque as a queue; in Kotlin ArrayDeque serves as both. All the core operations are O(1).

The monotonic stack pattern

A monotonic stack keeps its items in increasing or decreasing order. When a new item would break the order, you pop items until it fits, and each pop is the moment a popped item learns its answer: the new item is its next bigger (or smaller) neighbour. Each item is pushed and popped at most once, so the whole scan is O(n).

Recursion is a stack: converting to an explicit one

Every call pushes a frame holding its arguments and local variables; returning pops it. You can do the same by hand: push the starting state onto a list, then loop: pop a state, do its work, and push the states it would have recursed into. This removes the recursion depth limit and makes the stack's memory explicit.