A Fixed-capacity Circular Queue in Python

A queue removes the earliest still-present item first: first in, first out. This circular implementation uses a fixed list. front names the next removal position; rear names the next insertion position. After either index reaches the final slot, adding one modulo capacity wraps it to zero. Logical order follows active items around the ring, not simply increasing array indices from zero.

count disambiguates equal indices. When count=0 the queue is empty; when count=capacity it is full. In both cases front and rear may be equal. Testing only front==rear cannot identify which state this representation occupies. Another implementation can deliberately reserve an unused slot instead, but its capacity and invariants differ from this count-based design.

enqueue checks full, writes at rear, advances rear modulo capacity and increments count. dequeue checks empty, reads and clears front, advances front modulo capacity and decrements count. peek reads at front without advancing anything. Empty and full operations raise the documented errors before overwriting or removing data.

For capacity three, enqueue A,B,C leaves front=0,rear=0,count=3. Dequeue returns A and sets front=1,count=2. Enqueue D writes into physical slot 0 and advances rear to 1. Both indices are now 1 with count=3; logical order is B,C,D even though the physical list is [D,B,C]. A trace should show both views.

Each ordinary method performs a constant number of indexed operations and arithmetic updates, O(1) in this model. It avoids the O(n) shifting associated with repeatedly removing a Python list’s first item. Reserving capacity uses O(capacity) storage and does not itself increase a device’s sustained processing rate; a producer that remains faster than the consumer will still fill it.

Test capacity one as well as larger values: the indices remain zero after every modular update, but count still distinguishes its states. Alternate inserts/removals over many wraps, compare outputs with an independent FIFO model and confirm that overflow/underflow leave the state unchanged. Include None as an ordinary item so no hidden sentinel assumption can pass unnoticed.

class CircularQueue:
    def __init__(self, capacity):
        if type(capacity) is not int or capacity <= 0:
            raise ValueError('Capacity must be a positive integer')
        self.storage = [None] * capacity
        self.front = self.rear = self.count = 0

    def is_empty(self):
        return self.count == 0

    def is_full(self):
        return self.count == len(self.storage)

    def enqueue(self, value):
        if self.is_full():
            raise OverflowError('Queue full')
        self.storage[self.rear] = value
        self.rear = (self.rear + 1) % len(self.storage)
        self.count += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError('Queue empty')
        value = self.storage[self.front]
        self.storage[self.front] = None
        self.front = (self.front + 1) % len(self.storage)
        self.count -= 1
        return value

    def peek(self):
        if self.is_empty():
            raise IndexError('Queue empty')
        return self.storage[self.front]

    def __len__(self):
        return self.count

queue = CircularQueue(3)
for value in ('A', 'B', 'C'):
    queue.enqueue(value)
print(queue.dequeue())
queue.enqueue('D')
print(queue.storage)
print(queue.front, queue.rear, queue.count)
print([queue.dequeue() for _ in range(3)])
print(len(queue))

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.