Design a Circular Queue: The Ring Buffer, Head, Size and Modulo

A queue is easy to use and surprisingly easy to build badly. Put it on a plain array, remove from the front, and every remaining element shifts down one place. The fix is the ring buffer, also called a circular queue: a fixed array whose two ends are joined, so nothing ever moves except two integers. "Design a circular queue" is a common interview question because it is small enough to write in full and has one trap, telling full from empty, that catches people who have not thought it through.

The problem it solves

A queue is first in, first out: enqueue at the back, dequeue from the front. On a Python list, append is cheap, but pop(0) shifts every remaining element one place to the left. Draining n queued items that way moves about n² / 2 elements in total. Shifting the data is the waste.

A ring buffer never shifts. It keeps a fixed array and remembers where the front is. Dequeuing moves the front index forward by one; enqueuing writes into the next free cell after the back. When an index runs off the end of the array, it continues at the start. Everything happens in constant time, and the memory never grows, which is the point in audio and network buffers, logs of the last k events, and producer-consumer queues with a hard limit.

The intuition

Lay the cells in a circle. Two numbers describe the whole queue:

• head, the index of the front element.
• size, how many cells are live.

The back of the queue is size cells after the head, so the next write goes to (head + size) % capacity. The modulo is the join between the end of the array and its start: index 5 in a five-cell ring is cell 0 again. Dequeue reads buf[head], then moves the head with head = (head + 1) % capacity and decrements the size. The cell is not cleared. Its old value stays there, dead, until a later enqueue writes over it.

Now the trap. A common design keeps two indexes, head and tail, and no size. In an empty queue, head equals tail. Fill every cell, and the tail wraps all the way round and equals the head again. The same state means two different things. There are two standard fixes. Keep a size counter, as above, and full means size == capacity. Or keep one cell permanently empty, so the tail can never catch up with the head: full means the next tail position would be the head, and an n-item queue needs n + 1 cells. Both are correct; pick one and say why.

Watch it run

The animation joins five cells end to end, and two integers describe the queue: head and size. It pushes a, b, c and d into cells 0 to 3, each at (head + size) % 5. It pops a, and the head moves to 1; the cell keeps its old contents, since nothing is shifted or cleared. It pops b, and the head moves to 2. It pushes e into cell 4. Then comes the wrap: (head + size) is past the end, so % 5 folds it back to cell 0, and f reuses a freed slot. The closing frame counts it up: six values handled, zero elements moved, where a list with pop(0) would have shifted on every single removal.

The code

A complete circular queue with the usual interface: enqueue and dequeue that report failure instead of raising, plus front, rear, is_empty and is_full. Replaying the animation's script leaves f in cell 0 and the old b still sitting, dead, in cell 1:

class RingQueue:
    def __init__(self, capacity):
        self.buf = [None] * capacity
        self.head = 0                      # index of the front element
        self.size = 0                      # how many cells are live

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

    def is_full(self):
        return self.size == len(self.buf)

    def enqueue(self, x):
        if self.is_full():
            return False
        self.buf[(self.head + self.size) % len(self.buf)] = x    # write position wraps
        self.size += 1
        return True

    def dequeue(self):
        if self.is_empty():
            return None
        x = self.buf[self.head]
        self.head = (self.head + 1) % len(self.buf)              # head walks the ring
        self.size -= 1
        return x

    def front(self):
        return None if self.is_empty() else self.buf[self.head]

    def rear(self):
        return None if self.is_empty() else self.buf[(self.head + self.size - 1) % len(self.buf)]

    def items(self):                       # logical order, front to back
        return [self.buf[(self.head + i) % len(self.buf)] for i in range(self.size)]

q = RingQueue(5)
for x in "abcd":
    q.enqueue(x)
print(q.dequeue(), q.dequeue())            # a b
q.enqueue("e")                             # (2 + 2) % 5 = cell 4
q.enqueue("f")                             # (2 + 3) % 5 = cell 0: the wrap
print(q.buf, q.head, q.size)               # ['f', 'b', 'c', 'd', 'e'] 2 4
print(q.items(), q.front(), q.rear())      # ['c', 'd', 'e', 'f'] c f

q.enqueue("g")
print(q.is_full(), q.enqueue("h"))         # True False

The other design: a head and a tail and no size, with one cell kept empty. A queue for three items needs four cells, and the fourth enqueue is refused:

