Queues

The queue is the stack’s mirror image. Where a stack processes the most recent element first (LIFO), a queue processes the oldest element first (FIFO). This ordering property makes queues indispensable for breadth-first traversal, task scheduling, request buffering, and any system that needs fairness — first come, first served.

Queues appear in interviews less frequently than stacks in isolation, but they dominate when combined with trees and graphs (BFS), system design (message queues), and priority-based processing (scheduling). Master the variants in this chapter used in those higher-level problems.

FIFO Semantics: Enqueue, Dequeue, Peek

A queue supports three core operations:

Operation	Description	Time
enqueue(e) / offer(e)	Add element to the back	O(1)
dequeue() / poll()	Remove and return the front element	O(1)
peek()	Return the front element without removing	O(1)

Java’s Queue<T> interface defines two flavors: throwing (add, remove, element) and returning-null (offer, poll, peek). In interview code, use the non-throwing versions — null returns are easier to handle than catching exceptions in algorithm logic.

Circular Queue: The Ring Buffer

A naive array-based queue has a problem: as you dequeue from the front, the usable portion of the array shifts right, wasting space at the beginning. A circular queue (ring buffer) solves this by wrapping around — when the tail pointer reaches the end of the array, it jumps back to index 0.

public class CircularQueue<T> {
    private final Object[] data;
    private int head;
    private int tail;
    private int size;
    private final int capacity;

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        this.data = new Object[capacity];
        this.head = 0;
        this.tail = 0;
        this.size = 0;
    }

    public boolean enqueue(T element) {
        if (isFull()) return false;
        data[tail] = element;
        tail = (tail + 1) % capacity;
        size++;
        return true;
    }

    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (isEmpty()) throw new java.util.NoSuchElementException("Queue is empty");
        T element = (T) data[head];
        data[head] = null; // Allow GC
        head = (head + 1) % capacity;
        size--;
        return element;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) throw new java.util.NoSuchElementException("Queue is empty");
        return (T) data[head];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }

    public int size() {
        return size;
    }
}

Modular Arithmetic: The Heart of the Ring Buffer

The expression (index + 1) % capacity is the key operation. It advances the pointer by one, wrapping around to 0 when it reaches the end. This works because the modulo operator produces a value in [0, capacity - 1] — exactly the valid index range.

Why track size separately? Without a size field, distinguishing “full” from “empty” is ambiguous — both states have head == tail. The alternatives are:

1. Waste one slot: The queue is full when (tail + 1) % capacity == head, sacrificing one element of capacity. Used in many C implementations.
2. Boolean flag: An isFull flag toggled on enqueue/dequeue.
3. Size counter: The cleanest approach. Track size explicitly and derive full/empty from it.

In interviews, the size-counter approach produces the most readable code. Choose it unless the interviewer specifically asks for the one-wasted-slot variant.

Complexity: All operations are O(1) with no amortization — the array never resizes.

Double-Ended Queue (Deque)

A deque allows insertion and removal at both ends. It generalizes both stacks (use one end) and queues (use opposite ends).

Java’s ArrayDeque<T> implements Deque<T> with a circular array internally. It is the recommended general-purpose stack and queue in Java:

Deque<String> deque = new ArrayDeque<>();

// Queue behavior (FIFO)
deque.offerLast("first");
deque.offerLast("second");
String front = deque.pollFirst(); // "first"

// Stack behavior (LIFO)
deque.offerFirst("top");
String top = deque.pollFirst();   // "top"

ArrayDeque outperforms both LinkedList (for queue usage) and Stack (for stack usage):

Feature	ArrayDeque	LinkedList	Stack
Push/Pop	O(1) amort.	O(1)	O(1) sync’d
Cache locality	Excellent	Poor	Excellent
Per-element overhead	~0	24+ bytes	~0
Thread-safe	No	No	Yes (unnecessary)

In every interview, use ArrayDeque. It is faster, uses less memory, and sends the right signal about your JDK knowledge.

Priority Queue: Heap-Backed Ordering

A priority queue orders elements by priority rather than insertion time. The highest-priority element (smallest value in a min-heap, largest in a max-heap) is always at the front.

Java’s PriorityQueue<T> uses a binary min-heap stored as an array:

// Min-heap: smallest element at the front
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(2);
minHeap.offer(8);
int smallest = minHeap.poll(); // 2

// Max-heap: largest element at the front
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(5);
maxHeap.offer(2);
maxHeap.offer(8);
int largest = maxHeap.poll(); // 8

Implementing a MinHeap from Scratch

Interviewers sometimes ask you to implement the underlying heap. Here is a clean Java 25 implementation:

public class MinHeap {
    private final int[] data;
    private int size;

    public MinHeap(int capacity) {
        this.data = new int[capacity];
        this.size = 0;
    }

    public void insert(int val) {
        if (size == data.length) throw new IllegalStateException("Heap is full");
        data[size] = val;
        siftUp(size);
        size++;
    }

