622. Design Circular Queue

622

MediumData Structure DesignFixed array with modular indexingRing buffer with head + size

Design Circular Queue

Design a circular queue of fixed capacity k. enQueue(value) inserts at the rear and returns true, or false if the queue is full. deQueue() removes the front element and returns true, or false if empty. Front() and Rear() return the front and rear values or -1 if empty. isEmpty() and isFull() report the state. The circular design reuses freed slots at the front instead of wasting space.

Open official problem prompt ↗

In plain English

Implement a fixed-capacity FIFO queue that reuses freed front slots, with every operation in constant time.

Picture it like this

Like a circular parking lot with numbered spots: cars leave from the front and new cars fill the next open spot, and the counting wraps back to spot 0 after the last one.

Example

Input: MyCircularQueue(3); enQueue(1); enQueue(2); enQueue(3); enQueue(4); Rear(); isFull(); deQueue(); enQueue(4); Rear()
Output: [null, true, true, true, false, 3, true, true, true, 4]
Why: The 4th enQueue fails (full, capacity 3); after one deQueue frees a slot, enQueue(4) succeeds and Rear() is 4.

Constraints

1 <= k <= 10000 <= value <= 1000At most 3000 calls across all methodsAll operations must run in O(1) time

Pattern lesson

See the pattern, then code

Ring buffer with head + size

↗

Data Structure Design

An API whose operations must meet strict O(1) or O(log n) contracts.. Store a head index and a live count; the rear slot is (head + count) mod k, so you never shift elements - indices simply wrap around the fixed array.

New words, made simpleKnow these before the algorithm

Ring buffer: A fixed array treated as circular via modular arithmetic.
Head index: Position of the current front element.
Wraparound: Using % k so an index past the end returns to the start.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Python list with pop(0)

Front removal shifts all elements - not O(1) and not fixed-capacity.

Use a dynamic list and pop from the front on dequeue.

Time O(n) per dequeueSpace O(n)

Best choiceFixed array with head + count

No shifting, fixed memory, and clean full/empty tests via count.

Track a head pointer and live count, computing the rear by modular arithmetic.

Time O(1) per operationSpace O(k)

The rule we keep true

Invariant

count always equals the number of live elements, and they occupy slots head, head+1, ..., head+count-1 taken modulo k.

Why this is correct

Reasoning

Storing count (rather than only head and tail pointers) removes the classic full-vs-empty ambiguity: full is count == k and empty is count == 0, and modular indexing guarantees the used slots stay contiguous around the ring without ever moving data.

The algorithm in three movesSay these aloud before coding

1Allocate an array of size k and track head index and current count

head=0, count=3, q=[1,2,3]

2enQueue writes to (head + count) % k and increments count if not full

enQueue(4): count==cap -> False

3deQueue advances head to (head + 1) % k and decrements count if not empty

deQueue: head=1; enQueue(4): q[(1+2)%3=0]=4

4Front is q[head]; Rear is q[(head + count - 1) % k]; empty/full compare count to 0 and k

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readthree inserts

2 · Askfull?

3 · Update stateq=[1,2,3], head=0, count=3

4 · Resultall true

Key takeaway

A size-3 ring buffer where the rear index wraps to slot 0 after a dequeue frees it.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 2-6State
A pre-sized array, capacity, head index, and live count.
2
Lines 8-13enQueue
Reject when full; otherwise write at (head + count) % cap and grow count.
3
Lines 15-20deQueue
Reject when empty; otherwise advance head modulo cap and shrink count.
4
Lines 22-30Front / Rear
Front is q[head]; rear is computed with the same modular offset, both -1 when empty.
5
Lines 32-36isEmpty / isFull
Direct comparisons of count against 0 and capacity.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Capacity 1 queue toggles between empty and full on each op
deQueue on empty returns false without touching head
Rear right after wraparound reads slot 0 correctly
Front and Rear on an empty queue both return -1

Common beginner mistakes

Confusing full and empty when using only head/tail pointers without a count
Computing rear as head + count instead of head + count - 1 (off by one)
Forgetting the modulo on the rear/enqueue index so it runs off the array
Using list.pop(0), which is O(n) and abandons the fixed-capacity design

Check your understanding

Why does storing a count avoid the full-versus-empty ambiguity that plagues head/tail-only ring buffers?

PyPython 3 · solution.py

Optimal

1class MyCircularQueue:2    def __init__(self, k: int):3        self.q = [0] * k4        self.cap = k5        self.head = 06        self.count = 078    def enQueue(self, value: int) -> bool:9        if self.count == self.cap:10            return False11        self.q[(self.head + self.count) % self.cap] = value12        self.count += 113        return True1415    def deQueue(self) -> bool:16        if self.count == 0:17            return False18        self.head = (self.head + 1) % self.cap19        self.count -= 120        return True2122    def Front(self) -> int:23        return -1 if self.count == 0 else self.q[self.head]2425    def Rear(self) -> int:26        if self.count == 0:27            return -128        return self.q[(self.head + self.count - 1) % self.cap]2930    def isEmpty(self) -> bool:31        return self.count == 03233    def isFull(self) -> bool:34        return self.count == self.cap

Time complexityO(1) per operationOptimized

Space complexityO(k)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMicrosoftBloombergGoogle

Design Circular Queue

Design Circular Queue

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Data Structure Design