AlgoScope

Circular Queue

A queue in a fixed array never shifts anything. The front and rear are just indices, and when one reaches the last slot it wraps to slot 0. A slot freed at the front gets reused at the rear, so the array is a ring.

The player

Empty circular queue with 4 slots. Running 8 operations: enqueue 5, enqueue 3, enqueue 9, dequeue, dequeue, enqueue 7, enqueue 2, peek.0123front

An empty queue in an array of 4 slots. Items join at the rear and leave from the front, and both indices wrap around to slot 0 instead of shifting anything.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 6, with their answers.

  1. Rear is at slot 0, 1 of 4 slots used. Where does 3 go?

    • The next slot
    • Wraps to slot 0
    • Rejected, full

    Answer: The next slot. There is room and the rear is not at the last slot, so it just steps forward.

  2. Rear is at slot 1, 2 of 4 slots used. Where does 9 go?

    • The next slot
    • Wraps to slot 0
    • Rejected, full

    Answer: The next slot. There is room and the rear is not at the last slot, so it just steps forward.

  3. Front is at slot 0 with 5. After removing it, where is the front?

    • The next slot
    • Wraps to slot 0
    • Rejected, empty

    Answer: The next slot. The front steps forward to slot 1. Slot 0 is free for the rear to reuse.

  4. Front is at slot 1 with 3. After removing it, where is the front?

    • The next slot
    • Wraps to slot 0
    • Rejected, empty

    Answer: The next slot. The front steps forward to slot 2. Slot 1 is free for the rear to reuse.

  5. Rear is at slot 2, 1 of 4 slots used. Where does 7 go?

    • The next slot
    • Wraps to slot 0
    • Rejected, full

    Answer: The next slot. There is room and the rear is not at the last slot, so it just steps forward.

  6. Rear is at slot 3, 2 of 4 slots used. Where does 2 go?

    • The next slot
    • Wraps to slot 0
    • Rejected, full

    Answer: Wraps to slot 0. Slot 3 is the last one, and there is room, so the index wraps: (3 + 1) mod 4 = 0.

How it runs, step by step

  1. An empty queue in an array of 4 slots. Items join at the rear and leave from the front, and both indices wrap around to slot 0 instead of shifting anything.

    Empty circular queue with 4 slots. Running 8 operations: enqueue 5, enqueue 3, enqueue 9, dequeue, dequeue, enqueue 7, enqueue 2, peek.

  2. enqueue 5 into slot 0, where the front already waits. Size 1.

    Enqueue 5 into slot 0. Size 1.

  3. enqueue 3 into slot 1, one past the old rear. Size 2.

    Enqueue 3 into slot 1. Size 2.

  4. enqueue 9 into slot 2, one past the old rear. Size 3.

    Enqueue 9 into slot 2. Size 3.

  5. dequeue returns 5 from slot 0. Nothing shifts. The front moves to slot 1. Size 2.

    Dequeue removes 5 from slot 0. The front moves to slot 1.

  6. dequeue returns 3 from slot 1. Nothing shifts. The front moves to slot 2. Size 1.

    Dequeue removes 3 from slot 1. The front moves to slot 2.

  7. enqueue 7 into slot 3, one past the old rear. Size 2.

    Enqueue 7 into slot 3. Size 2.

  8. enqueue 2. The rear was at the last slot, 3, so it wraps to slot 0. That slot was freed by an earlier dequeue. Size 3.

    Enqueue 2. The rear wraps around to slot 0. Size 3.

  9. peek shows the front, 9 in slot 2, without removing it.

    Peek shows the front item, 9. Nothing changes.

  10. Done: 5 enqueues, 2 dequeues, 1 wrap. 3 items left, front at slot 2. Every operation was O(1) because nothing ever shifted.

    Done. 3 items remain, with the front at slot 2. 1 wrap around the array.

The code

Circular Queue, in Python

class CircularQueue:
    def __init__(self, capacity):
        self.slots = [None] * capacity
        self.head = 0
        self.size = 0

    def enqueue(self, v):
        if self.size == len(self.slots): return False              # full
        self.slots[(self.head + self.size) % len(self.slots)] = v  # rear wraps around
        self.size += 1
        return True

    def dequeue(self):
        if self.size == 0: return None                             # empty
        v = self.slots[self.head]
        self.slots[self.head] = None
        self.head = (self.head + 1) % len(self.slots)              # front wraps around
        self.size -= 1
        return v

    def peek(self): return None if self.size == 0 else self.slots[self.head]

Circular Queue, in JavaScript

class CircularQueue {
  constructor(capacity) {
    this.slots = new Array(capacity).fill(null);
    this.head = 0;
    this.size = 0;
  }

  enqueue(v) {
    if (this.size === this.slots.length) return false;              // full
    this.slots[(this.head + this.size) % this.slots.length] = v;    // rear wraps around
    this.size++;
    return true;
  }

  dequeue() {
    if (this.size === 0) return null;                               // empty
    const v = this.slots[this.head];
    this.slots[this.head] = null;
    this.head = (this.head + 1) % this.slots.length;                // front wraps around
    this.size--;
    return v;
  }

