Types of Queue

A queue's variations exist because the plain array-based FIFO queue wastes memory or lacks flexibility, and each variant fixes one specific weakness by changing how the front/rear pointers move or how the next element to leave is chosen.

Recognize the pattern

• Need strict arrival order, but a naive array queue keeps "leaking" free slots at the front after dequeues → Circular Queue.
• Need insertion/removal at both ends (sliding window max/min, browser history, undo) → Deque.
• Need to process the most urgent item next, not the oldest → Priority Queue (heap-backed).

These three — Simple/Circular, Deque, Priority — are the canonical DSA queue variants (the ones CLRS and standard interview taxonomies test). You may also hear practitioners talk about an "affinity queue" in scheduler/systems design (grouping tasks by key/thread/tenant for cache locality); that is a scheduling concept built on top of a queue, not a distinct core ADT, so it will not show up as a named data structure in a DSA problem set.

Circular Queue: brute force → optimal

Brute force (linear queue on an array): dequeue removes index 0, then every remaining element is shifted left by one so front stays at index 0. Cost: O(n) per dequeue, and slots freed at the front are never reused unless you shift — usable capacity effectively shrinks as enqueue/dequeue cycles continue.

Optimal (circular queue): track front and rear indices and advance them with modulo arithmetic, idx = (idx + 1) % capacity, so the array wraps and freed slots are reused without shifting any data. Cost: O(1) per enqueue/dequeue.

Complexity, derived

Let capacity = n. Each enqueue performs a fixed number of steps: one full-check, one array write, one modulo increment of rear — independent of n, so O(1) time per enqueue and dequeue. The linear (non-wrapping) queue traced above needed to shift every remaining element on each dequeue, an O(n) operation — that O(n) cost is paid on every single dequeue, not amortized away, which is exactly what the circular queue's modulo trick eliminates.

Space is O(n) for the fixed backing array in both designs. The difference is not total memory but usable capacity: the linear queue's freed front slots (index 0, 1, ...) sit unreachable until a shift or a fresh array is allocated, while the circular queue's % capacity arithmetic makes every one of the n slots reusable indefinitely, as the traced example below shows.

Deque operations (push/pop front or rear) are also O(1) with a doubly linked list or a resizable circular array. Priority queue insert/extract-min on a binary heap of size n costs O(log n) time (sift up/down touches one path root-to-leaf, height = log n) and O(n) space.

Traced example: circular queue, capacity 5

Without wraparound, slot 0 would sit empty forever after the first dequeue even though the queue is logically not full. Note that the queue is full only once size == capacity (here, 5 elements at indices 0-4) — front and rear positions alone don't tell you full-vs-empty, which is why the code below tracks size explicitly.

Java: circular queue core

import java.util.NoSuchElementException;

class CircularQueue {
    private final int[] data;
    private int front = 0, rear = -1, size = 0;
    CircularQueue(int capacity) { data = new int[capacity]; }

    boolean enqueue(int val) {
        if (size == data.length) return false; // full
        rear = (rear + 1) % data.length;
        data[rear] = val;
        size++;
        return true;
    }

    int dequeue() {
        if (size == 0) throw new NoSuchElementException();
        int val = data[front];
        front = (front + 1) % data.length;
        size--;
        return val;
    }
}

Pitfalls

• Ambiguous full-vs-empty state: when front == rear it could mean empty or full. Fix by tracking an explicit size counter (as above) instead of relying only on pointer comparison.
• Forgetting the modulo on both front and rear advances causes silent out-of-bounds writes once the array wraps once.
• Using a plain ArrayDeque/linked-list deque but assuming O(1) random access — deques give O(1) at the ends only, not indexed access.
• Treating a priority queue as stable/FIFO among equal priorities — most heap implementations do not guarantee arrival order for ties.
• If you build a scheduler with key/thread/tenant grouping (an "affinity queue" in practitioner terms), remember it is a policy layered on a queue, not a queue variant with its own textbook complexity guarantees — and it can starve low-affinity or new groups unless you add an aging/starvation guard.

When to use / when not

Three quick recognition checks: sliding-window maximum specifically wants a monotonic deque of indices, not a plain FIFO queue; Dijkstra wants a priority queue (with decrease-key, or lazy deletion of stale entries); and an audio/network ring buffer is the circular queue's home turf because a fixed-capacity ring does zero allocation in steady state. If the problem is about reversal or nesting rather than arrival order, that's a stack — not a queue variant at all.

Takeaways

• Circular queue converts O(n) shifting into O(1) wraparound purely via modulo arithmetic on front/rear indices.
• Deque and priority queue trade strict FIFO order for flexibility (both ends, or priority) at different cost profiles: O(1) vs O(log n).
• Always disambiguate the empty/full collision at front == rear with an explicit size or a sentinel slot — full is defined by size == capacity, not by any single pair of pointer values.

Recall: A circular queue has capacity 5, and is currently full (size == 5) with front = 1 and rear = 0 (rear has wrapped around). After one dequeue frees a slot, what index does the next enqueue write to, and why?

Synthesized from the source notes on queue variations, standard CLRS/GeeksforGeeks treatment of circular buffers, and standard heap-based priority queue analysis.