When a stack or queue is the answer

Halfway through scanning a string or a stream of events, you realise you have to set something aside and come back to it later. Whether you come back to the newest thing you set aside or the oldest one decides the data structure, and saying which out loud is often the moment the interviewer sees you've found the shape of the problem. After this lesson you can pick between a stack and a queue from the wording of a prompt, use the right Python type for each, replace recursion with your own stack, answer "next lower value" questions in one pass with a monotonic stack, and track the maximum of a moving window with a deque.

Newest first or oldest first

A stack hands back the item added most recently: last in, first out (LIFO), like a pile of papers where you only ever touch the top sheet. A queue hands back the item that has waited longest: first in, first out (FIFO), like a line at a ticket counter.

A Python list is a resizable array, so adding and removing at the end is cheap. ("Amortized" means the occasional resize averages out over many appends; Big O as you'd say it in an interview covers it.) The front is another matter. list.pop(0) shifts every remaining element one slot left, which costs O(n) for a list of n items, so draining a list from the front costs O(n²) in total. A deque (double-ended queue) is built from linked blocks of slots, so both of its ends cost O(1). It can serve as a stack too, but indexing into its middle is O(n). Leave queue.Queue for threaded code; its locking buys you nothing in an interview.

Interviewers notice queue = [] followed by queue.pop(0) inside a breadth-first search. The code is correct, and on a large graph it can turn a linear search quadratic in the number of nodes queued, so reach for deque before anyone asks.

A stack holds whatever is still open

Nesting means that anything opened inside something else must close before the outer thing does. That rule is LIFO: whatever closes next is whatever opened most recently. So when a problem has opens and closes (brackets, tags, function calls, indentation levels), push on open, pop on close, and the top of the stack is always the innermost thing still open.

Here is the idea on a profiler log. Each event says a function started or ended at some time, calls nest, and you want each function's exclusive time: the time it was actually running, not waiting on a function it called.

def exclusive_times(events):
    """events: (time, name, kind) in time order, kind "start" or "end",
    calls properly nested. Returns {name: time spent running on top}."""
    totals = {}
    open_calls = []    # stack of names; the top is the call running now
    last_time = None
    for time, name, kind in events:
        if open_calls:
            running = open_calls[-1]
            totals[running] = totals.get(running, 0) + time - last_time
        if kind == "start":
            open_calls.append(name)
        else:
            open_calls.pop()
        last_time = time
    return totals

Suppose main starts at 0, parse runs from 2 to 5, save runs from 6 to 9 and main ends at 10. The result is main 4, parse 3 and save 3. Between any two events at most one function is running, the one on top, so charging each gap to the top is the whole algorithm. A stack of names, rather than a set of open names, is also what makes recursion work: if f calls f, the name sits on the stack twice and comes off twice. The cost is O(e) time and O(d + f) extra space, where e is the number of events, d the deepest nesting and f the number of distinct function names.

The stack checks the log for free, too: an end event whose name isn't the one on top means the log is broken. Undo has the same shape. Each edit pushes what it would take to reverse it, and undo pops the newest entry.

Your own stack in place of recursion

Every recursive function already uses a stack: the call stack, where each pending call waits for the one it made. You can keep the pending work in your own list instead. Do that when the depth could pass Python's default limit of 1,000 frames, or when you want to pause a traversal and resume it later.

Flattening a nested list shows the change. The recursive version loops over the items and calls itself on each sublist. The iterative version keeps a stack of items still to visit:

def flatten(nested):
    """Integers of an arbitrarily deep nested list, left to right."""
    out = []
    stack = [nested]
    while stack:
        item = stack.pop()
        if isinstance(item, list):
            stack.extend(reversed(item))  # first child must come off first
        else:
            out.append(item)
    return out

The comment on extend carries the one subtle point. A stack returns the last thing pushed, so pushing a list's children in their own order visits them backward: flatten([1, [2, 3], 4]) would come out [4, 3, 2, 1]. Pushing them reversed puts the first child on top. An interviewer who sees output in the wrong order will ask you to trace it, so trace it yourself first.

For the cost, let t be the total number of entries in every list at every level, numbers and sublists alike. Each is pushed once and popped once, so the time is O(t). The stack can hold O(t) entries, but they are ordinary list slots rather than interpreter frames, so a list nested 10,000 levels deep, which makes the recursive version raise RecursionError, flattens without trouble.

"I'll keep my own stack so the depth isn't capped by the interpreter. A stack reverses order, so I push the children right to left."

A monotonic stack finds the next lower value

Some prompts ask, for every element, about the first later element that beats it: the next warmer day, the next lower price. Checking every later element is O(n²). A monotonic stack does it in one pass. "Monotonic" means the values on the stack only rise, or only fall, from bottom to top.

Take daily prices and ask, for each day, how many days pass until a strictly lower price. Keep a stack of the days still waiting for an answer. A new price is the answer for every waiting day with a higher price, and those days are all at the top of the stack:

def days_until_lower(prices):
    """For each day, the number of days until a strictly lower price, or 0."""
    wait = [0] * len(prices)
    waiting = []  # indices with no lower price yet; prices never fall going up
    for day, price in enumerate(prices):
        while waiting and prices[waiting[-1]] > price:
            earlier = waiting.pop()
            wait[earlier] = day - earlier
        waiting.append(day)
    return wait

For prices [5, 7, 6, 4, 8, 3] the answer is [3, 1, 1, 2, 1, 0]. Push indices, not prices: you need the index to measure the distance, and you can always look the price up. The prices on the stack never fall from bottom to top, because a lower price pops every higher one before it is pushed.

The nested while makes this look quadratic, and calling it O(n²) is the slip interviewers hear most. Each day is pushed once and popped at most once, so the inner loop runs at most n times across the whole scan: O(n) time and O(n) space for n days.

"The inner loop looks nested, but every index goes on the stack once and comes off at most once, so the total work over the whole scan is O(n)."

To ask about the next higher value instead, flip the comparison. To look backward for the previous lower value, pop while the top's price is at least the current one, then read the top before you push.

Queues keep arrival order

Reach for a queue when work must be handled in the order it arrived: requests waiting for a worker, or jobs waiting for a printer. A common variant counts events in the last minute: append each timestamp, call popleft while the front is 60 or more seconds old, and the queue's length is the count. Each timestamp enters once and leaves once, so the work averages O(1) per event.

Breadth-first search (BFS) is the queue's most common interview use. Because the queue returns nodes in the order they were found, BFS visits everything one edge from the start before anything two edges away, which is why it finds the path with the fewest edges in an unweighted graph. Choosing a tree or graph traversal works through it.

A deque tracks the maximum of a moving window

A sliding window is a range that moves forward through the data, such as the last 50 items or the last 10 seconds. Keeping its sum is easy: add the newcomer, subtract whatever left. Keeping its maximum is harder, because when the maximum leaves you need the next largest without rescanning.

Keep a deque of candidates. A value stops mattering once a value at least as large arrives after it, since the later one stays in the window at least as long. So each new value first removes, from the back, every candidate that is no larger than itself, then joins at the back. The candidates' values fall from front to back, the front is the maximum, and values that age out leave from the front.

Here it is for a monitoring dashboard: latency samples arrive with timestamps, and for each one you report the peak over the last window seconds.

from collections import deque

def rolling_peak(samples, window):
    """samples: (time, value) pairs in time order; window > 0.
    For each sample, the largest value with time in (time - window, time]."""
    peaks = []
    candidates = deque()  # (time, value); values strictly fall left to right
    for time, value in samples:
        while candidates and candidates[-1][1] <= value:
            candidates.pop()          # can never be the peak again
        candidates.append((time, value))
        while candidates[0][0] <= time - window:
            candidates.popleft()      # slid out of the window
        peaks.append(candidates[0][1])
    return peaks

Each sample enters the deque once and leaves at most once, so the time is O(n) for n samples, and the extra space is O(w), where w is the most samples that fall inside one window. The version interviewers see most often rescans: max() over the window for every new sample, O(n·w) in total. That is a fine first answer if you name its cost and then replace the rescan.

Practicing with these questions

Before coding any of these, say which end you remove from and why: newest first means a stack, oldest first means a queue. Then write down what one entry holds (a character, an index, a pair) and what stays true of the entries from bottom to top or front to back. Most bugs in these problems come from storing the wrong thing, so settle that before the loop.

Start with Check That a String of Three Bracket Types Is Properly Nested as a warm-up and aim to finish it in five minutes, tests included. For the window question below, write the rescanning version first and state its cost before you look for anything faster. The Blind 75 stack set has more short drills.