Stacks & Queues

Picture a sink full of plates and a line at a coffee shop.

• Stack (LIFO) — last in, first out. You always deal with the newest pending item first. Plates: you take the one on top.
• Queue (FIFO) — first in, first out. You always deal with the oldest pending item first. Coffee line: first to arrive, first served.

In Python:

stack = []
stack.append(x)   # push — O(1)
stack.pop()       # pop the most recent — O(1)
stack[-1]         # peek

from collections import deque
q = deque()
q.append(x)       # enqueue — O(1)
q.popleft()       # dequeue the oldest — O(1)

Never use list.pop(0) for a queue — it shifts every element and turns O(1) into O(n).

The principle: choose the structure by asking which pending item do I need next — the newest or the oldest? Newest → stack. Oldest → queue. Recursion, undo, and bracket-matching are "newest first." BFS, schedulers, and rate limiters are "oldest first."

Nobody hands you a problem titled "use a stack." You have to smell it. Three reliable scents:

1. Matching / nesting. Brackets, HTML tags, function calls. Every opener waits for its closer, and the closer always belongs to the most recent unclosed opener. That sentence — "most recent unfinished thing" — is a stack.

pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
    if ch in "([{":
        stack.append(ch)
    elif not stack or stack.pop() != pairs[ch]:
        return False
return not stack

2. Undo / backtrack. Text-editor undo, directory navigation (cd ..), evaluating postfix expressions. The last action is the first one reversed.

3. "Nearest greater/smaller to the left/right." Any problem asking, for each element, about the closest element in one direction that beats it. That's the monotonic stack — next section.

The principle: when the problem talks about the most recently seen thing that's still relevant, you're holding a stack whether you named it or not.

Here's the problem that teaches it. Daily temperatures: given temps = [73, 74, 75, 71, 69, 72, 76, 73], for each day, how many days until a warmer one?

Brute force scans rightward from every index: O(n²). The fix is to flip your viewpoint. Don't ask "where is my warmer day?" Ask, as each new day arrives: whose question do I answer?

Keep a stack of indices whose answer is still unknown. The temperatures at those indices are strictly decreasing (if a newer day were warmer than an older one on the stack, it would have answered it already — that's the invariant). When a new temperature arrives, it answers every stacked day it beats:

def days_until_warmer(temps):
    res = [0] * len(temps)
    stack = []                      # indices, temps strictly decreasing
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()         # day j just got its answer: day i
            res[j] = i - j
        stack.append(i)
    return res

Walk it: 73 pushes. 74 arrives, pops 73 (answer: 1 day), pushes. 75 pops 74, pushes. 71, 69 just pile up — each colder than the top. 72 arrives and pops both 69 and 71. 76 pops everything. Each index is pushed once and popped at most once — O(n) total, even with the nested-looking while loop.

The principle: when each element needs its nearest greater (or smaller) neighbor in one direction, keep a stack of the unresolved, ordered so the newcomer resolves them from the top. The stack holds exactly the elements whose future is still undecided.

A classic warm-up with a deep lesson: simulate FIFO using only LIFO parts.

Two stacks: inbox and outbox. Enqueue pushes onto inbox. Dequeue pops from outbox — and only when outbox is empty do you tip inbox over into it, reversing the order:

class Queue:
    def __init__(self):
        self.inbox, self.outbox = [], []

    def enqueue(self, x):
        self.inbox.append(x)

    def dequeue(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
        return self.outbox.pop()

Any single dequeue might cost O(n), but each element moves at most twice total (into inbox, then into outbox), so the amortized cost is O(1). Saying the word amortized and explaining "count moves per element, not per operation" is exactly what interviewers are fishing for.

The principle: two reversals make an identity — and worst-case-per-operation isn't the only honest way to measure cost.

Design questions like "a stack that also returns its minimum in O(1)" test whether you'll pay a little memory to avoid recomputation. Don't scan the stack on every min() call — store the running minimum alongside each element:

stack = []                 # entries: (value, min_so_far)
def push(x):
    m = min(x, stack[-1][1]) if stack else x
    stack.append((x, m))
# min of the whole stack is always stack[-1][1]

Popping needs no repair work, because each entry remembers the minimum of everything beneath it — history travels with the data.

The principle: when a structure must answer an aggregate query in O(1), snapshot the aggregate at every state change instead of recomputing it. The same move powers prefix sums, min-stacks, and versioned caches.