    public int extractMin() {
        if (size == 0) throw new java.util.NoSuchElementException("Heap is empty");
        int min = data[0];
        data[0] = data[--size];
        siftDown(0);
        return min;
    }

    public int peekMin() {
        if (size == 0) throw new java.util.NoSuchElementException("Heap is empty");
        return data[0];
    }

    private void siftUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (data[index] >= data[parent]) break;
            swap(index, parent);
            index = parent;
        }
    }

    private void siftDown(int index) {
        while (true) {
            int smallest = index;
            int left = 2 * index + 1;
            int right = 2 * index + 2;

            if (left < size && data[left] < data[smallest]) {
                smallest = left;
            }
            if (right < size && data[right] < data[smallest]) {
                smallest = right;
            }

            if (smallest == index) break;
            swap(index, smallest);
            index = smallest;
        }
    }

    private void swap(int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

Array representation of a binary heap: For a node at index i:

• Parent: (i - 1) / 2
• Left child: 2 * i + 1
• Right child: 2 * i + 2

This mapping stores a complete binary tree in a flat array without pointers — cache-friendly and space-efficient.

Complexity:

• insert: O(log n) — sift up at most log n levels
• extractMin: O(log n) — sift down at most log n levels
• peekMin: O(1) — the root is always the minimum

Classic Problem: Implement Queue Using Two Stacks

Problem: Implement a FIFO queue using only two LIFO stacks.

This is one of the most frequently asked data structure problems. The trick: one stack handles incoming elements, the other handles outgoing.

public class QueueFromStacks<T> {
    private final Deque<T> inStack = new ArrayDeque<>();
    private final Deque<T> outStack = new ArrayDeque<>();

    public void enqueue(T element) {
        inStack.push(element);
    }

    public T dequeue() {
        transferIfNeeded();
        if (outStack.isEmpty()) {
            throw new java.util.NoSuchElementException("Queue is empty");
        }
        return outStack.pop();
    }

    public T peek() {
        transferIfNeeded();
        if (outStack.isEmpty()) {
            throw new java.util.NoSuchElementException("Queue is empty");
        }
        return outStack.peek();
    }

    public boolean isEmpty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void transferIfNeeded() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }
}

How it works: Elements arrive into inStack in order [1, 2, 3] (3 on top). When you need to dequeue, transfer all elements to outStack, reversing the order to [3, 2, 1] (1 on top). Now outStack.pop() returns 1 — the oldest element. The transfer only happens when outStack is empty.

Amortized O(1) analysis: Each element is pushed once onto inStack, transferred once to outStack, and popped once from outStack — exactly 3 operations per element over its lifetime. The worst-case single dequeue can be O(n) (when transferring), but across n operations, the total work is O(n), giving O(1) amortized per operation.

This is a favorite interview question because the amortized analysis is non-obvious. Walk the interviewer through the per-element accounting to demonstrate deep understanding.

Classic Problem: BFS Level-Order Traversal

Breadth-first search (BFS) is the canonical queue application. For a binary tree, level-order traversal visits nodes level by level, left to right.

public sealed interface TreeNode permits TreeNode.Leaf, TreeNode.Branch {
    record Leaf(int val) implements TreeNode {}
    record Branch(int val, TreeNode left, TreeNode right) implements TreeNode {}
}

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<>();
    if (root == null) return levels;

    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> currentLevel = new ArrayList<>(levelSize);

        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();

            switch (node) {
                case TreeNode.Leaf(var val) -> currentLevel.add(val);
                case TreeNode.Branch(var val, var left, var right) -> {
                    currentLevel.add(val);
                    if (left != null) queue.offer(left);
                    if (right != null) queue.offer(right);
                }
            }
        }

        levels.add(currentLevel);
    }

    return levels;
}

The level boundary trick: Before processing each level, capture queue.size(). That number tells you exactly how many nodes belong to the current level. Process that many nodes, adding their children to the queue, and you have a clean level-by-level traversal.

Java 25’s sealed interface and pattern matching make the tree node handling explicit and type-safe. The compiler verifies that both Leaf and Branch cases are handled.

Complexity: O(n) time and O(w) space where w is the maximum width of the tree (the largest level). For a complete binary tree, the last level holds ~n/2 nodes.

Classic Problem: Sliding Window Maximum — Deque Approach

Problem: Given an array and a window size k, find the maximum element in each sliding window position.

Example: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 → [3, 3, 5, 5, 6, 7]

A monotonic deque stores indices in decreasing order of their values. The front of the deque always holds the index of the maximum in the current window:

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>(); // Stores indices

    for (int i = 0; i < n; i++) {
        // Remove indices outside the current window
        while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
            deque.pollFirst();
        }

        // Remove indices whose values are smaller than nums[i]
        // (they can never be the max while nums[i] exists in the window)
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
            deque.pollLast();
        }

        deque.offerLast(i);

        // Window is fully formed starting at i = k - 1
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }

    return result;
}

