Stacks, queues and deques

Why it matters

Many problems hide a rule about which item to handle next. If the most recently opened thing must be closed first (brackets, function calls, undo history, nested encodings), the structure is a stack. If things must be handled in arrival order (BFS levels, request buffers, events inside a time window), it is a queue. A deque supports both ends and underlies the monotonic-deque technique. In systems the same structures appear as call stacks, ring buffers in drivers and logging pipelines, and work queues.

Core ideas

Pattern: Stack. Push when something opens, pop when it closes, and check that what you pop matches. For Valid Parentheses the invariant is "the stack holds exactly the unmatched openers, innermost on top"; the string is valid when every closer matches the top and the stack ends empty. The same shape handles postfix evaluation (push operands; on an operator pop two, minding operand order for subtraction and division), Decode String (push the current context when entering brackets, pop and combine when leaving) and simulations such as Asteroid Collision. In all of them each element is pushed and popped at most once, so a while loop inside the for loop still gives O(n) total.

Augmented stacks. Store extra state with each entry. A min stack pushes (value, min_so_far): the minimum of a stack changes only on push or pop, so the top entry always knows it.

Queues and amortization. A queue built from two stacks pushes onto inbox and pops from outbox, refilling outbox from inbox only when outbox is empty. One pop can cost O(n), but each element moves from inbox to outbox at most once, so any n operations cost O(n): amortized O(1) per operation. Be able to state this argument in two sentences.

Ring buffers. A fixed array with a head index and a count implements a bounded queue or deque: enqueue at (head + count) % cap, dequeue at head and advance it modulo cap; a front insertion moves head back by one modulo cap. Keeping count (or leaving one slot unused) removes the classic ambiguity where head == tail could mean either full or empty.

Deques. O(1) push and pop at both ends. Use them for BFS queues, for windows that evict old items, and as the basis of the monotonic-deque pattern. Python has collections.deque, Java ArrayDeque, C++ std::deque; in JavaScript use an array with a head index or write a small ring buffer.

Explicit stacks for recursion. Any recursive DFS can be written with a stack of pending work. This avoids recursion limits (CPython's default is typically 1000 frames) and makes the order explicit. Push children in reverse order to match the recursive pre-order; for post-order, push a node twice with a flag that says whether its children are done.

Common misconceptions

• "A dynamic array works as a queue." Removing from the front shifts every remaining element (Python list.pop(0); JavaScript shift() is specified the same way), which can make a BFS quadratic.
• "A queue from two stacks is O(n) per operation." A single operation can be O(n), but the amortized cost is O(1) because each element moves once.
• "head == tail means empty." Without a count or a spare slot it can also mean full; choose one convention and test both states and wrap-around.
• "A loop inside a loop over a stack is quadratic." If every element is pushed and popped at most once, the total work is linear.
• "An iterative DFS visits nodes in the same order as the recursive one." Only if you push children in reverse order.

How to approach it

When you see nesting, matching or "most recent", reach for a stack and say what it holds. When you see levels, arrival order or a time window, reach for a queue or deque. Count pushes and pops to argue linear time. Interviewers typically extend these problems: add a getMin, bound the capacity, support both ends, or make the queue safe for concurrent producers and consumers, a natural follow-up for backend and systems roles.