Queue

A queue is a linear data structure that follows the FIFO principle — First In, First Out. Whoever joined first gets served first, exactly like a real-world line at a ticket counter. Elements are added at the rear and removed from the front. Queues show up everywhere: task scheduling, BFS traversal, request buffering, print spoolers — any situation where order of arrival must be preserved.

The Array-Based Queue's Shifting Problem

The naive way to build a queue from an array is to append at the end for enqueue, and remove from index 0 for dequeue. The catch: removing index 0 means every remaining element has to shift one position to the left so the front is index 0 again.

public class SimpleQueue {
    private int[] data;
    private int size;

    public SimpleQueue(int capacity) {
        data = new int[capacity];
        size = 0;
    }

    public void enqueue(int value) {
        if (size == data.length) {
            throw new RuntimeException("Queue is full");
        }
        data[size++] = value;
    }

    public int dequeue() {
        if (size == 0) {
            throw new RuntimeException("Queue is empty");
        }
        int front = data[0];
        for (int i = 1; i < size; i++) {
            data[i - 1] = data[i];   // shift every remaining element left
        }
        size--;
        return front;
    }
}

Time complexity: enqueue is O(1), but dequeue is O(n) because of the left-shift over all remaining elements. Space complexity: O(n) for the backing array.

Circular Queue: Fixing It With Modulo

A circular queue tracks separate front and rear indices instead of always resetting to 0. Both indices wrap around using the modulo operator, so the "logical" array bends into a circle — when rear falls off the end of the backing array, it wraps back to index 0 and reuses the slots that earlier dequeues freed up.

public class CircularQueue {
    private int[] data;
    private int front;
    private int rear;
    private int size;
    private final int capacity;

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        data = new int[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }

    public void enqueue(int value) {
        if (size == capacity) {
            throw new RuntimeException("Queue is full");
        }
        rear = (rear + 1) % capacity;   // wrap around when rear hits the end
        data[rear] = value;
        size++;
    }

    public int dequeue() {
        if (size == 0) {
            throw new RuntimeException("Queue is empty");
        }
        int value = data[front];
        front = (front + 1) % capacity;  // wrap the front too
        size--;
        return value;
    }

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

Trace with capacity 4: enqueue three values -> front=0, rear=2, size=3. Dequeue twice -> front advances to 2, size=1. Enqueue two more -> rear wraps from 3 to (3+1)%4=0, reusing the two slots that were freed by the dequeues — no shifting, no wasted space.

Time complexity: O(1) for both enqueue and dequeue — only index arithmetic, no scanning. Space complexity: O(n) for a fixed-capacity backing array of size n.

Deque: A Queue and Stack Hybrid

A Deque ("deck", double-ended queue) allows O(1) insertion and removal at both ends. That means it can act as a stack (push/pop from one end only, as covered in the previous lesson) or as a queue (insert at the rear with offer, remove from the front with poll) — the same object, used two different ways.

Deque<Integer> queue = new ArrayDeque<>();

queue.offer(1);   // add at rear
queue.offer(2);
queue.offer(3);

System.out.println(queue.poll());  // 1 — removed from the front, FIFO order
System.out.println(queue.peek());  // 2 — next in line

Time complexity: O(1) for offer, poll, and peek. Space complexity: O(n) for n elements.

ArrayDeque: The Standard Implementation

java.util.ArrayDeque is Java's recommended general-purpose implementation of Deque, and by extension the recommended queue implementation too. It's backed by a resizable circular array — the exact circular-buffer idea worked out above, production hardened. Compared to using a LinkedList as a queue, ArrayDeque avoids a per-element node allocation and has better cache locality, since its elements sit contiguously in memory instead of scattered across heap-allocated nodes.

Worked Problem: Queue Using Two Stacks

A common interview exercise: build a FIFO queue using only stack operations (push/pop). The trick is to keep two stacks — one for incoming elements, one for outgoing. Enqueue always pushes onto inStack. Dequeue pops from outStack; if it's empty, first drain all of inStack into it, which reverses the order back to FIFO (the oldest element, pushed first into inStack, ends up on top of outStack).

public class QueueUsingStacks {
    private Deque<Integer> inStack = new ArrayDeque<>();
    private Deque<Integer> outStack = new ArrayDeque<>();

    public void enqueue(int value) {
        inStack.push(value);
    }

    public int dequeue() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());   // reverses the order back to FIFO
            }
        }
        if (outStack.isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return outStack.pop();
    }
}

Trace: enqueue 1, 2, 3 -> inStack (top to bottom) is [3, 2, 1]. First dequeue: outStack is empty, so drain inStack into it -> outStack (top to bottom) becomes [1, 2, 3]. Pop returns 1 — correct FIFO order. Further dequeues pop 2, then 3 directly from outStack with no re-draining needed.

Time complexity: O(1) for enqueue always. For dequeue, each element is moved from inStack to outStack exactly once over its lifetime, so the cost of draining is amortized O(1) per dequeue, even though a single call that triggers a drain costs O(n) in the worst case. Space complexity: O(n) across both stacks.