Queues — Five Problems

Queue = FIFO. The element inserted first is removed first. Enqueue at the rear, dequeue from the front. Implementable via array or linked list.

Deque (double-ended queue). Open at both ends: insert or delete at either the front or the rear, and read either end. This flexibility is what makes problem 5 possible.

• Standard queue operations to implement: push/enqueue, pop/dequeue, peek/front, empty, size.
• Queue underpins BFS (level-order traversal, shortest path in unweighted graphs), sliding windows, and streaming aggregates.

Restatement. Build a FIFO queue exposing push, pop, peek, empty using only stack (LIFO) operations. No other data structure allowed.

Practice: LeetCode 232↗ — "Implement Queue using Stacks".

Pattern / family. Data-structure design; stack↔queue conversion via reversal. Sibling of "Implement Stack using Queues."

Why two stacks. One stack alone gives you access only to the most recently pushed element (the top). But the queue's front is the oldest element, buried at the bottom. A single stack can never expose it directly. Pouring one stack into a second reverses the order, so the oldest element rises to the top of the second stack.

Approach A — costed peek/pop. Keep everything in s1 on push. When you need the front (peek/pop), drain s1 into s2, act on s2.top, then pour back. Correct but O(n) on every read because it moves elements back and forth each time.

Complexity. Approach A: O(n) per read op. Amortized version: O(1) amortized per op, O(n) space. [!] The transcript states complexities loosely; the amortized O(1) result is the accepted answer.

// Amortized O(1) queue backed by two stacks.
class MyQueue {
    private Deque<Integer> in  = new ArrayDeque<>();  // newest on top
    private Deque<Integer> out = new ArrayDeque<>();  // oldest on top

    public void push(int x) {          // enqueue at rear
        in.push(x);
    }

    public int pop() {                 // dequeue from front
        peek();                        // ensure 'out' has the front
        return out.pop();
    }

    public int peek() {                // front element
        if (out.isEmpty()) {           // refill ONLY when empty
            while (!in.isEmpty()) out.push(in.pop());
        }
        return out.peek();
    }

    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}

Edge cases & bugs. Empty on both stacks → empty() true. Calling peek()/pop() on an empty queue is undefined by the problem; guard if needed. Interleaving push and pop is handled automatically because pushes land in in and reads consume out.

Interview follow-ups. Reverse direction: implement a stack using two queues (the cost shifts to push). Discuss amortized vs. worst-case per-operation cost.

Why it matters. The "reverse with a second container" trick recurs whenever you need the opposite access order from what a structure gives you.

Restatement. A MovingAverage(int size) object; each next(int val) returns the average of the last size values seen so far. Before size values exist, average over however many have arrived.

Practice: LeetCode 346↗ — "Moving Average from Data Stream".

Pattern / family. Fixed-size sliding window over a stream, backed by a queue; incremental aggregate.

Worked example (size = 3). next(1)→1.0; next(10)→(1+10)/2 = 5.5; next(3)→(1+10+3)/3 = 4.667; next(5)→ window slides, (10+3+5)/3 = 6.0.

Brute force. Store all values; on each next, re-sum the last size of them. O(k) per call.

Complexity. O(1) per next(), O(k) space for the window (k = size).

// Running-sum sliding window; O(1) per next().
class MovingAverage {
    private final Deque<Integer> q = new ArrayDeque<>();
    private final int size;
    private double sum = 0;

    public MovingAverage(int size) { this.size = size; }

    public double next(int val) {
        q.addLast(val);
        sum += val;
        if (q.size() > size) {          // window overflowed
            sum -= q.pollFirst();       // drop oldest, adjust sum
        }
        return sum / q.size();          // divide by current count
    }
}

Edge cases & bugs. First few calls (window not yet full). Integer sum overflow for large streams → use double/long. The variables (count, front) describe the same subtract-on-eviction logic; queue.size() is the clean way to track count.

Interview follow-ups. Weighted or exponential moving average; handling very large windows; concurrent producers.

Why it matters. Incremental aggregation (add-on-enter, subtract-on-exit) is the core of every fixed-size sliding-window problem — sums, counts, distinct-counts, and more.

Restatement. Each node has a next pointer and a child pointer that may head a separate list (which itself may have children). Flatten into one list following the taught traversal order.