Why a deque and not a stack or queue? You need to remove from both ends: from the front (to evict elements that have left the window) and from the back (to maintain the decreasing order). Only a deque supports O(1) operations at both ends.

Complexity: O(n) time — each element enters and leaves the deque at most once. O(k) space for the deque.

This problem connects to the monotonic stack pattern from the previous chapter. The key difference: the sliding window constraint requires front removal, which a stack cannot provide.

Classic Problem: Task Scheduling with Cooldown

Problem: Given a list of tasks (represented by characters) and an integer n representing the cooldown interval, find the minimum number of intervals the CPU needs to complete all tasks. The same task must wait at least n intervals before executing again. During the cooldown, the CPU can execute different tasks or idle.

Example: tasks = ['A','A','A','B','B','B'], n = 2 → Output: 8 (e.g., A B _ A B _ A B)

This problem uses both a priority queue (to always pick the most frequent remaining task) and a regular queue (to track when cooled-down tasks become available again):

public int leastInterval(char[] tasks, int n) {
    // Count frequency of each task
    var freq = new int[26];
    for (char task : tasks) {
        freq[task - 'A']++;
    }

    // Max-heap ordered by remaining frequency
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    for (int f : freq) {
        if (f > 0) maxHeap.offer(f);
    }

    // Cooldown queue: pairs of (remaining count, time when available)
    record CooldownEntry(int remaining, int availableAt) {}
    Queue<CooldownEntry> cooldownQueue = new ArrayDeque<>();

    int time = 0;

    while (!maxHeap.isEmpty() || !cooldownQueue.isEmpty()) {
        time++;

        // Move tasks that have finished their cooldown back to the heap
        if (!cooldownQueue.isEmpty() && cooldownQueue.peek().availableAt() <= time) {
            maxHeap.offer(cooldownQueue.poll().remaining());
        }

        if (!maxHeap.isEmpty()) {
            int remaining = maxHeap.poll() - 1;
            if (remaining > 0) {
                cooldownQueue.offer(new CooldownEntry(remaining, time + n + 1));
            }
        }
        // If heap is empty and cooldown queue is non-empty, CPU idles (time still advances)
    }

    return time;
}

The strategy: At each time step, pick the task with the highest remaining frequency (greedy choice via max-heap). After executing, that task enters the cooldown queue with a timestamp marking when it becomes available again. This greedy approach minimizes idle time by always choosing the task that will cause the most constraints in the future.

The local record CooldownEntry bundles remaining count and availability time without needing a separate class file — a Java 25 convenience that keeps the code self-contained.

Complexity: O(n × m) time where n is total tasks and m is the number of distinct tasks (heap operations are O(log m)). O(m) space for the heap and cooldown queue.

When to Use Queue vs. Stack vs. Deque

Use Case	Structure
BFS / level-order traversal	Queue
DFS / backtracking	Stack
Sliding window problems	Deque
Task scheduling with ordering	Queue (+ priority queue)
Undo/redo functionality	Two stacks
Expression evaluation	Stack
”Find nearest X” for each element	Monotonic stack or deque
Fairness / first-come-first-served	Queue
Most recent first processing	Stack

When the problem does not clearly suggest one over the other, ask yourself: “Does the processing order matter? If so, which element should I process first?” FIFO → queue. LIFO → stack. Both ends → deque.

Edge Cases and Interviewer Tips

Edge cases to verify:

• Empty queue — Dequeue and peek should handle gracefully.
• Single element — All operations should work with exactly one item.
• Capacity-full circular queue — Enqueue should reject or resize.
• Window size equals array length — Sliding window maximum should return a single element.
• All tasks identical — Task scheduling becomes pure cooldown calculation.
• Cooldown of 0 — No idle time needed, total intervals equals total tasks.

Interviewer tips:

• For BFS problems, always capture queue.size() before the inner loop — this is the level boundary technique that interviewers expect.
• When asked “implement X using Y” (queue using stacks, stack using queues), the amortized analysis matters more than the implementation. Lead with the analysis.
• Mention ArrayDeque and explain why it is preferred over LinkedList for queue usage — it shows JDK maturity.
• For priority queue problems, clarify whether you need a min-heap or max-heap before coding. A wrong comparator wastes time debugging.
• If a problem involves processing by priority with a constraint (cooldown, dependency), the pattern is almost always priority queue + auxiliary queue.

Queues complete your toolkit of linear data structures. With arrays, linked lists, stacks, and queues mastered, you have the building blocks to tackle any data structure problem an interviewer presents. More importantly, you now understand why each structure exists — the memory trade-offs, the access patterns, the cache behavior — which lets you make informed choices rather than guessing. The structures in this part form the foundation for everything ahead: trees, graphs, hash maps, and the system design problems that tie them all together.