Implement a Circular queue

The problem, simply

Build a queue that holds at most k values, using one array of size k. You need:

• enQueue(x): add at the back. Return false if full.
• deQueue(): remove from the front. Return false if empty.
• Front() and Rear(): the values at each end, or -1 if empty.
• isEmpty() and isFull().

Every action must be O(1), and a box freed at the front must be usable again.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep the line packed at the start of the array. The front is always box 0. When the front leaves, shift everyone one box left.

1. enQueue: write at arr[size] and add one to size.
2. deQueue: move arr[1..size-1] one step left, take one from size.
3. Front is arr[0], Rear is arr[size - 1].

class ShiftingQueue {
    private final int[] arr;
    private int size = 0;

    ShiftingQueue(int k) { arr = new int[k]; }

    public boolean enQueue(int x) {
        if (isFull()) return false;
        arr[size++] = x;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) return false;
        for (int i = 1; i < size; i++) arr[i - 1] = arr[i];   // everyone steps left
        size--;
        return true;
    }

    public int Front() { return isEmpty() ? -1 : arr[0]; }

    public int Rear() { return isEmpty() ? -1 : arr[size - 1]; }

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

    public boolean isFull() { return size == arr.length; }
}

How long it takes: deQueue shifts up to k - 1 values, O(k). The rest is O(1). Extra room: the array, O(k).

Way 2: the clever way

Do not move the values. Move two pointers and let them wrap around with % k.

1. Keep front (the oldest value), rear (the newest value) and count. Start with front = 0, rear = -1, count = 0.
2. enQueue(x): if count == k, return false. Else rear = (rear + 1) % k, write arr[rear] = x, add one to count.
3. deQueue(): if count == 0, return false. Else front = (front + 1) % k, take one from count.
4. Front() is arr[front], Rear() is arr[rear]. Empty is count == 0, full is count == k.

The % k is what bends the row into a circle: after box k - 1 comes box 0.

class MyCircularQueue {
    private final int[] arr;
    private int front = 0, rear = -1, count = 0;

    public MyCircularQueue(int k) { arr = new int[k]; }

    public boolean enQueue(int x) {
        if (isFull()) return false;
        rear = (rear + 1) % arr.length;     // step forward, wrap at the end
        arr[rear] = x;
        count++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) return false;
        front = (front + 1) % arr.length;   // the oldest leaves
        count--;
        return true;
    }

    public int Front() { return isEmpty() ? -1 : arr[front]; }

    public int Rear() { return isEmpty() ? -1 : arr[rear]; }

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

    public boolean isFull() { return count == arr.length; }
}

How long it takes: every action moves one pointer and changes the count, O(1). Extra room: the array of k boxes, O(k).

Watch out for

• Write (rear + 1) % k, not rear + 1 % k. The % binds tighter than +.
• Rear() must read arr[rear], not arr[rear - 1] and not arr[(front + count) % k], which is the next free box.
• If you compute rear from front, use (front + count - 1) % k. With front = 0 and count = 0 that is -1 % k, which is negative in Java, so guard the empty case.
• The old value stays in the array after deQueue. That is fine, it will be written over.

What interviewers ask next

• Can you drop the count? Yes. Either keep one box empty, or keep front and size only and compute rear = (front + size - 1) % k.
• Make it grow. When full, make an array twice as big and copy the values in queue order starting at index 0. That is how ArrayDeque works.
• A circular deque, with adding and removing at both ends. Moving front backward is (front - 1 + k) % k; add k before % to avoid negatives.
• Make it safe for two threads, one adding and one removing. A ring buffer with one writer and one reader can work without locks, using only the two indices. That is common in audio, logging and network drivers.
• Why is it called a ring buffer? The array is used as if its two ends were joined into a ring.

Remember this

Grown-up words: the merry-go-round is a circular queue or ring buffer, the two fingers are the front and rear indices, wrapping around is modulo arithmetic, and sliding everyone forward in Way 1 is an O(n) shift.