Circular Queue
Stacks & Queues: lesson 8 of 9
A fixed array that never shifts, because the ends wrap around.
Lesson 8 of 9 · 5 min
Circular Queue
Step 1 of 10
head0size0/5
queue
Five cells, joined end to end. Two integers describe the queue: head and size.
The Idea
A queue on a plain list is tempting until you see the cost: removing the front shifts everything else down. A ring buffer never moves data. It moves two numbers.
head marks the front, size says how many cells are live, and % capacity folds any index past the end back to the beginning.
Real-World Example
A dashboard camera writing over the oldest footage. The card never grows and nothing is ever copied — the write head simply comes round again and lands on the frames you no longer need.
The Code
class Ring:
def __init__(self, cap):
self.buf, self.head, self.size = [None] * cap, 0, 0
def push(self, x):
if self.size == len(self.buf): raise IndexError("full")
self.buf[(self.head + self.size) % len(self.buf)] = x # wrap with %
self.size += 1
def pop(self):
x = self.buf[self.head]
self.head = (self.head + 1) % len(self.buf) # head walks the ring
self.size -= 1
return x
r = Ring(3)
for x in "abc": r.push(x)
print(r.pop(), r.pop()) # a b
r.push("d"); r.push("e") # the two freed cells are reused, nothing shifts
print(r.buf, r.head) # ['d', 'e', 'c'] 2Your turn
What does this print?
buf, head, size = [None] * 3, 0, 0
for x in "abc":
buf[(head + size) % 3] = x; size += 1
head, size = (head + 1) % 3, size - 1
buf[(head + size) % 3] = "d"; size += 1
print(buf)Mini quiz
1 / 3