Design Circular Queue

MEDIUM✓ CHIP-TIMEDLC #622 — FULL STATEMENT ↗

The drill: Implement a fixed-size FIFO queue backed by a single array that reuses freed slots by wrapping the read and write positions around the ends — enqueue, dequeue, peek both ends, and report empty or full.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

This drill builds a fixed-capacity queue on top of a single array, one that behaves strictly first-in-first-out while reusing slots the moment they free up instead of leaving them stranded at the front.

Five operations sit on the interface: enQueue adds a value at the back when room exists, deQueue removes the front value when the queue isn't empty, Front and Rear peek at either end without removing anything, and isEmpty / isFull report the queue's current state.

The array itself never grows or shrinks — freed slots at the front get reused by later enqueues, which means the logical front and back wrap around the physical ends of the array rather than marching off it.

EX 01

MyCircularQueue(3)

enQueue(1) → true

enQueue(2) → true

enQueue(3) → true

enQueue(4) → false

Rear() → 3

isFull() → true

deQueue() → true

enQueue(4) → true

Rear() → 4

FILL TO CAPACITY, OVERFLOW REJECTED, THEN WRAP AFTER A DEQUEUE

EX 02

MyCircularQueue(1)

isEmpty() → true

enQueue(5) → true

isFull() → true

Front() → 5

Rear() → 5

deQueue() → true

isEmpty() → true

deQueue() → false

CAPACITY ONE

EX 03

MyCircularQueue(2)

Front() → -1

Rear() → -1

enQueue(10) → true

Front() → 10

Rear() → 10

enQueue(20) → true

Front() → 10

Rear() → 20

deQueue() → true

Front() → -1

Rear() → -1

FRONT/REAR ON AN EMPTY QUEUE RETURN -1

capacity is fixed once at construction and never changes
enQueue fails cleanly once the queue is full, deQueue fails cleanly once it's empty
values are plain integers with no special range
every operation is expected to run in constant time

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A normal array-backed queue either shifts every remaining element on dequeue or wastes the slots at the front forever. What if the front and back positions were allowed to walk off the end and land back at index 0?

HINT 2 THE STRUCTURE

Two indices are enough — where the next enqueue writes, and where the next dequeue reads — as long as both wrap using modulo the capacity instead of stopping at the array's end.

HINT 3 ONE STEP FROM THE ANSWER

Track the current size alongside a head index; write new values at (head + size) % capacity, advance head by one (mod capacity) on dequeue, and let size alone decide full versus empty so a full buffer is never confused with an empty one.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE WRAP-AROUND BUFFERPATTERN · CIRCULAR INDEX BUFFERcapacity 3 · enQ 1,2,3,4 · Rear · isFull · deQ · enQ 4 · Rear

new(3)

enQ 1

enQ 2

enQ 3

enQ 4

Rear

isFull

deQ

enQ 4

Rear

BUFFER — head / count / slots

head → 0

count → 0

buf → [_,_,_]

STEP 1

Capacity-3 circular buffer created — head 0, count 0, three empty slots waiting to wrap.

STEP 1 / 11 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/design-circular-queue.py — RACE PACE

LANG ▸

PACE ▸

class MyCircularQueue:
    def __init__(self, k: int):
        self.capacity = k
        self.buf = [0] * k
        self.head = 0
        self.count = 0

    def enQueue(self, value: int) -> bool:
        if self.count == self.capacity:
            return False
        tail = (self.head + self.count) % self.capacity
        self.buf[tail] = value
        self.count += 1
        return True

    def deQueue(self) -> bool:
        if self.count == 0:
            return False
        self.head = (self.head + 1) % self.capacity
        self.count -= 1
        return True

    def Front(self) -> int:
        return self.buf[self.head] if self.count else -1

    def Rear(self) -> int:
        return self.buf[(self.head + self.count - 1) % self.capacity] if self.count else -1

    def isEmpty(self) -> bool:
        return self.count == 0

    def isFull(self) -> bool:
        return self.count == self.capacity

TIME O(1) ALL OPSSPACE O(K)PYTHON · RACE PACE · 33 LN

class MyCircularQueue:
    def __init__(self, k: int):
        self.capacity = k
        self.data = []

    def enQueue(self, value: int) -> bool:
        if len(self.data) == self.capacity:
            return False
        self.data.append(value)
        return True

    def deQueue(self) -> bool:
        if not self.data:
            return False
        self.data.pop(0)
        return True

    def Front(self) -> int:
        return self.data[0] if self.data else -1

    def Rear(self) -> int:
        return self.data[-1] if self.data else -1

    def isEmpty(self) -> bool:
        return len(self.data) == 0

    def isFull(self) -> bool:
        return len(self.data) == self.capacity

TIME O(N) DEQUEUESPACE O(K)PYTHON · TRAINING PACE · 28 LN

class MyCircularQueue {
    private final int[] buf;
    private final int capacity;
    private int head = 0;
    private int count = 0;

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

    public boolean enQueue(int value) {
        if (count == capacity) return false;
        int tail = (head + count) % capacity;
        buf[tail] = value;
        count++;
        return true;
    }

    public boolean deQueue() {
        if (count == 0) return false;
        head = (head + 1) % capacity;
        count--;
        return true;
    }

    public int Front() {
        return count == 0 ? -1 : buf[head];
    }

    public int Rear() {
        return count == 0 ? -1 : buf[(head + count - 1) % capacity];
    }

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

    public boolean isFull() {
        return count == capacity;
    }
}

TIME O(1) ALL OPSSPACE O(K)JAVA · RACE PACE · 42 LN

class MyCircularQueue {
    private final List<Integer> data = new ArrayList<>();
    private final int capacity;

    public MyCircularQueue(int k) {
        capacity = k;
    }

    public boolean enQueue(int value) {
        if (data.size() == capacity) return false;
        data.add(value);
        return true;
    }

    public boolean deQueue() {
        if (data.isEmpty()) return false;
        data.remove(0);
        return true;
    }

    public int Front() {
        return data.isEmpty() ? -1 : data.get(0);
    }

    public int Rear() {
        return data.isEmpty() ? -1 : data.get(data.size() - 1);
    }

    public boolean isEmpty() {
        return data.isEmpty();
    }

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

TIME O(N) DEQUEUESPACE O(K)JAVA · TRAINING PACE · 36 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED