Stacks & Queues

Why this pattern exists / recognition signals

A stack and a queue are the same idea — a linear collection with restricted access points — with opposite access disciplines: a stack is LIFO (last in, first out; think a stack of plates, you take from the top), a queue is FIFO (first in, first out; think a checkout line, you take from the front). Restricting access to one or two ends (instead of allowing arbitrary access, like an array) is what makes both O(1) per operation and is exactly the discipline that mirrors real recursive/sequential structure — that’s why they show up everywhere from “undo history” to “process scheduling.”

Recognition signals — reach for one of these when the problem says:

“matching brackets/parentheses” / “valid expression” → stack (most recent open must close first — that’s LIFO)
“next greater/smaller element”, “daily temperatures”, “largest rectangle in histogram” → monotonic stack
“evaluate postfix/infix expression” → stack
“undo/redo”, “backtrack to previous state”, “call stack simulation” (DFS iterative) → stack
“process in the order received”, “level-order traversal”, “task scheduling by arrival” → queue
“sliding window maximum” → monotonic deque (a queue that supports push/pop at both ends)
“implement X using only Y” (queue using stacks, stack using queues) → tests whether you understand what each primitive can and can’t do cheaply

Core mechanism

LIFO vs FIFO

flowchart TB
    subgraph Stack["Stack (LIFO) — push/pop only at the top"]
        direction TB
        S3["3 ← top (pop returns this)"] --- S2["2"] --- S1["1 ← bottom"]
    end
    subgraph Queue["Queue (FIFO) — push at back, pop at front"]
        direction LR
        Q1["1 ← front (dequeue returns this)"] --- Q2["2"] --- Q3["3 ← back (enqueue adds here)"]
    end

Both support push/pop (or enqueue/dequeue) in O(1) if backed by the right structure — a stack is trivially O(1) on a plain dynamic array (push/pop at the end never shifts anything), but a naive array-backed queue is not (see below).

Monotonic stack — “next greater element” in O(n)

The brute-force approach (“for each element, scan forward until you find a bigger one”) is O(n²) because it re-scans elements you’ve already looked at. A monotonic stack avoids the rescan: keep a stack of indices whose values are in decreasing order (top to bottom). When a new value arrives that’s bigger than the stack’s top, that new value is the “next greater element” for everything smaller sitting on top of the stack — pop them all, recording the answer, then push the new value. Every element is pushed once and popped at most once, so total work is O(n), not O(n²).

Worked example: nums = [2, 1, 2, 4, 3], find the next greater element for each index.

i	nums[i]	stack before (indices, values shown)	action	stack after	next-greater result so far
0	2	[]	push 0	[0(2)]	[-,-,-,-,-]
1	1	[0(2)]	1 < 2, push 1	[0(2), 1(1)]	[-,-,-,-,-]
2	2	[0(2), 1(1)]	2 > 1 → pop 1, ans[1]=2. 2 == 2, top not `<`, so stop popping (strictly greater required); push 2	[0(2), 2(2)]	[-,2,-,-,-]
3	4	[0(2), 2(2)]	4 > 2 → pop 2(idx2), ans[2]=4. 4 > 2 → pop 0(idx0), ans[0]=4. stack empty, push 3	[3(4)]	[4,2,4,-,-]
4	3	[3(4)]	3 < 4, push 4	[3(4), 4(3)]	[4,2,4,-,-]
end	—	[3(4), 4(3)]	stack exhausted, remaining indices get -1	—	[4,2,4,-1,-1]

flowchart LR
    subgraph Trace["nums=[2,1,2,4,3], processing i=3 (val=4)"]
        direction TB
        A["stack top: idx2 (val 2) — 4 > 2, pop, ans[2]=4"] --> B["stack top: idx0 (val 2) — 4 > 2, pop, ans[0]=4"]
        B --> C["stack empty — push idx3 (val 4)"]
    end

Each popped element is popped exactly once, ever — that’s the whole reason total work across the entire array stays O(n) even though it doesn’t look like a single pass.

Efficient queue: two stacks, or a circular buffer

The problem: an array-backed queue that dequeues from index 0 with arr.remove(0) must shift every remaining element left by one — O(n) per dequeue.

Fix 1 — circular buffer (ring array): keep head and tail indices that wrap around ((index + 1) % capacity) instead of physically shifting elements. Enqueue writes at tail and advances it; dequeue reads at head and advances it. No shifting, ever — O(1) both ways, at the cost of a fixed capacity (or amortized resize, like a dynamic array).

