Introduction
A circular queue (or ring buffer) is a fixed-capacity queue where the front and rear indices wrap around to the beginning of the underlying array once they reach the end. In a naive array-based queue, dequeuing from the front leaves that slot permanently unused, wasting space over time. A circular queue reclaims those freed slots by treating the array as a logical circle, making it ideal for streaming buffers, CPU scheduling, and network packet buffering where memory must stay bounded.
Cricket analogy: A fixed set of 11 wristbands handed out to fielders on a rotating basis wastes a wristband forever if you just retire it after each fielder leaves; a circular queue instead reclaims that same wristband slot for the next fielder, keeping the kit bag bounded.
Syntax
class CircularQueue:
def __init__(self, capacity: int):
self.capacity = capacity
self.data = [None] * capacity
self.front = 0 # index of the front element
self.size = 0 # current number of elements
def is_full(self) -> bool:
return self.size == self.capacity
def is_empty(self) -> bool:
return self.size == 0Explanation
The key idea is index wraparound via the modulo operator. The rear insertion position is computed as (front + size) % capacity, so once the raw index would exceed capacity - 1, the modulo operation wraps it back to 0. Dequeuing similarly advances front with front = (front + 1) % capacity instead of shifting all elements. A size counter (or a distinct full/empty flag) is essential: with only front and rear pointers, an empty queue and a full queue can produce the same front == rear condition, so size disambiguates the two states.
Cricket analogy: A stadium's fixed 20-seat VIP box computes the next open seat as (current occupied count) modulo capacity, wrapping back to seat 1 once seat 20 fills; the usher must separately track headcount, because "seat 1 is next" alone can't tell an empty box from a full one.
Example
class CircularQueue:
def __init__(self, capacity: int):
self.capacity = capacity
self.data = [None] * capacity
self.front = 0
self.size = 0
def is_full(self) -> bool:
return self.size == self.capacity
def is_empty(self) -> bool:
return self.size == 0
def enqueue(self, value):
if self.is_full():
raise OverflowError("Circular queue is full")
rear = (self.front + self.size) % self.capacity
self.data[rear] = value
self.size += 1
def dequeue(self):
if self.is_empty():
raise IndexError("Circular queue is empty")
value = self.data[self.front]
self.data[self.front] = None
self.front = (self.front + 1) % self.capacity
self.size -= 1
return value
cq = CircularQueue(3)
cq.enqueue("a")
cq.enqueue("b")
cq.enqueue("c")
cq.dequeue() # removes 'a', frees index 0
cq.enqueue("d") # wraps around and reuses index 0
print(cq.data) # ['d', 'b', 'c']Complexity
Enqueue and dequeue are both O(1), identical to a standard queue, because index arithmetic replaces element shifting. Space complexity is O(capacity), fixed at allocation time rather than growing unbounded — this is the whole point: a circular queue trades dynamic growth for predictable, bounded memory usage, which matters in embedded systems and real-time buffering.
Cricket analogy: Swapping a fielder in or out of a fixed 11-slot rotation using index arithmetic is instant, unlike physically reshuffling everyone's position; the squad size stays fixed at 11 no matter how many substitutions happen, which is exactly what matters for a bounded matchday roster.
Key Takeaways
- A circular queue is a fixed-size array that wraps indices using the modulo operator to reuse freed slots.
- Rear position: (front + size) % capacity; front advances via front = (front + 1) % capacity.
- A size counter (or distinct full/empty flags) is required because front == rear alone cannot distinguish empty from full.
- Enqueue and dequeue remain O(1), same as a linear queue, but with bounded, reusable memory.
- Common uses: ring buffers for streaming data, CPU round-robin scheduling, and network packet queues.
Practice what you learned
1. What problem does a circular queue solve compared to a naive array-based linear queue?
2. In a circular queue implementation using front and size, how is the rear insertion index computed?
3. Why is a separate size counter (or full/empty flag) typically needed in a circular queue?
4. What is the time complexity of enqueue and dequeue in a circular queue?
Was this page helpful?
You May Also Like
Queues
A FIFO data structure supporting O(1) enqueue and dequeue, ideal for task scheduling and breadth-first traversal.
Deques
A double-ended queue allowing O(1) insertion and removal from both the front and the back.
Arrays in Data Structures
How arrays store elements in contiguous memory and why that layout drives their performance characteristics.