Diving Deeper – Circular Queues and Deques

A circular queue reuses freed array slots by treating the underlying array as a ring: front and rear pointers advance with modulo arithmetic (i+1) % capacity instead of stopping at the array's end, so a slot vacated by a dequeue at index 0 can be reused by an enqueue that wraps around from index n-1. A deque generalizes this ring further by allowing insertion and removal at both ends.

Recognize the pattern

• You need a fixed-capacity FIFO buffer that must reuse space after dequeues without shifting elements — e.g. producer-consumer ring buffers, CPU task schedulers, streaming windows.
• Phrases like "sliding window maximum", "circular buffer", "bounded history", or "insert/remove from both front and back" signal circular queue / deque. (Note: sliding-window max specifically needs a monotonic deque — pop from the back while smaller, expire from the front — a plain FIFO circular queue is not enough.)
• The queue's maximum size is known up front and it is array-backed rather than a growable linked structure.

Brute force → optimal

Brute force (plain array queue): keep a flat array; on every dequeue shift all remaining elements one slot left so index 0 is always the front. Enqueue is O(1) (append at the end), but each dequeue costs O(n) for the shift — n dequeues cost O(n²) total, and once rear hits the array end you falsely report overflow even with free space at the front.

Optimal (circular queue): track front, rear, and a size counter; advance both indices with modulo capacity. No element is ever shifted, so both operations are O(1) no matter how many times the pointers have wrapped.

Complexity, derived

Each enqueue performs a constant number of primitive steps: one full/empty check, one array write at arr[rear], one modulo-increment rear = (rear+1) % capacity, one increment of size. None of these steps depend on capacity or on how many elements are currently stored, so enqueue and dequeue are both O(1) time, worst case and amortized — contrast with the O(n) shift in the naive array queue. Deque operations (addFront, removeRear) add one modulo-decrement variant but are still O(1) each. Space is O(capacity) — one fixed array allocated up front, plus three O(1) integer pointers; no per-operation extra allocation, unlike a linked-list queue which pays a node allocation per enqueue.

Traced example: capacity 5

Start empty: front=0, rear=-1, size=0, array slots [_,_,_,_,_]. This code's convention is rear = index of the last occupied slot (not "next free slot"), which is why it starts at -1 rather than 0.

The last enqueue computes rear = (4+1) % 5 = 0 and writes 60 into the slot vacated earlier by 10 — the wrap-around reuse that makes this a circular queue. After this step front=1 (the real front, holding 20 at index 1) and rear=0 (holding the most recently written 60 at index 0); both index 0 and index 1 hold real, occupied values — there is no free slot among them. The queue is now full (size == capacity == 5). Notice that (rear+1) % capacity = (0+1) % 5 = 1 = front: this is exactly the ambiguous condition for this convention (rear = last occupied slot). The same equation, (rear+1) % capacity == front, also held back at the very start (front=0, rear=-1: (-1+1)%5=0). Structurally the two states look identical from front/rear alone — only the separate size counter (0 vs. 5) tells them apart.

Java implementation

class CircularQueue {
    private final int[] arr;
    private int front = 0, rear = -1, size = 0;
    private final int capacity;

    CircularQueue(int capacity) {
        this.capacity = capacity;
        this.arr = new int[capacity];
    }

    boolean enqueue(int val) {
        if (size == capacity) return false; // overflow
        rear = (rear + 1) % capacity;
        arr[rear] = val;
        size++;
        return true;
    }

    int dequeue() {
        if (size == 0) throw new RuntimeException("underflow");
        int val = arr[front];
        front = (front + 1) % capacity;
        size--;
        return val;
    }

    int peekFront() {
        if (size == 0) throw new RuntimeException("empty");
        return arr[front];
    }

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

A deque adds mirror operations at the rear end using modulo subtraction (add capacity before the mod to avoid negative results in Java):

void addFront(int val) {
    if (size == capacity) throw new RuntimeException("overflow");
    front = (front - 1 + capacity) % capacity;
    arr[front] = val;
    size++;
}

int removeRear() {
    if (size == 0) throw new RuntimeException("underflow");
    int val = arr[rear];
    rear = (rear - 1 + capacity) % capacity;
    size--;
    return val;
}

Pitfalls

• Full vs. empty ambiguity, matched to your convention: the exact check depends on what rear means. In the convention used above — rear is the index of the last occupied slot, initialized to -1 — both empty and full states satisfy (rear+1) % capacity == front (verify: at start front=0, rear=-1 gives 0==0; after filling capacity 5 above, front=1, rear=0 gives 1==1). In the alternate convention where rear is the index of the next free slot, it's plain front == rear that is ambiguous instead. Either way, without a separate size counter (or sacrificing one slot as a sentinel) you cannot tell the two states apart from the pointers alone — always check which convention your code actually uses before applying either rule.
• Forgetting the +capacity before mod when decrementing in Java/C++: (front - 1) % capacity can return a negative index and throw ArrayIndexOutOfBoundsException.
• Confusing rear's meaning: some implementations store rear as "next free slot", others as "last occupied slot" (as used above, starting at -1) — mixing conventions mid-implementation causes off-by-one bugs and breaks whichever full/empty check you rely on.
• Resizing a circular array is trickier than a normal array: elements must be copied out starting from front in logical order, not raw index order, or the sequence gets scrambled.

When to use / when not

Use a circular queue when capacity is bounded and known ahead of time and you need guaranteed O(1) enqueue/dequeue with zero per-operation allocation — ring buffers in networking stacks, audio/video streaming buffers, round-robin CPU schedulers. Use a deque when you need push/pop at both ends, e.g. implementing a sliding-window maximum or an LRU-adjacent structure.

Trade-off vs. a linked-list queue: a linked list needs no fixed capacity and never "overflows" (until memory runs out), but pays a heap allocation per node and worse cache locality; the circular array queue is faster and cache-friendly but must reject or resize on overflow. Trade-off vs. java.util.ArrayDeque: in production Java code, prefer ArrayDeque (it already implements circular-array doubling internally) — hand-rolling one is for interview/learning purposes or when a hard capacity cap is a functional requirement, not just an optimization.

Takeaways

• Modulo arithmetic on front/rear indices is what turns a linear array into a reusable ring — no shifting, ever.
• A separate size counter (or sacrificing one slot) is mandatory to disambiguate full from empty — and the exact ambiguous pointer equation depends on whether rear means "last occupied slot" or "next free slot".
• Deques are circular queues with both ends exposed; the extra operations just add a mirrored, subtraction-based modulo step.
• In real Java code, reach for ArrayDeque unless a hard, fixed capacity is an actual requirement.

Recall: In a circular queue of capacity 5 currently holding elements at indices 3 and 4 (front=3, rear=4, size=2), what are the new values of front, rear, and size after one dequeue followed by one enqueue?

Adapted and expanded from the original "Diving Deeper – Circular Queues and Deques" module, with added derivations, a traced example, an SVG diagram, and Java implementations for interview-prep depth.