Practice: LeetCode 430↗ — "Flatten a Multilevel Doubly Linked List" [!] (LeetCode's official version uses a doubly linked list and depth-first pre-order flattening; the queue/BFS ordering taught here is the GeeksforGeeks "Flatten a multilevel linked list" variant — search that title to match this exact behavior).

Pattern / family. Linked-list traversal with a helper (auxiliary) data structure; queue used for deferred/level ordering.

The traversal rule. Walk the next chain. Whenever a node has a child, enqueue that child head. When you hit a node whose next is null, dequeue the front of the queue and attach it as the current node's next, then keep walking. Children are appended in FIFO order — hence a queue.

Complexity. O(n) time (each node visited once). O(n) space for the queue in the worst case.

// Node has: int val; Node next; Node child;
public static Node flatten(Node head) {
    if (head == null) return null;
    Queue<Node> q = new LinkedList<>();
    Node cur = head;
    while (cur != null) {
        if (cur.child != null) {        // defer the child list
            q.add(cur.child);
            cur.child = null;           // [+] tidy up dangling child ptr
        }
        if (cur.next == null && !q.isEmpty()) {
            cur.next = q.poll();        // splice next remembered head
        }
        cur = cur.next;
    }
    return head;
}

Edge cases & bugs. A node with a child but no next (attach child, continue). Deeply nested chains. Empty list. [+] Null out child after enqueuing so the flattened list is clean.

Interview follow-ups. A good exercise: solve it with pure pointer manipulation and no queue — doable but far more complex. Also compare against LeetCode 430↗'s DFS pre-order flatten, which produces a different order.

Why it matters. "Defer with a queue, resume when the current path ends" generalizes to tree/graph traversal and any level-order flattening.

Restatement. Given a binary tree and a key, return the node immediately to the right of the key's node on the same level. Return null if none (key is rightmost on its level or absent). Expected O(n).

Practice: GeeksforGeeks↗ — "Find right node of a given node in binary tree" (also stated as "right sibling / next right node in same level"). Related: LeetCode 116/117↗ "Populating Next Right Pointers."

Pattern / family. Level-order traversal (BFS) with a queue; classic BFS template.

Complexity. O(n) time, O(n) space (queue holds up to a full level).

// TreeNode: int data; TreeNode left, right;
public static TreeNode findRight(TreeNode root, int key) {
    if (root == null) return null;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        int n = q.size();                 // freeze this level's size
        for (int i = 0; i < n; i++) {
            TreeNode cur = q.poll();
            if (cur.data == key) {        // found the key node
                return (i == n - 1) ? null // last on level → no right
                : q.peek(); // next is the right node
            }
            if (cur.left  != null) q.add(cur.left);
            if (cur.right != null) q.add(cur.right);
        }
    }
    return null;                          // key not present
}

Edge cases & bugs. Key is the last node in its level → null. Key absent → null. Single-node tree. Forgetting to freeze n before enqueuing children (would run into the next level). Returning only one node, not an array.

Interview follow-ups. Populate next pointers for every node (LeetCode 116/117↗). Do it with O(1) extra space using established level links.

Why it matters. The "freeze level size, loop that many times" BFS template is reusable for level averages, right-side view, zigzag order, and connecting siblings.

Restatement. Given array a and window size k, output the maximum of every contiguous subarray of size k.

Practice: LeetCode 239↗ — "Sliding Window Maximum".

Pattern / family. Monotonic deque (decreasing). The "maintain a useful subset in sorted order" idea mirrors the monotonic-stack technique.

Worked example. a = [10,21,5,18,13,7,6,5,4,9,3], k=3 → maxima: 21, 21, 18, 18, 13→ (per array) 18, 7, 6, ... the running window max for each position. [!] The transcript's spoken numbers drift; trust the mechanism: front of deque = current window max.

Brute force. For each of the n−k+1 windows, scan k elements → O(n·k). Too slow for large n.

Two maintenance steps per element i:

• Evict stale front by index: if deque.front ≤ i - k, it's outside the window → pollFirst.
• Evict smaller from back by value: while a[deque.last] ≤ a[i], those can never be the max again → pollLast. Then addLast(i).

Why decreasing order. When the current element is bigger than the back of the deque, that back element is now useless: it's older and smaller, so it can never be a future window's max while the current element is around. Removing it keeps the deque a shrinking list of "still-possible maxima," with the front being the biggest.

Complexity. O(n) time — each index is pushed and popped at most once. O(k) space for the deque.

// Monotonic decreasing deque of indices.
public static int[] maxSlidingWindow(int[] a, int k) {
    int n = a.length;
    int[] res = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>(); // holds indices, values decreasing
    for (int i = 0; i < n; i++) {
        // 1) drop indices that fell out of the window
        if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
        // 2) drop back indices whose values are <= current (useless)
        while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();
        dq.addLast(i);
        // 3) once the first window is complete, front is the max
        if (i >= k - 1) res[i - k + 1] = a[dq.peekFirst()];
    }
    return res;
}

Edge cases & bugs. k = 1 (every element is its own max). k = n (single window). Duplicates — decide ≤ vs < in the back-eviction; ≤ keeps the deque smaller and is standard. Only start writing output once i ≥ k-1.

Interview follow-ups. Sliding window minimum (flip the comparison). First negative in every window. Constant-max stack/queue. Compare with a max-heap solution: O(n log n) and needs lazy deletion — the deque is strictly better.

Why it matters. The monotonic-deque template — "kick out the useless, keep a sorted candidate set, read one end" — solves a whole family of window-extremum problems in O(n).

Session throughline. A stack is for reversal (LIFO); a queue is for FIFO ordering, moving windows, and BFS. A deque adds two-ended access — the key to O(n) window extremum. When a problem needs the oldest element, a fixed window, level-by-level order, or removal from both ends, reach for a queue or deque.