The Circular Queue: Wrap-Around
Chapter Forty-Four
Syllabus topic Module 1, "Queues: Circular Queue operations"
Pages 134 to 136 of 411
In one line
A circular queue treats the array as a ring by advancing every index with modulo arithmetic, so the cells freed at the front are reused and both operations stay O(1).
The one idea
Chapter 42's queue failed because rear ran off the end of the array while cells at the front sat empty. The fix is to let it carry on from the beginning.
rear = (rear + 1) mod capacity
front = (front + 1) mod capacity
That is the whole change. The modulo turns the array into a ring: index 4 of a 5 cell array is followed by index 0.
Drawn, the array is a circle with the two markers on it:
cell 0 - cell 1 - cell 2 - cell 3 - cell 4 - back to cell 0
The queue is the stretch from front round to rear, which may wrap past the end.
The operations
enqueue: cells[rear] = item; rear = (rear + 1) mod capacity; count = count + 1
dequeue: item = cells[front]; front = (front + 1) mod capacity; count = count - 1
empty : count == 0
full : count == capacity
A count is kept, and chapter 45 explains why that choice is made rather than deducing full and empty from the markers alone.
Built and run, with the wrap visible
class CircularQueue:
"""The array as a ring. count distinguishes full from empty."""
def __init__(self, capacity):
self.capacity = capacity
self.cells = [None] * capacity
self.front = 0
self.rear = 0
self.count = 0
def is_empty(self):
return self.count == 0
def is_full(self):
return self.count == self.capacity
def size(self):
return self.count
def enqueue(self, item):
if self.is_full():
raise OverflowError("enqueue onto a full queue: overflow")
self.cells[self.rear] = item
self.rear = (self.rear + 1) % self.capacity
self.count += 1
def dequeue(self):
if self.is_empty():
raise IndexError("dequeue from an empty queue: underflow")
item = self.cells[self.front]
self.cells[self.front] = None
self.front = (self.front + 1) % self.capacity
self.count -= 1
return item
def front_item(self):
if self.is_empty():
raise IndexError("front of an empty queue: underflow")
return self.cells[self.front]
def order(self):
"""The items from front to rear, following the ring."""
out = []
for step in range(self.count):
out.append(self.cells[(self.front + step) % self.capacity])
return out
def picture(self):
cells = ["%-4s" % ("." if c is None else c) for c in self.cells]
return "[%s] f=%d r=%d n=%d" % (" ".join(cells), self.front,
self.rear, self.count)
q = CircularQueue(5)
print("new ", q.picture())
for person in ("A", "B", "C"):
q.enqueue(person)
print("A B C in ", q.picture(), "order:", q.order())
q.dequeue()
q.dequeue()
print("2 out ", q.picture(), "order:", q.order())
q.enqueue("D")
q.enqueue("E")
print("D E in ", q.picture(), "order:", q.order())
print()
print("now the wrap: rear is at the end of the array and there are free cells at the front")
q.enqueue("F")
print("F in ", q.picture(), "order:", q.order())
q.enqueue("G")
print("G in ", q.picture(), "order:", q.order())
print()
print("the queue is full now:", q.is_full(), "with size", q.size(),
"of capacity", q.capacity)
try:
q.enqueue("H")
except OverflowError as e:
print("enqueue H ->", e)
print()
print("draining it in order:")
while not q.is_empty():
print(" dequeue ->", q.dequeue(), " ", q.picture())The Circular Queue: Wrap-Around
new [. . . . . ] f=0 r=0 n=0
A B C in [A B C . . ] f=0 r=3 n=3 order: ['A', 'B', 'C']
2 out [. . C . . ] f=2 r=3 n=1 order: ['C']
D E in [. . C D E ] f=2 r=0 n=3 order: ['C', 'D', 'E']
now the wrap: rear is at the end of the array and there are free cells at the front
F in [F . C D E ] f=2 r=1 n=4 order: ['C', 'D', 'E', 'F']
G in [F G C D E ] f=2 r=2 n=5 order: ['C', 'D', 'E', 'F', 'G']
the queue is full now: True with size 5 of capacity 5
enqueue H -> enqueue onto a full queue: overflow
draining it in order:
dequeue -> C [F G . D E ] f=3 r=2 n=4
dequeue -> D [F G . . E ] f=4 r=2 n=3
dequeue -> E [F G . . . ] f=0 r=2 n=2
dequeue -> F [. G . . . ] f=1 r=2 n=1
dequeue -> G [. . . . . ] f=2 r=2 n=0Follow the line marked "D E in": rear has become 0. It reached 5, the capacity, and wrapped to the beginning. The next enqueue puts F in cell 0, which chapter 42 had abandoned for ever.
The queue now uses every cell, it holds 5 items in a 5 cell array, and it correctly refuses the sixth. The drift is gone and both operations are still two assignments.
Note the order line while the queue is wrapped: the items are C, D, E, F, G but they sit in the array as F, G, C, D, E. The order lives in the markers, not in the positions, which is why order walks with the modulo rather than reading the array left to right.
The cost
| Circular queue | |
|---|---|
| enqueue | O(1) |
| dequeue | O(1) |
| Space used | all of it |
| Capacity | fixed at creation |
| Overflow | genuine, only when actually full |
Compare chapter 42's two attempts: the drifting queue had O(1) operations and wasted space, the shifting queue had full space use and O(n) dequeue. The circular queue has both, and the only thing it costs is a little index arithmetic.
The trap in reading the array
Printing the cells left to right does not print the queue. In the run above the array read F G C D E while the queue was C, D, E, F, G. An examination answer that reads the block in order has misread the structure.
The Circular Queue: Wrap-Around
Always report a circular queue from front, stepping with the modulo, for count items.
Quick revision
- The array is treated as a ring: every index advance is
(index + 1) mod capacity. - This reuses the cells freed at the front, which the drifting queue abandoned.
- enqueue writes at rear then advances it; dequeue reads at front then advances it. Both O(1).
- A separate count is kept for size, empty and full.
- The queue occupies the stretch from front round to rear and may wrap past the end of the array.
- The order lives in the markers, not the positions: reading the array left to right does not give the
queue's order.
- It achieves what neither chapter 42 attempt did: O(1) both ways with every cell usable.
Test yourself
1. What single change turns the drifting queue into a circular one? Advancing the indices with modulo the capacity, so that after the last cell they continue at the first.
2. Write the enqueue and dequeue operations. enqueue: check full, cells[rear] = item, rear = (rear + 1) mod capacity, increment the count. dequeue: check empty, item = cells[front], front = (front + 1) mod capacity, decrement the count.
3. In the run, the array held F G C D E and the queue was C, D, E, F, G. Explain. The queue starts at front, which was 2, and wraps round the end of the array. The order is given by stepping from front with the modulo, not by reading the cells left to right.
4. Compare the circular queue with the two attempts of chapter 42. The drifting queue was O(1) but abandoned a cell per dequeue. The shifting queue used all the space but made dequeue O(n). The circular queue is O(1) both ways and uses every cell.
5. When does a circular queue genuinely overflow? Only when it actually holds capacity items, unlike the drifting queue, which reported full whenever rear reached the end.
6. How should a circular queue be printed? From front, stepping with (front + step) mod capacity for count items. Reading the array in index order misreports it whenever the queue is wrapped.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.