Problem 10.4 · Queue, Deque and Monotonic QueueMedium

Design Circular Queue

What it teaches: A fixed array with a head index and a size, wrapping with modulo: the structure inside ArrayDeque and ring buffers.

Practise it on judges as “Design Circular Queue”.

The problem

Implement MyCircularQueue(k) with enQueue(value) and deQueue() (return true on success), Front() and Rear() (return −1 if empty), isEmpty() and isFull().

Example 1

Input: ops = [MyCircularQueue, enQueue, enQueue, enQueue, enQueue, Rear, isFull, deQueue, enQueue, Rear]
args = [[3], [1], [2], [3], [4], [], [], [], [4], []]
Output: [null, true, true, true, false, 3, true, true, true, 4]

Constraints

1 ≤ k ≤ 1000
0 ≤ value ≤ 1000

Pattern clues in the wording

→ Fixed capacity, FIFO
→ O(1) operations without shifting

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

MyCircularQueue.java · starter

class MyCircularQueue {
    public MyCircularQueue(int k) {}
    public boolean enQueue(int value) { return false; }
    public boolean deQueue() { return false; }
    public int Front() { return -1; }
    public int Rear() { return -1; }
    public boolean isEmpty() { return true; }
    public boolean isFull() { return false; }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	ops = ["MyCircularQueue","enQueue","enQueue","enQueue","enQueue","Rear","isFull","deQueue","enQueue","Rear"] args = [[3],[1],[2],[3],[4],[],[],[],[4],[]]	[null,true,true,true,false,3,true,true,true,4]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: array + head + size · O(1) per operation

Optimal: array + head + size

Time O(1) per operation Space O(k)

enQueue writes at (head + size) % k; deQueue moves head forward modulo k. size tells full from empty.

Approach 1

class MyCircularQueue {
    private final int[] data;
    private int head = 0, size = 0;

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

    public boolean enQueue(int value) {
        if (isFull()) return false;
        data[(head + size) % data.length] = value;
        size++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % data.length;
        size--;
        return true;
    }

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

    public int Rear() { return isEmpty() ? -1 : data[(head + size - 1) % data.length]; }

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

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

Verdict: Simple and constant time.

Before you submit

Edge cases and common mistakes

Test these inputs

Capacity 1
Wrapping several times
Front/Rear on an empty queue

Mistakes people make

Computing the rear as (head + size) % k (that's the next free slot).
Forgetting modulo after incrementing head.

Interview

Follow-up questions

How would you make it thread-safe for one producer and one consumer?

Command Palette

The problem

Approaches

Optimal: array + head + size

Edge cases and common mistakes

Follow-up questions