Design Circular Queue

Problem

Database connection pools and OS I/O buffers use circular queues to manage a fixed set of slots without allocating or shifting memory. Implement MyCircularQueue with capacity k using a fixed array: enqueue(val), dequeue(), front(), rear(), is_empty(), is_full(). Use head and tail pointers with modular arithmetic.

MyCircularQueue(3)
enqueue(1) → True;  enqueue(2) → True;  enqueue(3) → True
enqueue(4) → False  # full
rear()     → 3
is_full()  → True
dequeue()  → True
enqueue(4) → True   # slot freed
rear()     → 4

Try it

Python

Loading editor…

Tests

q = MyCircularQueue(3)
assert q.enqueue(1) and q.enqueue(2) and q.enqueue(3), "fill to capacity"
assert not q.enqueue(4), "reject when full"
assert q.is_full() and not q.is_empty(), "full state"
assert q.front()==1 and q.rear()==3, "front and rear"
assert q.dequeue(), "dequeue from front"
assert q.enqueue(4), "enqueue after dequeue"
assert q.front()==2 and q.rear()==4, "wrap-around state"
q2 = MyCircularQueue(1)
assert q2.is_empty() and not q2.is_full(), "empty single-slot queue"
assert q2.enqueue(99) and q2.front()==99 and q2.rear()==99, "single slot"
assert not q2.enqueue(0), "single slot full"

Hints (3)

Solution

Approach: Fixed array as a ring with head/tail pointers and a size counter.

Allocate data once with k slots. head indexes the oldest element, tail indexes the next free slot to write, and size counts live elements. Enqueue writes data[tail] = value, then advances tail = (tail + 1) % capacity and bumps size. Dequeue does not erase anything - it just advances head = (head + 1) % capacity and drops size. The % capacity is what makes the array circular: when a pointer steps off the last slot it wraps back to index 0, so freed front slots get reused without ever shifting elements.

The subtle part is telling full from empty, because head == tail is true in both states. The size counter resolves the ambiguity directly - is_full is size == capacity, is_empty is size == 0 - which is cleaner than the alternative of sacrificing one slot. rear() must read data[(tail - 1) % capacity], not data[tail], because tail already points one past the last written element; the - 1 with the modulo handles the case where tail just wrapped to 0. Trace MyCircularQueue(3): enqueue 1,2,3 fills it (size == 3), a fourth enqueue is rejected, dequeue advances head to 1, then enqueue 4 writes into the freed slot 0 and tail wraps - front() is now 2, rear() is 4.

Edge cases: Every operation guards its precondition - enqueue checks is_full, dequeue/front/rear check is_empty and return False or -1 rather than corrupting state or indexing out of range. A capacity-1 queue works because wrap-around and the size counter are independent of k.

Complexity: O(1) time for every operation - pure pointer arithmetic and array indexing, no shifting; O(k) space for the fixed backing array.