Introduction to Queues

Mechanism

A queue enforces First-In-First-Out (FIFO) ordering by restricting mutation to two ends: insertion (enqueue) only happens at the rear, removal (dequeue) only happens at the front. Because every element must travel the full length of the structure before exiting, the relative arrival order is preserved exactly — the data structure's shape (two disjoint access points) is what *forces* fairness, not a sorting step.

Recognize the pattern

• The problem talks about order of arrival, fairness, or "process in the order requests came in."
• You need to process nodes level-by-level (BFS) or handle requests/jobs in submission order.
• You need a buffer where a producer writes and a consumer reads independently (task queues, IO buffers, print spoolers).
• Keywords: "first come first served," "level order," "sliding window of recent items," "scheduler."

Brute force vs optimal backing store

A naive queue built on a plain array with enqueue appending at the end and dequeue removing index 0 costs O(1) for enqueue but O(n) for dequeue, because every remaining element must shift left one slot to close the gap. For n dequeues that is Σ_k=0..n−1 k = n(n−1)/2 = Θ(n²) total — unacceptable for a queue meant to service many requests.

The optimal approach never shifts elements. Two designs achieve O(1) for both ends:

• Circular (ring) array: front and rear are indices that wrap around with modulo arithmetic, so the same fixed array is reused without shifting.
• Doubly linked list: keep head and tail pointers; enqueue attaches a new tail node, dequeue detaches the head node — pure pointer rewiring, no traversal.

Complexity, derived

Circular array: enqueue writes arr[rear] then sets rear = (rear+1) % capacity — a fixed, constant number of arithmetic operations regardless of how many elements are already stored, so O(1) time. dequeue reads arr[front] then front = (front+1) % capacity — likewise O(1), independent of n. No element is ever touched more than twice (once in, once out) across its lifetime, so n operations cost O(n) total, not O(n²). Space is O(c) where c is the fixed capacity — allocated once, reused forever (amortized O(1) extra space per element, zero if the array is pre-sized).

Linked list: same O(1) per operation because head/tail are held by reference, but each node carries a pointer-sized overhead, so space is O(n) with a larger constant than the array version, and it grows/shrinks dynamically instead of needing a pre-declared capacity.

Traced example

Capacity 4 circular array, initially empty, front=0, rear=0, size=0. The Array state column is the literal contents of data[0..3] by physical index (not logical front-to-rear reading order) — this matters because enqueue always writes data[rear] first and increments rear second.

After enqueue(40), rear (0) physically sits before front (1) in array index order — this is what wraparound looks like once rear laps back to the low end of the array while front is still ahead of it. And after the final enqueue(50), front=1 and rear=1 are equal — the exact same index relationship as the initial empty state (front=0, rear=0). Comparing indices alone can't tell you the queue is full versus empty; only the separate size field can.

Java: circular array queue

public class CircularQueue<T> {
    private final Object[] data;
    private int front = 0, rear = 0, size = 0;

    public CircularQueue(int capacity) { data = new Object[capacity]; }

    public void enqueue(T val) {
        if (size == data.length) throw new IllegalStateException("queue full");
        data[rear] = val;
        rear = (rear + 1) % data.length;
        size++;
    }

    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (size == 0) throw new IllegalStateException("queue empty");
        T val = (T) data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size--;
        return val;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        if (size == 0) throw new IllegalStateException("queue empty");
        return (T) data[front];
    }

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

Pitfalls

• Naive array shifting: implementing dequeue as remove(0) on an ArrayList/array silently degrades every dequeue to O(n).
• Ambiguous full-vs-empty state: the traced example above shows it directly — the empty starting state (front=0, rear=0) and the full ending state (front=1, rear=1) are both cases of front == rear, indistinguishable by index alone. CircularQueue above sidesteps the whole problem: it never compares front to rear at all, checking size == 0 or size == data.length instead. The class doesn't expose a standalone isFull(), but if you wanted one it would just reuse the same field — boolean isFull() { return size == data.length; } — rather than reintroducing the index-comparison trap.
• Fixed capacity surprises: a circular array queue throws or silently drops on overflow unless you add resize logic (allocate 2x, copy front→rear order back into index 0).
• java.util.Queue via LinkedList autoboxing: fine for correctness, but boxing primitives adds real overhead in hot loops — prefer ArrayDeque in Java, which is array-backed and avoids per-node allocation.

When to use / when not — trade-offs

Use a queue whenever fairness (arrival order) matters: BFS traversal, task/job schedulers, rate limiters, producer-consumer buffers, print/message queues. Do not use a queue when you need most-recent-first access (use a stack — LIFO — for backtracking, undo history, DFS) or when you need access/removal from both ends (use a deque, which generalizes both stack and queue and is what most languages recommend by default, e.g. Java's ArrayDeque). A plain queue also cannot efficiently support priority-based processing — for "most urgent first" semantics use a priority queue (heap-backed, O(log n) insert/extract) instead.

Takeaways

• FIFO is enforced by the shape of the structure — two separate access points — not by a sort.
• Naive array queues are O(n) per dequeue due to shifting; circular arrays or linked lists give true O(1).
• rear always points at the next empty slot to write, not at the last element inserted.
• Full vs. empty ambiguity in circular arrays (front==rear means either) requires a size counter or a sacrificed slot — the traced example's empty-start and full-end states prove it.
• Choose stack for LIFO/backtracking, deque for both-ends access, priority queue for urgency-based ordering.

Recall: Why does a circular array queue need either a size field or a wasted slot to distinguish full from empty, when front == rear in both cases?

Synthesized from standard CS curricula on linear data structures (queue FIFO semantics, circular buffer implementation) and general algorithms references (CLRS-style complexity analysis of amortized O(1) queue operations).