Pattern 21: Stacks & Queues

One-line trigger: “Process in LIFO order (stack), FIFO order (queue), or maintain a running answer over a sliding window (deque).”

0. The Templates (Copy-Paste Skeletons)

0.1 Stack — matching / undo / nesting

Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
    if (isOpen(c)) stack.push(c);
    else {
        if (stack.isEmpty() || !matches(stack.pop(), c)) return false;  // pop-and-verify
    }
}
return stack.isEmpty();   // leftovers = unclosed

0.2 Queue — BFS / level-order / multi-source spread

Queue<T> q = new ArrayDeque<>();
q.offer(start);
Set<T> visited = new HashSet<>();  visited.add(start);

int level = 0;
while (!q.isEmpty()) {
    int size = q.size();               // ← FREEZE the size: this is one full level
    for (int i = 0; i < size; i++) {
        T cur = q.poll();
        for (T next : neighbors(cur)) {
            if (visited.add(next)) q.offer(next);   // add() returns false if already present
        }
    }
    level++;                           // level == BFS distance from start
}

0.3 Monotonic Deque — sliding-window max/min in O(n)

// Deque holds INDICES; values are decreasing (max) or increasing (min).
int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> dq = new ArrayDeque<>();     // front = index of current window max
    int[] res = new int[nums.length - k + 1];

    for (int i = 0; i < nums.length; i++) {
        // 1. EVICT FRONT: index has slid out of the window
        if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
        // 2. EVICT BACK: smaller values can never be the max while nums[i] is around
        while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
        // 3. PUSH
        dq.offerLast(i);
        // 4. RECORD once the window is full
        if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
    }
    return res;
}

Flip <= to >= in step 2 for sliding-window minimum. That is the only change.

0.4 Design: Queue via two Stacks (amortised O(1))

class MyQueue {
    private final Deque<Integer> in = new ArrayDeque<>();   // pushes land here
    private final Deque<Integer> out = new ArrayDeque<>();  // pops come from here

    public void push(int x) { in.push(x); }

    public int pop()  { shift(); return out.pop(); }
    public int peek() { shift(); return out.peek(); }
    public boolean empty() { return in.isEmpty() && out.isEmpty(); }

    // Only refill when `out` is EMPTY — this is what makes it amortised O(1).
    private void shift() {
        if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
    }
}

0.5 Design: Min Stack — O(1) getMin

class MinStack {
    private final Deque<int[]> stack = new ArrayDeque<>();  // {value, minSoFar}

    public void push(int val) {
        int min = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
        stack.push(new int[]{val, min});
    }
    public void pop()      { stack.pop(); }
    public int  top()      { return stack.peek()[0]; }
    public int  getMin()   { return stack.peek()[1]; }
}

0.6 Design: Circular Queue (ring buffer)

class MyCircularQueue {
    private final int[] buf; private int head = 0, count = 0;
    MyCircularQueue(int k) { buf = new int[k]; }

    boolean enQueue(int v) {
        if (count == buf.length) return false;
        buf[(head + count) % buf.length] = v;   // tail derived, never stored
        count++; return true;
    }
    boolean deQueue() {
        if (count == 0) return false;
        head = (head + 1) % buf.length; count--; return true;
    }
    int Front() { return count == 0 ? -1 : buf[head]; }
    int Rear()  { return count == 0 ? -1 : buf[(head + count - 1) % buf.length]; }
}

Storing count instead of a tail pointer removes the classic “full vs empty look identical” ambiguity. Say that out loud — it’s the whole point of the question.

1. Pattern Identification & Logic

How to Identify — Stack (LIFO)

“Valid parentheses / balanced brackets / nesting”
“Undo”, “backtrack”, “innermost first”, “decode a nested string”
“Evaluate an expression” (RPN, basic calculator, infix)
“Simplify a path” (/a/./b/../c)
Recursion you’re asked to convert to iterative → an explicit stack is the call stack

