Patterns

Stacks and queues

Stacks and queues are not exciting data structures. They are policies about who gets served next. A stack serves the most recently pushed item. A queue serves the oldest item still waiting. Most interview problems that "need a stack" are really problems about nesting, cancellation, or undo. Most interview problems that "need a queue" are really problems about fairness across time, including the level-by-level walk you will see again on the trees and graphs pages.

If you can describe the policy in one sentence, the implementation is usually a Python list or a deque. The hard part is seeing the policy in the story.

Stacks and nested structure

A stack is the right model when a later item can close or cancel an earlier item, and the item it closes is the nearest one that is still open. Parentheses are the textbook picture. Folder paths, function calls, and "undo the last edit" are the same picture wearing different nouns.

Original task: a route string uses parentheses and square brackets as grouping marks, plus other characters you should ignore. Return whether every opener has a matching closer of the same type, in a properly nested order.

def grouping_is_balanced(route: str) -> bool:
    closing = {")": "(", "]": "["}
    stack: list[str] = []
    for char in route:
        if char in "([":
            stack.append(char)
        elif char in closing:
            if not stack or stack[-1] != closing[char]:
                return False
            stack.pop()
    return not stack


assert grouping_is_balanced("(a[b]c)") is True
assert grouping_is_balanced("([)]") is False
assert grouping_is_balanced("(") is False
assert grouping_is_balanced("") is True

Each character is handled once. Each opener is pushed once and popped at most once. Time is linear in the length of the route. Extra space is proportional to the deepest nesting, which is at most the length of the string.

The false case ([)] is the one a counter variable cannot handle. A counter for parentheses and a counter for brackets would both end at zero, and the string is still wrong, because the closer does not match the nearest opener. The stack stores that "nearest" fact. When you pop, you are claiming the closer belongs to that opener and to no other.

The empty stack on a closer is a mismatch, not a cue to keep going. The non-empty stack at the end is also a mismatch: something was opened and never closed. The empty string is balanced. Decide that explicitly so you do not special-case it by accident later.

The strings page treats other character problems that are not about nesting. Do not put every string task on a stack. Ask whether the most recent unmatched item is the one a new item must talk to. If the task is "are these two strings anagrams," the answer is no, and a frequency map is the tool.

Using a list as a stack, carefully

In Python, list.append and list.pop() are the stack operations, and both are amortized constant time at the end of the list. list.pop(0) is not a stack operation and it is not a cheap queue operation either. It moves every later element. If you need a queue, use collections.deque, where pops from the left are cheap.

A second stack pattern is the monotonic stack: the stack stays sorted in a rough sense because you pop items that can no longer be the answer once the current item arrives. The story is "the previous smaller bar is blocked by this taller one." You do not need that pattern for every stack problem. You need it when each element is looking for the nearest neighbor that satisfies an inequality. If you cannot name the neighbor, do not build a monotonic stack. A plain stack, or no stack, is clearer. Interviewers can tell when a technique was selected from a list of names rather than from the problem.

Queues and fair turns

A queue answers "who has been waiting the longest?" Printers, ticket windows, and breadth-first search all share that policy. If the story says the newest arrival should jump ahead, you wanted a stack, or a priority rule, which is a heap. The heaps page is the priority version. Do not fake a priority rule by sorting the queue on every insertion unless n is tiny and you say so.

Original task: a print lab receives jobs as (pages, job_id) in arrival order. The printer finishes at most page_budget pages, then sends the job to the back if it still has pages left. Return the ids in the order they fully finish. This is a small round-robin simulator, written so the queue policy is visible.

from collections import deque


def finish_order(jobs: list[tuple[int, str]], page_budget: int) -> list[str]:
    queue = deque(jobs)
    finished: list[str] = []
    while queue:
        pages, job_id = queue.popleft()
        pages -= page_budget
        if pages <= 0:
            finished.append(job_id)
        else:
            queue.append((pages, job_id))
    return finished


assert finish_order([(3, "a"), (1, "b")], 2) == ["b", "a"]
assert finish_order([(2, "a")], 5) == ["a"]

Each successful pop takes a job from the front. If work remains, the job joins the back, behind whatever was already waiting. In the assert, job a uses 2 of its 3 pages and goes to the back, job b finishes, then a finishes. That order is the policy. A stack would have finished a before b if you always continued the latest job, which is a different lab.

Complexity depends on the totals. Every unit of page_budget work across all jobs causes a constant amount of queue work, so the time is proportional to the total pages divided by the budget, plus the number of jobs. Say that honestly. Do not claim the function is linear in the number of jobs if a single job has a million pages and the budget is one. Extra space is proportional to the number of jobs still waiting.

If page_budget is zero or negative, the loop never finishes. Guard that before you use the function in anything real. Interview prompts usually promise a positive budget. Repeating the promise in an assert or a precondition is still a good habit, and it is one of the common mistakes themes: trusting a loop without a reason it terminates.

What to say, and a drill

Say the policy first. "A closer has to match the nearest opener, so I keep openers on a stack." Or "jobs that are not finished should wait behind jobs that have not had a turn, so I use a queue." Then name the Python type. Then give the complexity, including the awkward part if the awkward part exists.

For the drill, extend grouping_is_balanced with curly braces and an assert for "{[}". Then write a queue function that simulates a simple ticket line: each person has a number of questions, the agent answers one question per turn, and unfinished people go to the back. It will look almost like the printer. That similarity is what you want to notice. After that, read the tree page and implement a level-order traversal with the same deque. The traversal will feel new, and the queue will not.