Stacks & Queues

Stacks and queues answer one question: which unfinished item should be handled next? Choose the order, state what each stored entry means, then write the update rule.

Fast review: focus on matching, reduction, and expiration. Practice Custom Brackets, Compress Array, Min Stack, and Viewer Counter; the other exercises are optional variations.

1. Choose the Access Order

Implementation trap: use Python's deque.popleft() for FIFO removal; repeated list.pop(0) can turn a scan into O(n²). A dynamic-array stack has amortized O(1) push/pop; deque end operations are O(1). In Go, a queue with a head index needs to reclaim consumed storage if it is long-lived.

2. Recipe: Validate Nested Brackets

Use when: pairs can nest, and a closing bracket must match the most recent opening bracket that has not been closed yet. The goal is to validate both bracket types and nesting order.

For example, ([]) is valid. In ([)], after reading ([, the [ must close first. The next character is ), so the string is invalid—even though the total counts match. This is why we check only the stack top, rather than search for any matching opener.

Recipe: push opening brackets. For a closing bracket, reject an empty stack or a mismatched top; otherwise pop the matched opener. At the end, the stack must be empty. The stack always contains the unmatched opening brackets, in their original order.

def valid_brackets(s):
    opening_for = {')': '(', ']': '[', '}': '{'}
    openings = set(opening_for.values())
    stack = []
    for char in s:
        if char in openings:
            stack.append(char)
        elif char in opening_for:
            if not stack or stack[-1] != opening_for[char]:
                return False
            stack.pop()  # This pair is now complete.
        # Ignore non-bracket characters.
    return not stack  # Any remaining opener is unmatched.

Each bracket is pushed and popped at most once: O(n) time, O(n) space. Custom Brackets applies this recipe to a supplied set of pairs. If the task asks which brackets to remove, store opening indices so unmatched positions can be identified.

When a counter is enough: with only ( and ), track balance = opens − closes. It must never be negative and must end at zero. Multiple bracket types require the stack's ordering information; a counter loses it. For a balanced input, cutting at every return to zero gives the maximum number of balanced pieces: a cut at positive balance would leave an opener unmatched. See Balanced Partition.

3. Common Applications

Chain reactions

In Compress Array, repeatedly merge the leftmost adjacent equal pair into its sum. Scan left to right, keeping the processed prefix fully reduced. Hold the new value separately: while it equals the top, pop and add that top to it; push the value only after the chain stops. This requires while, not if.

For [8, 4, 2] followed by 2, the merges are 2+2 → 4+4 → 8+8 → 16. Each input is pushed once and each merge removes an entry, so the scan is O(n) time and O(n) space despite the nested loop. The full implementation is on the problem page.

Reverse Polish Notation is another reduction: pop operands and push the result. Pop the right operand before the left.

Expiring events

In Viewer Counter, keep arrivals in a queue: append on arrival, evict expired entries before answering, then read the remaining count. Timestamps across arrivals and queries must be nondecreasing, so expired entries form a prefix of the queue. The invariant after eviction is that the queue contains exactly the events in the current window.

For the inclusive window [t − window, t], evict while oldest < t - window. At t=12 with window=10, timestamp 2 stays; at t=13 it expires. This counts arrival events, not unique users. Each event enters and leaves once: amortized O(1) per operation, though one query may evict many. Space is O(m) for m retained events; expire on arrivals too if queries may be rare. Out-of-order timestamps break FIFO expiration. Continue to Sliding Windows for maintaining window aggregates.

Reusable idea — carry extra information. Choose the entry's fields from the information needed by the next update:

Grouping changes the representation: number of groups is not number of events. Prefix summaries retain history: pushing 2 twice into Min Stack and popping once must still leave minimum 2. If using a separate minima stack instead of pairs, record tied minima as well.

4. Key Takeaways

• Use a stack for nested brackets; use a queue for expiring events. A closing bracket must match the most recent unmatched opener. With time-ordered arrivals, the oldest events expire first.
• Store extra information to avoid scanning again. In Min Stack, store each value together with the minimum so far. Popping removes both and reveals the previous minimum, so finding the minimum stays O(1).
• A nested loop can still take O(n) total time. In Compress Array, one input may trigger several merges, but the entire scan performs n pushes and at most n pops. Count those total operations instead of multiplying the two loop bounds.

Where to Apply These Ideas

For two-stack implementations, count how often an item switches stacks. In a queue built from two stacks, each item is pushed into the input stack, transferred once to the output stack, and removed once: O(1) amortized per operation. Browser back/forward can move the same page repeatedly, so its cost depends on the total actual moves.