How to Identify — Queue (FIFO)

“Level by level”, “layer”, “shortest number of steps in an unweighted graph”
“Minimum moves / turns / transformations” → BFS, and BFS needs a queue
“Everything spreads simultaneously” → multi-source BFS (seed the queue with all sources)
“First one to arrive / round-robin / task scheduling in arrival order”
Producer–consumer, request buffering, rate limiting (sliding-window log)

How to Identify — Monotonic Deque

“Sliding window of size k” and you need max / min / a bounded range inside it
“Longest subarray where max - min ≤ limit” → two deques (one max, one min)
Brute force is O(n·k) and the constraints make that too slow

The ‘Trick’ to Know

Stack: the pop is the pairing. You don’t search for the match — the top of the stack is guaranteed to be it.
Queue + int size = q.size(): freezing the size before the inner loop is what turns a flat BFS into a level-aware BFS. Without it you cannot answer “how many levels”.
Monotonic deque: an element that is smaller than a later element can never be the window max again — it is dominated forever, so delete it immediately. What survives is a decreasing sequence whose front is the answer.

2. Java Implementation (Brute Force vs. Optimal)

Example Problem: Sliding Window Maximum — LC 239

Return the max of every contiguous window of size k.

Brute Force: rescan each window — O(n·k)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        for (int i = 0; i + k <= n; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = i; j < i + k; j++) max = Math.max(max, nums[j]);  // rescan
            res[i] = max;
        }
        return res;
    }
}

Why it’s slow: every window re-reads k elements and throws the work away. At n = 10^5, k = 10^4 that’s 10^9 ops. TLE.

Better but not best: max-heap — O(n log n)

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);   // {value, index}
// push every element; lazily discard the top while its index has slid out of the window

Correct, and worth mentioning as the “obvious” improvement — but the deque beats it.

Optimal: Monotonic Deque — O(n)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();   // INDICES, values decreasing front→back

        for (int i = 0; i < n; i++) {
            if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();   // slid out
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();  // dominated
            dq.offerLast(i);
            if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
        }
        return res;
    }
}

Java Architecture Insights

ArrayDeque is the one class for all three roles. Stack (push/pop/peek), queue (offer/poll/peek), and deque (offerLast/pollFirst/peekLast). Learn one API.
Never java.util.Stack — a synchronized Vector subclass that iterates bottom-to-top. Never LinkedList as a queue either: it works, but every node is a separate heap object, so it is slower and far less cache-friendly than ArrayDeque’s circular array.
ArrayDeque rejects null (throws NPE). That is a feature — poll() returning null unambiguously means “empty”. LinkedList allows null elements and destroys that guarantee.
offer/poll/peek return sentinels; add/remove/element throw. In interview code prefer the sentinel trio and check isEmpty() — no exception handling noise.
PriorityQueue is not FIFO. It is a binary heap; poll() gives the smallest, and equal-priority ordering is undefined. If you need FIFO tie-breaking, add a monotonic sequence number to the comparator.
visited.add(next) returns boolean — using it as the check-and-mark in one call is idiomatic and removes a whole class of “enqueued the same node twice” bugs.

3. Mental Model & Visualization

Monotonic deque trace — `nums = [1,3,-1,-3,5,3,6,7]`, `k = 3`

i=0 v=1    back-evict: none            dq(idx)=[0]        (window not full)
i=1 v=3    3 >= nums[0]=1 → pollLast 0 dq=[1]             (window not full)
i=2 v=-1   -1 < 3 → keep               dq=[1,2]           window [1,3,-1]  max=nums[1]=3  ✓
i=3 v=-3   -3 < -1 → keep              dq=[1,2,3]         window [3,-1,-3] max=nums[1]=3  ✓
i=4 v=5    front 1 <= 4-3=1 → pollFirst
           5 >= -3 → pollLast 3
           5 >= -1 → pollLast 2        dq=[4]             window [-1,-3,5] max=nums[4]=5  ✓
