Circular Queue
DSA · Stacks and Queues
Theory
A circular queue (ring buffer) is a queue stored in a fixed-size array where the end wraps around to the beginning. Two indexes track the front and the rear. When the rear reaches the last slot, the next element is written to slot 0 if it is free, using the modulo operator: rear = (rear + 1) % capacity. This reuses space left behind by dequeued items, so a fixed block of memory can serve an endless stream of data without shifting elements. Ring buffers are used in keyboard input buffers, audio and video streaming, network packet queues and logging systems that keep only the most recent N events.
Why we use it
A plain array queue either wastes space at the front or needs O(n) shifting. A circular queue gives O(1) enqueue and dequeue with a fixed memory footprint, which is ideal for embedded systems and streaming.
When to use it
Use it when the maximum size is known and you want constant memory, for example the last 100 log lines or a producer-consumer buffer. Use collections.deque in Python for general queues.
How it works
- front = 0, size = 0, capacity = k
- Enqueue and size < k? Yes: rear = (front + size) % k; store; size++. No: Queue full: reject.
- Dequeue and size > 0? Yes: Take buf[front]; front = (front + 1) % k; size--. No: Queue empty.
- Indexes wrap around the array
Syntax
enqueue rear = (rear + 1) % cap O(1)
dequeue front = (front + 1) % cap O(1)
full size == cap
empty size == 0Example
class CircularQueue:
def __init__(self, capacity):
self.buf = [None] * capacity
self.cap, self.front, self.size = capacity, 0, 0
def enqueue(self, x):
if self.size == self.cap:
return False # full
rear = (self.front + self.size) % self.cap
self.buf[rear] = x
self.size += 1
return True
def dequeue(self):
if self.size == 0:
return None # empty
x = self.buf[self.front]
self.front = (self.front + 1) % self.cap
self.size -= 1
return x
q = CircularQueue(3)
print([q.enqueue(v) for v in (10, 20, 30, 40)]) # 40 rejected: full
print(q.dequeue(), q.dequeue()) # 10 20
print(q.enqueue(50), q.enqueue(60)) # wraps around
print([q.dequeue() for _ in range(4)]) # 30 50 60 NoneKey points
- Modulo arithmetic makes the array wrap around
- Tracking size avoids confusing a full queue with an empty one
- Both operations are O(1) with no shifting
- Python offers deque(maxlen=n) for a ready-made bounded queue