#622 Design Circular Queue

frequently reported atApple Amazon Microsoft Meta

the problem

In plain words

Implement a fixed-capacity FIFO queue MyCircularQueue(k) with enQueue, deQueue (return true/false), Front, Rear (return -1 if empty), isEmpty and isFull, reusing the freed space at the front.

in k = 3; enQueue(1), enQueue(2), enQueue(3), enQueue(4), Rear(), isFull(), deQueue(), enQueue(4), Rear()

out true, true, true, false, 3, true, true, true, 4

The 4th enQueue fails (full). After one deQueue, 4 fits into the freed slot at index 0.

1 ≤ k ≤ 1000
0 ≤ value ≤ 1000
At most 3000 calls

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternStack & queue design

Store head and size. The rear index is (head + size − 1) % k and the next free slot is (head + size) % k — no separate tail needed, and no empty/full ambiguity.

solutions

From brute force to optimal

Append to the end; dequeue with remove(0).

enQueue: reject if size == k, else add.
deQueue: remove(0).
Front/Rear: first/last element or −1.

timedeQueue O(n), others O(1)

remove(0) shifts every remaining element left.

spaceO(k)

At most k elements stored.

javajava.util.*

1// On LeetCode, name this class MyCircularQueue.2class MyCircularQueueList {3    private final List<Integer> items = new ArrayList<>();4    private final int capacity;5 6    public MyCircularQueueList(int k) {7        capacity = k;8    }9 10    public boolean enQueue(int value) {11        if (items.size() == capacity) return false;12        items.add(value); // amortized O(1)13        return true;14    }15 16    public boolean deQueue() {17        if (items.isEmpty()) return false;18        items.remove(0); // shifts every other element left: O(n)19        return true;20    }21 22    public int Front() {23        return items.isEmpty() ? -1 : items.get(0);24    }25 26    public int Rear() {27        return items.isEmpty() ? -1 : items.get(items.size() - 1);28    }29 30    public boolean isEmpty() {31        return items.isEmpty();32    }33 34    public boolean isFull() {35        return items.size() == capacity;36    }37}

A ring buffer: indices wrap with % k; dequeue just moves head.

enQueue: if full return false; write at (head + size) % k; size++.
deQueue: if empty return false; head = (head + 1) % k; size--.
Front: data[head]; Rear: data[(head + size − 1) % k].

timeO(1) for every operation

Each call does a constant number of arithmetic steps; nothing shifts.

spaceO(k)

One array of capacity k.

javajava.util.*

1class MyCircularQueue {2    private final int[] data;3    private int head = 0; // index of the front element4    private int size = 0; // number of stored elements5 6    public MyCircularQueue(int k) {7        data = new int[k];8    }9 10    public boolean enQueue(int value) {11        if (isFull()) return false;12        int tail = (head + size) % data.length; // first free slot, wrapping around13        data[tail] = value;14        size++;15        return true;16    }17 18    public boolean deQueue() {19        if (isEmpty()) return false;20        head = (head + 1) % data.length; // just move head; no shifting21        size--;22        return true;23    }24 25    public int Front() {26        return isEmpty() ? -1 : data[head];27    }28 29    public int Rear() {30        return isEmpty() ? -1 : data[(head + size - 1) % data.length];31    }32 33    public boolean isEmpty() {34        return size == 0;35    }36 37    public boolean isFull() {38        return size == data.length;39    }40}

sim

Dry run

loading simulation…

javajava.util.*

1class MyCircularQueue {2    private final int[] data;3    private int head = 0; // index of the front element4    private int size = 0; // number of stored elements5 6    public MyCircularQueue(int k) {7        data = new int[k];8    }9 10    public boolean enQueue(int value) {11        if (isFull()) return false;12        int tail = (head + size) % data.length; // first free slot, wrapping around13        data[tail] = value;14        size++;15        return true;16    }17 18    public boolean deQueue() {19        if (isEmpty()) return false;20        head = (head + 1) % data.length; // just move head; no shifting21        size--;22        return true;23    }24 25    public int Front() {26        return isEmpty() ? -1 : data[head];27    }28 29    public int Rear() {30        return isEmpty() ? -1 : data[(head + size - 1) % data.length];31    }32 33    public boolean isEmpty() {34        return size == 0;35    }36 37    public boolean isFull() {38        return size == data.length;39    }40}

in the room

How to say it in the interview

talk track

Start by naming the empty-vs-full problem with only head and tail — then fix it with a size counter.
Write the two index formulas first; the methods are one-liners after that.
Test aloud with k = 1 and with a wrap at the last index.

traps

Rear computed as data[tail − 1] when tail is 0 → index −1.
Not checking empty before Front/Rear.

what they ask next

Follow-ups

Make it thread-safe?

Guard methods with a lock, or use ArrayBlockingQueue, which is exactly a bounded circular array with locks and conditions.

Without a size field?

Keep one slot always empty: empty when head == tail, full when (tail + 1) % k == head (allocate k + 1 slots).

before you submit

Edge cases to test

k = 1: the single slot is both front and rear; enQueue → deQueue → enQueue must reuse it.
Front and Rear on an empty queue return −1 — check size before reading the array.
Wrap-around: after a few deQueues the next free slot is index 0, and Rear must read across the wrap.

practise next