i=5 v=3    3 < 5 → keep                dq=[4,5]           window [-3,5,3]  max=5          ✓
i=6 v=6    6 >= 3 → pollLast 5
           6 >= 5 → pollLast 4         dq=[6]             window [5,3,6]   max=6          ✓
i=7 v=7    7 >= 6 → pollLast 6         dq=[7]             window [3,6,7]   max=7          ✓

RESULT: [3, 3, 5, 5, 6, 7]

The three data structures side by side

STACK (LIFO)              QUEUE (FIFO)                 DEQUE (both ends)
   push ↓  ↑ pop            offer →  [ ][ ][ ]  → poll    pollFirst ←[ ][ ][ ]→ pollLast
        [ 3 ] ← top         front ↑         ↑ back        offerFirst→        ←offerLast
        [ 2 ]                                              front = window MAX (monotonic)
        [ 1 ]
   "innermost / most        "closest first /              "max of the window, with
    recent first"            level by level"               O(1) eviction at both ends"

Senior Mental Triggers

Stack — “nesting, matching, or ‘most recent unresolved thing’.” Queue — “fewest steps / level by level in an unweighted graph.” Monotonic deque — “sliding window of size k and I need its max or min in O(1).”

4. Curated Problem Lists

Stack — Bread & Butter

#	Problem	Difficulty
LC 20	Valid Parentheses	Easy
LC 155	Min Stack	Medium
LC 150	Evaluate Reverse Polish Notation	Medium
LC 71	Simplify Path	Medium
LC 682	Baseball Game	Easy
LC 1047	Remove All Adjacent Duplicates	Easy

Stack — FAANG ‘Aha!’

#	Problem	Difficulty	Twist
LC 394	Decode String	Medium	two stacks: counts + partial strings
LC 224	Basic Calculator	Hard	stack of (result, sign) across parens
LC 227	Basic Calculator II	Medium	precedence without parens
LC 32	Longest Valid Parentheses	Hard	stack of indices, seed with `-1`
LC 895	Maximum Frequency Stack	Hard	map of freq → stack
LC 735	Asteroid Collision	Medium	simulation; collisions resolve on the stack

Queue — Bread & Butter

#	Problem	Difficulty	Why a queue
LC 102	Binary Tree Level Order Traversal	Medium	canonical level BFS
LC 199	Binary Tree Right Side View	Medium	last node of each level
LC 232	Implement Queue using Stacks	Easy	amortised O(1) design
LC 225	Implement Stack using Queues	Easy	rotate-on-push
LC 622	Design Circular Queue	Medium	ring buffer, `count` not `tail`
LC 933	Number of Recent Calls	Easy	sliding-window log — evict older than 3000ms
LC 346	Moving Average from Data Stream	Easy	fixed-size queue + running sum

Queue — FAANG ‘Aha!’

#	Problem	Difficulty	Twist
LC 994	Rotting Oranges	Medium	multi-source BFS; seed ALL rotten cells
LC 542	01 Matrix	Medium	multi-source BFS from every 0
LC 286	Walls and Gates	Medium	multi-source BFS from every gate
LC 127	Word Ladder	Hard	BFS on an implicit graph; bidirectional BFS optimises it
LC 752	Open the Lock	Medium	BFS over 10^4 states + deadend set
LC 1091	Shortest Path in Binary Matrix	Medium	8-directional BFS
LC 621	Task Scheduler	Medium	greedy + cooldown queue
LC 641	Design Circular Deque	Medium	ring buffer, both ends
LC 362	Design Hit Counter	Medium	queue of timestamps (or 60-slot ring)

Monotonic Deque

#	Problem	Difficulty
LC 239	Sliding Window Maximum	Hard
LC 1438	Longest Subarray with Absolute Diff ≤ Limit	Medium
LC 862	Shortest Subarray with Sum at Least K	Hard
LC 1696	Jump Game VI	Medium
LC 918	Maximum Sum Circular Subarray	Medium