class HeadTailQueue:
    """No size field: keep one slot empty so that head == tail can only mean empty."""
    def __init__(self, capacity):
        self.buf = [None] * (capacity + 1)
        self.head = self.tail = 0

    def enqueue(self, x):
        if (self.tail + 1) % len(self.buf) == self.head:
            return False                   # full: the tail would land on the head
        self.buf[self.tail] = x
        self.tail = (self.tail + 1) % len(self.buf)
        return True

    def dequeue(self):
        if self.head == self.tail:
            return None                    # empty
        x = self.buf[self.head]
        self.head = (self.head + 1) % len(self.buf)
        return x

h = HeadTailQueue(3)
print([h.enqueue(x) for x in "wxyz"], len(h.buf))   # [True, True, True, False] 4

A ring that overwrites instead of refusing, like a dashboard camera keeping only the latest footage. When it is full, the write lands on the oldest cell and the head moves past it. Python's collections.deque with maxlen behaves the same way. And the cost the ring avoids: queuing 10,000 items in a list and draining them with pop(0) shifts almost fifty million elements:

class Recorder:
    """Overwrite-the-oldest ring, like a dashboard camera: a push never fails."""
    def __init__(self, capacity):
        self.buf, self.head, self.size = [None] * capacity, 0, 0

    def push(self, x):
        cap = len(self.buf)
        self.buf[(self.head + self.size) % cap] = x
        if self.size == cap:
            self.head = (self.head + 1) % cap          # the oldest frame is gone
        else:
            self.size += 1

    def frames(self):
        return [self.buf[(self.head + i) % len(self.buf)] for i in range(self.size)]

from collections import deque

cam, ref = Recorder(3), deque(maxlen=3)
for frame in range(1, 8):
    cam.push(frame)
    ref.append(frame)
print(cam.frames(), list(ref))             # [5, 6, 7] [5, 6, 7]

def shifts_with_pop0(n):
    """Elements moved when n items are queued in a list and removed with pop(0)."""
    return sum(remaining - 1 for remaining in range(n, 0, -1))

print(shifts_with_pop0(10_000))            # 49995000

Checked against collections.deque on 500 seeded random runs of 60 operations, with capacities from 1 to 6 so full and empty are hit constantly. Both designs must accept, refuse and return exactly what the reference does:

import random

random.seed(24)
ok = True
for _ in range(500):
    cap = random.randint(1, 6)
    ring, alt, ref = RingQueue(cap), HeadTailQueue(cap), deque()
    for step in range(60):
        if random.random() < 0.55:
            x = random.randint(0, 99)
            accepted = len(ref) < cap
            if accepted:
                ref.append(x)
            ok &= ring.enqueue(x) == accepted == alt.enqueue(x)
        else:
            want = ref.popleft() if ref else None
            ok &= ring.dequeue() == want == alt.dequeue()
        ok &= ring.items() == list(ref)
        ok &= ring.front() == (ref[0] if ref else None)
        ok &= ring.rear() == (ref[-1] if ref else None)
        ok &= ring.is_full() == (len(ref) == cap) and ring.is_empty() == (not ref)
print(ok)                                  # True

The complexity

• Every operation: O(1). An enqueue or dequeue is one array access, one addition and one modulo.
• Space: O(capacity), allocated once. The head-and-tail design spends one extra cell.
• Compared with pop(0) on a list: O(n) per dequeue, O(n²) to drain a queue of n items. The Big-O cheat sheet lists the same warning next to the other queue operations.

Where it goes wrong

• Head equals tail for both full and empty. Keep a size, or keep a cell empty.
• Forgetting the modulo on one of the updates. The index walks off the end of the array on the first wrap.
• Computing the rear as head + size. That is the next free cell; the last element is one before it, (head + size - 1) % capacity.
• Negative indexes in other languages. (i - 1) % n is safe in Python, but in C or Java it can be negative; add n first.
• Assuming dequeued cells are cleared. They still hold the old value; read through head and size, never the raw array.

When it shows up in interviews

"Design a circular queue" is a common medium question, and "design a circular deque" is the same ring with the head allowed to move backwards too. The ring also sits inside other answers: a bounded producer-consumer buffer, a fixed window of the last k readings for a moving average, and hit counters that bucket events per second. The other queue construction question is a queue built from two stacks, which trades the fixed size for amortised cost.

How to say it in an interview

"I use a fixed array with a head index and a size. Enqueue writes at (head + size) % capacity and increments the size; dequeue reads at the head, advances it modulo the capacity and decrements the size. Nothing is ever shifted, so every operation is O(1) and memory is fixed. The size field is what tells full from empty, since a bare head and tail are equal in both cases. The alternative is to keep one cell empty and call the queue full when the next tail would hit the head."