Designing a Circular Queue

Use a fixed size array and a head index that wraps around. The wrap is what the modulo does: the next write position is the head plus the number of items currently stored, taken modulo the capacity. Because the array is circular, the space freed at the front becomes available at the back again, so you never need to shift elements.

The genuinely tricky part is telling an empty queue from a full one. If you only track a head index, the queue looks empty when head equals the write position, which happens both when it is empty and when it is completely full. The standard solutions are to keep a separate count, which is the simplest, or to sacrifice one slot so that the head and the write position can never coincide in both states.

The mechanism is that the array is treated as a ring. Index arithmetic is always taken modulo the capacity, so position n minus one is followed by position zero. The write position is derived from the head and the count, so it always points at the first free slot.

The trade-off to name is the one-slot sacrifice. Reserving a slot avoids the extra counter and the branch that maintains it, at the cost of being able to hold one fewer element than the array size. That is a constant factor, so it rarely matters, but it changes the capacity semantics and interviewers sometimes care about it. The other design question is thread safety: a queue shared between a producer and a consumer needs locking or a lock-free ring buffer, and the lock-free version relies on careful memory ordering that is genuinely difficult to get right.

Keep the items in a fixed array with a head index and a count of how many slots are occupied. The write position is derived from the head and the count.

class CircularQueue:
    def __init__(self, capacity):
        self.items = [None] * capacity
        self.capacity = capacity
        self.front = 0
        self.count = 0

    def enqueue(self, value):
        if self.count == self.capacity:
            return False
        self.items[(self.front + self.count) % self.capacity] = value
        self.count += 1
        return True

    def dequeue(self):
        if self.count == 0:
            return None
        value = self.items[self.front]
        self.items[self.front] = None
        self.front = (self.front + 1) % self.capacity
        self.count -= 1
        return value

    def peek(self):
        if self.count == 0:
            return None
        return self.items[self.front]


queue = CircularQueue(3)
print(queue.enqueue(1), queue.enqueue(2), queue.enqueue(3))
print(queue.enqueue(4))
print(queue.dequeue(), queue.peek())

The outputs are True, True, True, then False, then 1 and 2. The three enqueues fill the queue, the fourth is refused because there is no room, and dequeuing returns the first value and leaves the second at the front.

The mechanism is the write position. The item that is the count-th element after the head is the first free slot, and taking that modulo the capacity wraps it around to the beginning of the array when the queue is near full. The head moves forward by one on each dequeue, also modulo the capacity, so the freed slot becomes available again.

The trade-off to name is that the count field makes the empty and full states unambiguous, and it costs one extra integer plus a branch in each operation. Clearing the slot on dequeue is not needed for correctness but is worth doing so that a dequeued reference is not kept alive by the array, which matters in a long running service. The other thing a production implementation needs is a way to wait rather than fail when the queue is full, which is where the lock-free ring buffer earns its keep.