5. Time & Space Complexity Table

Structure / Approach	Push/Offer	Pop/Poll	Peek	Space	Notes
`ArrayDeque` (stack or queue)	O(1) amort	O(1)	O(1)	O(n)	circular array; resizes by doubling
`LinkedList` as queue	O(1)	O(1)	O(1)	O(n)	works, but node-per-element → slower
`PriorityQueue`	O(log n)	O(log n)	O(1)	O(n)	not FIFO
Queue from 2 stacks	O(1)	O(1) amort	O(1) amort	O(n)	each element moves at most twice
Sliding-window max — brute	—	—	—	O(1)	O(n·k) total
Sliding-window max — heap	—	—	—	O(n)	O(n log n) total
Sliding-window max — deque	—	—	—	O(k)	O(n) total — each index in/out once
BFS with a queue	—	—	—	O(V)	O(V+E) total

6. Common Variants & Extensions

Multi-source BFS — seed the queue with every source before the loop. LC 994 / 542 / 286 all collapse to “normal BFS, different initialisation”. This is the single highest-value queue variant in interviews.
Bidirectional BFS — search from both ends and meet in the middle; cuts the branching factor exponent in half (LC 127). Mention it even if you don’t code it.
0-1 BFS — edge weights are only 0 or 1: use a Deque, offerFirst for weight-0 edges and offerLast for weight-1. Gives Dijkstra’s answer in O(V+E) with no heap.
Two deques at once — LC 1438 keeps a max-deque and a min-deque over the same window.
Stack-based iterative traversal — the explicit way to convert any recursive DFS to iterative when the interviewer asks about stack-overflow risk on deep inputs.
Monotonic stack (next greater / smaller) is the sibling pattern — see 20-Monotonic-Stack.

7. Interview Red Flags & Gotchas

❌ Forgetting int size = q.size() before the inner BFS loop. Without it, levels bleed into each other and any “how many steps” answer is wrong.
❌ Marking visited on poll() instead of on offer(). The same node then gets enqueued many times before it is ever dequeued — still correct, but the queue blows up to O(E) and on a dense graph you’ll time out. Mark when you enqueue.
❌ java.util.Stack / LinkedList as a queue. Both work; both signal you learned this from a 2011 tutorial.
❌ PriorityQueue when the question says “in order received”. Heaps are not FIFO.
❌ Comparator overflow: (a, b) -> b - a overflows on values near Integer.MAX_VALUE. Use Integer.compare(b, a).
❌ Circular queue “full vs empty”: head == tail is ambiguous. Track count, or deliberately waste one slot — and say which you chose and why.
❌ Monotonic deque storing values not indices. You then can’t tell when the max has slid out of the window. Store indices.
❌ Popping an empty stack in a bracket problem — check isEmpty() before pop(), and remember that a non-empty stack at the end means unclosed brackets.

8. Companion 90-second Pitch (verbal)

“For sliding-window maximum the brute force rescans every window — O(n·k). A max-heap gets it to O(n log n) with lazy deletion. But the key observation is that if nums[j] is smaller than some later nums[i], then nums[j] can never be the window max again — nums[i] outlives it and dominates it. So I keep a deque of indices whose values are decreasing front to back. At each step I evict the front if its index has slid out of the window, evict from the back everything nums[i] dominates, then push i. The front is always the current window’s max, in O(1). Each index enters and leaves the deque exactly once, so it’s O(n) time and O(k) space. I use ArrayDeque for this — it’s the same class I’d use as a stack or a plain queue, it’s array-backed rather than node-based, and unlike LinkedList it rejects nulls so a null from poll() unambiguously means empty.”

Pattern 21: Stacks & Queues (incl. Monotonic Deque, Design & Simulation)