Array Queue Operations and Wraparound

A FIFO queue removes the earliest still-present item. Here front identifies the next item to remove, rear identifies the next free slot to write, and count records occupancy. Initially both indices and count are zero. The backing array has a fixed positive capacity, and a queue can be empty or full even when front equals rear.

On enqueue, first reject a full queue, write at rear, advance rear modulo capacity and increase count. On dequeue, first reject an empty queue, read at front, optionally clear the stored reference, advance front modulo capacity and decrease count. The choice of whether rear identifies the last item or the next free slot differs between implementations; never mix the two conventions in one trace.

With capacity three, enqueue A,B,C fills slots 0,1,2 and moves rear to 0. Dequeue returns A and moves front to 1. Enqueue D then writes slot 0, so physical storage is D,B,C while the logical removal order is B,C,D. Reading the array from index zero is not a valid logical queue traversal after wrapping.

An occupied-count field distinguishes full from empty without reserving a spare slot. Another design can leave one slot unused and use an index relationship instead, but its usable capacity differs. State which design is used before checking boundary conditions. The example explicitly raises errors for overflow and underflow rather than overwriting data or inventing a return value.

Each successful enqueue or dequeue changes a fixed number of array positions and fields, giving constant time under the simple array model. Allocating the array takes capacity-related space. A linear queue implementation that shifts every remaining item after removal can have a different operation cost; the FIFO contract alone does not determine the implementation.

Useful invariants are 0≤count≤capacity and 0≤front,rear<capacity. The next free slot is rear, while the next item is at front only when count is positive. Test an empty removal, filling exactly to capacity, rejecting one extra insertion, wrapping after removal and draining in FIFO order. Maintaining these invariants is more useful than memorising one index formula without its meaning.

class Queue:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("positive capacity required")
        self.items = [None] * capacity
        self.front = self.rear = self.count = 0

    def enqueue(self, value):
        if self.count == len(self.items):
            raise OverflowError("queue full")
        self.items[self.rear] = value
        self.rear = (self.rear + 1) % len(self.items)
        self.count += 1

    def dequeue(self):
        if self.count == 0:
            raise IndexError("queue empty")
        value = self.items[self.front]
        self.items[self.front] = None
        self.front = (self.front + 1) % len(self.items)
        self.count -= 1
        return value

queue = Queue(3)
for value in ["A", "B", "C"]:
    queue.enqueue(value)
print(queue.dequeue())
queue.enqueue("D")
print([queue.dequeue() for _ in range(3)])

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.