flowchart LR
    subgraph Ring["circular buffer, capacity 5, head=1, tail=4"]
        direction LR
        C0["[0]"] --- C1["[1] head → 'B'"] --- C2["[2] 'C'"] --- C3["[3] 'D'"] --- C4["[4] tail → next write here"]
    end
    Note["enqueue writes at tail, then tail=(tail+1)%5
dequeue reads at head, then head=(head+1)%5
never shifts existing elements"]

Fix 2 — two stacks: keep an inStack for enqueues and an outStack for dequeues. Enqueue always pushes onto inStack — O(1). Dequeue pops from outStack; if outStack is empty, dump all of inStack into it first (which reverses the order, turning “oldest at the bottom of inStack” into “oldest at the top of outStack”), then pop.

sequenceDiagram
    participant In as inStack
    participant Out as outStack

    Note over In,Out: enqueue(1), enqueue(2), enqueue(3)
    In->>In: push 1, 2, 3 (bottom→top: 1,2,3)
    Note over In,Out: dequeue() — outStack empty, so transfer
    In->>Out: pop 3, push to Out
    In->>Out: pop 2, push to Out
    In->>Out: pop 1, push to Out
    Note over Out: Out bottom→top: 3,2,1 — so top is 1 (oldest!)
    Out-->>Out: pop() returns 1 ✓ FIFO order preserved

Why this is still O(1) amortized: each element is pushed onto inStack once and popped/pushed across to outStack at most once in its lifetime — the expensive transfer only happens when outStack is empty, and it moves each element exactly once before that element is ever dequeued again. Spread over many operations, the average cost per operation is O(1).

Worked numeric example — valid parentheses

Input: "({[]})"

i	char	stack before	action	stack after
0	`(`	[]	opener → push	[(]
1	`{`	[(]	opener → push	[(, {]
2	`[`	[(, {]	opener → push	[(, {, []
3	`]`	[(, {, []	closer → pop top `[`, matches `]`	[(, {]
4	`}`	[(, {]	closer → pop top `{`, matches `}`	[(]
5	`)`	[(]	closer → pop top `(`, matches `)`	[]
end	—	[]	stack empty at end → valid	—

If the stack isn’t empty at the end, or a closer’s popped value doesn’t match, or you try to pop an empty stack — invalid.

Java — representative implementations

import java.util.*;
 
public class StackQueueOps {
 
    // Valid Parentheses
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
        for (char c : s.toCharArray()) {
            if (!pairs.containsKey(c)) {
                stack.push(c); // opener
            } else {
                if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
                    return false; // mismatched or nothing to close
                }
            }
        }
        return stack.isEmpty(); // every opener must have been closed
    }
 
    // Next Greater Element — monotonic stack, O(n)
    public int[] nextGreaterElement(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Deque<Integer> stack = new ArrayDeque<>(); // holds indices; nums at those indices decrease top->bottom
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                result[stack.pop()] = nums[i];
            }
            stack.push(i);
        }
        return result;
    }
 
    // Queue implemented with two stacks
    static class QueueWithStacks<T> {
        private final Deque<T> inStack = new ArrayDeque<>();
        private final Deque<T> outStack = new ArrayDeque<>();
 
        public void enqueue(T item) {
            inStack.push(item); // O(1)
        }
 
        public T dequeue() {
            if (outStack.isEmpty()) {
                while (!inStack.isEmpty()) {
                    outStack.push(inStack.pop()); // amortized O(1) per element
                }
            }
            if (outStack.isEmpty()) {
                throw new NoSuchElementException("dequeue on empty queue");
            }
            return outStack.pop();
        }
    }
}

Python — representative implementations

from collections import deque
 
 
def is_valid(s: str) -> bool:
    """Valid Parentheses."""
    pairs = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []
    for c in s:
        if c not in pairs:
            stack.append(c)  # opener
        else:
            if not stack or stack.pop() != pairs[c]:
                return False  # mismatched or nothing to close
    return not stack  # every opener must have been closed
 
 
def next_greater_element(nums: list[int]) -> list[int]:
    """Next Greater Element — monotonic stack, O(n)."""
    n = len(nums)
    result = [-1] * n
    stack: list[int] = []  # holds indices; nums at those indices decrease top->bottom
    for i, val in enumerate(nums):
        while stack and nums[stack[-1]] < val:
            result[stack.pop()] = val
        stack.append(i)
    return result
 
 
class QueueWithStacks:
    """Queue implemented with two stacks."""
 
    def __init__(self) -> None:
        self._in: list = []
        self._out: list = []
 
    def enqueue(self, item) -> None:
        self._in.append(item)  # O(1)
 
    def dequeue(self):
        if not self._out:
            while self._in:
                self._out.append(self._in.pop())  # amortized O(1) per element
        if not self._out:
            raise IndexError("dequeue on empty queue")
        return self._out.pop()

Note: collections.deque is Python’s real-world answer to “efficient queue” — it’s a doubly linked list of fixed-size blocks under the hood, giving O(1) appendleft/popleft unlike a plain list, where list.pop(0) is O(n) for the same reason a naive array-backed queue is.

Complexity comparison

Structure / operation	Time	Space	Notes
Stack push/pop (array or linked-list backed)	O(1)	O(n)	Only ever touches one end
Queue enqueue/dequeue, naive array (`remove(0)`)	O(n) dequeue	O(n)	Shifting every remaining element is the bug to avoid
Queue enqueue/dequeue, circular buffer	O(1)	O(n) (fixed or amortized-resized capacity)	No shifting, wraps via modulo
Queue enqueue/dequeue, two stacks	O(1) amortized	O(n)	Occasional O(n) transfer, but each element moves once per lifetime
Monotonic stack (next greater/smaller)	O(n) total	O(n)	Brute force is O(n²) — each element pushed & popped at most once
Monotonic deque (sliding window max)	O(n) total	O(k) window	Push/pop from both ends, O(1) amortized per element

Common pitfalls

Popping an empty stack/queue without checking: crashes or throws — always guard, and in “valid parentheses”-style problems, an empty stack when a closer arrives means invalid, not a crash.
Using list.pop(0) or list.remove(0) in Python (or ArrayList.remove(0) in Java) for a queue: silently O(n) per operation, turning an intended O(n) algorithm into O(n²) — use collections.deque or ArrayDeque/LinkedList instead.
Monotonic stack direction confusion: “next greater element” pops while the new value is bigger than the stack top (decreasing stack); “next smaller element” pops while the new value is smaller (increasing stack) — mixing these up silently produces the wrong relation, not an error.
Off-by-one / wrong comparator on monotonic stack (< vs <=): decide up front whether equal elements count as “greater” — affects whether duplicates get matched to themselves or to a later strictly-greater element.
Forgetting the two-stack queue only pays the transfer cost when outStack is empty: transferring on every dequeue regardless of outStack’s state destroys the amortized O(1) guarantee and degrades to O(n) per operation.
Circular buffer index math: forgetting the modulo wraparound ((tail + 1) % capacity) causes an index-out-of-bounds once tail reaches the array’s physical end, even though the queue isn’t logically full.

Practice problems

Valid Parentheses (stack)
Min Stack (stack with O(1) getMin — track a second stack of running minimums, or store pairs)
Evaluate Reverse Polish Notation (stack-based expression evaluation)
Daily Temperatures (monotonic stack — next warmer day)
Next Greater Element I & II (monotonic stack, II adds a circular array twist)
Largest Rectangle in Histogram (monotonic stack, harder — track index + height together)
Implement Queue using Stacks / Implement Stack using Queues (primitive-swap understanding check)
Sliding Window Maximum (monotonic deque)

Interview angles

“Why is a naive array-backed queue’s dequeue O(n)?” — removing from the front requires shifting every remaining element left by one to keep the array contiguous from index 0; name the fix (circular buffer or two stacks) before being asked.
“Walk through why the monotonic stack approach for next-greater is O(n) and not O(n²), even though there’s a while loop inside a for loop.” — amortized analysis: each element is pushed exactly once and popped at most once across the entire run, so total pop operations across all iterations is bounded by n, not n per outer iteration.
“Implement a queue using two stacks — what’s the amortized complexity of dequeue, and when does the expensive case happen?” — O(1) amortized; the O(n) transfer only fires when outStack is empty, and each element only ever gets transferred once in its lifetime, so cost spreads out.
“Min Stack — how do you get O(1) getMin without scanning the whole stack?” — maintain a parallel stack that tracks the running minimum at each depth (push min(newVal, currentMin) alongside every push), so popping the main stack automatically “un-tracks” the right minimum too.
“When would you reach for a deque instead of a plain stack or queue?” — whenever you need O(1) push/pop at both ends, e.g. a monotonic deque for sliding-window-maximum, or implementing a work-stealing task queue.
“Recursion uses an implicit stack — how would you convert a recursive DFS into an iterative one?” — replace the call stack with an explicit stack of “work to do” (nodes to visit), pushing children in the order that preserves the same visit order the recursion would have produced.

Notes

Explorer