LeetCode · #622

Design Circular Queue Solution

Design a fixed-size queue that supports O(1) front/rear access and wraparound insertion and deletion without shifting elements.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #622

🏗️

Pattern

Design — ring buffer with modulo arithmetic

Implement a class MyCircularQueue with capacity k. The queue must support enQueue, deQueue, Front, Rear, isEmpty, and isFull. The challenge is distinguishing full from empty while reusing array slots after deletions.

Example

 Input: MyCircularQueue q = new MyCircularQueue(3)
q.enQueue(1) // true
q.enQueue(2) // true
q.enQueue(3) // true
q.enQueue(4) // false — full
q.Rear() // 3
q.isFull() // true
q.deQueue() // true
q.enQueue(4) // true — wraps into freed slot
q.Rear() // 4 

Constraints

 • 1 ≤ k ≤ 1000 • 0 ≤ value ≤ 1000 • At most 3000 calls are made to enQueue, deQueue, Front, Rear, isEmpty, and isFull 

Section Two · Brute Force

Shifting Array Queue — O(n) deQueue

Store elements from index 0 to size - 1. enQueue writes at the end, but deQueue shifts every remaining element one step left. This satisfies the interface, but it throws away the entire point of a circular queue.

Why it works

Because the logical front is always kept at index 0, Front() and Rear() are trivial. Capacity checks also become easy: full means size == k, empty means size == 0.

Why we can do better

Problem: Shifting makes every deletion O(n). The whole design problem exists to avoid moving data. A ring buffer keeps elements in place and moves only the metadata: head and size.

Java — shifting array

 class MyCircularQueue {
private final int[] data;
private int size = 0;
public MyCircularQueue(int k) {
        data = new int[k];
    }
public boolean enQueue(int value) {
if (isFull()) return false;
        data[size++] = value;
return true;
    }
public boolean deQueue() {
if (isEmpty()) return false;
for (int i = 1; i < size; i++)
            data[i - 1] = data[i];
        size--;
return true;
    }
public int Front() { return isEmpty() ? -1 : data[0]; }
public int Rear()  { return isEmpty() ? -1 : data[size - 1]; }
public boolean isEmpty() { return size == 0; }
public boolean isFull()  { return size == data.length; }
}

Python — shifting array

 class MyCircularQueue:
def __init__(self, k: int):
        self.data = [0] * k
        self.size = 0 def enQueue(self, value: int) -> bool:
if self.isFull():
return False
self.data[self.size] = value
        self.size += 1 return True def deQueue(self) -> bool:
if self.isEmpty():
return False for i in range(1, self.size):
            self.data[i - 1] = self.data[i]
        self.size -= 1 return True def Front(self) -> int:
return -1 if self.isEmpty() else self.data[0]
def Rear(self) -> int:
return -1 if self.isEmpty() else self.data[self.size - 1]
def isEmpty(self) -> bool:
return self.size == 0 def isFull(self) -> bool:
return self.size == len(self.data)

Metric	Value
Time	O(n) for `deQueue`, O(1) for the other methods
Space	O(k)

Section Three · Optimal

Ring Buffer with Head + Size — O(1)

Keep the array fixed. Instead of moving elements, track where the logical front starts and how many items are currently stored. The next enqueue position is (head + size) % capacity. The rear element lives at (head + size - 1 + capacity) % capacity.

💡 Mental model: Picture numbered seats around a merry-go-round. Riders do not physically slide when the front rider gets off. You simply move the “front” sticker to the next seat. When a new rider boards, they take the seat immediately after the current rear, wrapping around to seat 0 when needed.

Algorithm — constant-time wraparound

State: store data[], head, size, and capacity.
enQueue(value): if full, return false; otherwise write to (head + size) % capacity and increment size.
deQueue(): if empty, return false; otherwise move head = (head + 1) % capacity and decrement size.
Front(): return data[head] when not empty.
Rear(): compute the logical last index with modulo normalization.

🎯 When to recognize this pattern:

Fixed capacity plus repeated front deletions is the giveaway.
If an interface says “bounded queue,” “wrap around,” or “reuse freed slots,” you want a ring buffer instead of shifting elements or allocating linked nodes.

Why keep size?:

Without extra state, head == tail is ambiguous — it can mean either empty or full.
Tracking size removes that ambiguity cleanly and keeps every method O(1).

Section Four · Walkthrough

Visual Walkthrough

Circular Queue — head stays logical, writes wrap physically

Section Five · Code

Code — Java & Python

Java — ring buffer

 class MyCircularQueue {
private final int[] data;
private final int capacity;
private int head = 0;
private int size = 0;
public MyCircularQueue(int k) {
        data = new int[k];
        capacity = k;
    }
public boolean enQueue(int value) {
if (isFull()) return false;
int tail = (head + size) % capacity;
        data[tail] = value;
        size++;
return true;
    }
public boolean deQueue() {
if (isEmpty()) return false;
        head = (head + 1) % capacity;
        size--;
return true;
    }
public int Front() {
return isEmpty() ? -1 : data[head];
    }
public int Rear() {
if (isEmpty()) return -1;
int tail = (head + size - 1 + capacity) % capacity;
return data[tail];
    }
public boolean isEmpty() {
return size == 0;
    }
public boolean isFull() {
return size == capacity;
    }
}

Python — ring buffer

 class MyCircularQueue:
def __init__(self, k: int):
        self.data = [0] * k
        self.capacity = k
        self.head = 0
self.size = 0 def enQueue(self, value: int) -> bool:
if self.isFull():
return False
tail = (self.head + self.size) % self.capacity
        self.data[tail] = value
        self.size += 1 return True def deQueue(self) -> bool:
if self.isEmpty():
return False
self.head = (self.head + 1) % self.capacity
        self.size -= 1 return True def Front(self) -> int:
return -1 if self.isEmpty() else self.data[self.head]
def Rear(self) -> int:
if self.isEmpty():
return -1
tail = (self.head + self.size - 1) % self.capacity
return self.data[tail]
def isEmpty(self) -> bool:
return self.size == 0 def isFull(self) -> bool:
return self.size == self.capacity

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Shifting array	O(n) deQueue	O(k)	Easy state management, but every front removal moves data.
Linked list + capacity	O(1)	O(k)	Also works, but allocates one node per element and misses the ring-buffer lesson.
Ring buffer ← optimal	O(1) all methods	O(k)	No shifts, no extra nodes, and wraparound is handled with modulo arithmetic.

Why not keep a moving tail pointer only?:

You can, but then you still need either a size field or one permanently unused slot to separate full from empty.
The head + size formulation is compact and less bug-prone in interviews.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Expected behavior	Why it matters
`k = 1`	The only slot alternates between full and empty	Small capacities expose off-by-one mistakes quickly.
Queue is empty	`deQueue()` returns false, `Front()`/`Rear()` return -1	The interface uses sentinel values instead of exceptions.
Queue is full	`enQueue()` returns false	You must reject writes instead of overwriting existing data.
Wraparound after deletions	Freed slots at the front are reused	This is the entire advantage over a naive array queue.
Repeated cycles of fill → empty → fill	All operations stay O(1)	Persistent correctness matters more than one successful example.

⚠ Common Mistake: Using head == tail to mean “empty” without any extra state breaks as soon as the queue becomes full, because a full ring can also make the indices equal. Track size explicitly, or intentionally waste one slot and code the full condition differently.

← Back to Queue problems

LearningTree

LC 622 · Design Circular Queue — Solution & Explanation | DSA Guide