  peek() { return this.size === 0 ? null : this.slots[this.head]; }
}

Circular Queue, in Kotlin

class CircularQueue(capacity: Int) {
    private val slots = arrayOfNulls<Int>(capacity)
    private var head = 0
    var size = 0
        private set

    fun enqueue(v: Int): Boolean {
        if (size == slots.size) return false        // full
        slots[(head + size) % slots.size] = v       // rear wraps around
        size++
        return true
    }

    fun dequeue(): Int? {
        if (size == 0) return null                  // empty
        val v = slots[head]
        slots[head] = null
        head = (head + 1) % slots.size              // front wraps around
        size--
        return v
    }

    fun peek(): Int? = if (size == 0) null else slots[head]
}

This lesson has no write-it-yourself editor. It is free, like every lesson, and nothing here is locked.

Remember

  • Front and rear are indices into a fixed array. Dequeue moves the front, it never shifts items.
  • The next slot is (index + 1) mod capacity, which is how a pointer wraps from the last slot to 0.
  • Keep a size counter. Front equal to rear looks the same when the queue is empty and when it is full.

Where this is used

The Linux kernel logOperating systems

Everything printk writes goes into a fixed ring buffer, and dmesg just reads that ring. A driver may log from an interrupt handler, where allocating memory is not allowed, so the buffer has to be preallocated and bounded, and the oldest lines are overwritten rather than the buffer growing. That is why the earliest boot messages quietly disappear from dmesg on a machine that logs heavily.

Real-time audio buffersAudio

ALSA gives an application a fixed ring of sample frames with two pointers into it: the sound hardware advances one as it plays or captures, the application advances the other as it fills or drains, each at its own pace. Neither side ever waits on an allocation, which a callback with a few milliseconds of deadline cannot afford, so JACK ships a lock-free ring buffer of its own for handing samples to and from the processing thread. An underrun is nothing more exotic than one pointer catching up to the other before the next block was ready.

Network card descriptor ringsNetworking

A NIC and its driver share a ring of packet descriptors: the card advances a write index as frames arrive, the driver advances a read index as it consumes them. The ring must be fixed because it is DMA-mapped memory the hardware writes into directly, and the only thing the two sides exchange is a pair of indices, so there is no lock on the packet path. DPDK hands these same rings straight to user space.

The LMAX DisruptorConcurrency

The queue behind the LMAX trading exchange is a circular queue with a power-of-two capacity and entries allocated once at startup. Because slots are reused rather than allocated per message, passing millions of events a second creates no garbage, and the wrap is an AND rather than a division. Producers and consumers coordinate purely by publishing sequence numbers into that ring.

Why it works this way

Three ways to tell empty from full

With nothing but a head and a tail index there are three standard fixes. Keep a separate size counter, as the code here does. Leave one slot permanently unused, so full is (tail + 1) % capacity == head, which costs a slot but keeps all the state in the two indices. Or let head and tail count every item ever enqueued and dequeued, never wrapping, and apply the modulo only when indexing. The two index-only forms both suit a ring shared between a single producer and a single consumer, because each side writes only its own index and reads the other's, so no lock is needed on the fast path. The never-wrapping form is usually the one picked of the two: it uses every slot, and tail - head is the exact count rather than something that has to be reconstructed.

Why capacity is almost always a power of two

A % whose divisor the compiler cannot see is a real integer division, far slower than the arithmetic around it, on a path that is meant to be a handful of instructions. When capacity is a power of two, index & (capacity - 1) gives the same answer in one instruction. That is why the Linux kernel's circular buffer helpers, the CIRC_CNT and CIRC_SPACE macros, are defined only for power-of-two buffers, and why the LMAX Disruptor rejects a ring size that is not one. It also makes the never-wrapping counter form safe: an unsigned counter that rolls over at 2^32 lands exactly where the mask expects, because the capacity divides 2^32, so tail - head is still the correct count. In C or C++, declare those counters signed instead and the overflow is undefined behaviour, which is the classic bug in hand-rolled ring buffers.

Why dequeue writes null into the slot it just read

The queue works without that line: size already says the slot is free, and the next enqueue will overwrite it. But in a garbage collected language the array still holds a reference, so the queue keeps the object alive long after the consumer finished with it, and a long-lived queue quietly pins one dead object per slot. Java's ArrayBlockingQueue, which is a circular array queue with exactly this shape, clears the slot on every take for that reason, and ArrayDeque does the same when it removes an element.

What happens when it is full is a policy decision

Returning false is one answer. The other two are to overwrite the oldest item, advancing head along with the write index, which is what a log or telemetry ring does, and to block until a consumer frees a slot, which is the bounded buffer of the producer-consumer problem. Overwriting never stalls the producer but drops data silently. Blocking keeps every item but lets one slow consumer stall a fast producer. Picking the wrong one is how a monitoring agent ends up pausing the service it is supposed to be watching.

Read more

Next up

Deque

Push and pop at both ends

Next lesson: Deque