Skip to content
Tutorials Center
My learning

Topics

Lesson 49 of 225 ยท Stacks and Queues

Circular Queue and Ring Buffer

Build a circular queue (ring buffer) in Python with a fixed-size array, wrap-around head and tail, full and empty detection, overwriting mode and real uses.

A queue backed by a fixed-size array has an annoying problem. Items enter at the back and leave at the front, so the used part of the array creeps to the right. After a while the back reaches the end of the array even though the front slots are empty again. Shifting everything left would cost O(n) per dequeue, which defeats the point.

The fix is to treat the array as a circle. When an index runs off the right end, it wraps around to slot 0. The result is a circular queue, also called a ring buffer: a queue with a fixed memory footprint and O(1) enqueue and dequeue, with no shifting and no allocation. It is how keyboards, network cards, audio pipelines and logging systems buffer data.

The picture

TEXT
capacity = 6, after some activity

index:     0    1    2    3    4    5
         [ . ][ . ][ C ][ D ][ E ][ . ]
                     ^              ^
                    head           tail (next free slot)

enqueue F -> goes in slot 5, tail wraps to 0
         [ . ][ . ][ C ][ D ][ E ][ F ]
            ^        ^
           tail     head

enqueue G -> goes in slot 0, tail becomes 1
         [ G ][ . ][ C ][ D ][ E ][ F ]
                 ^   ^
              tail  head

Two indexes drive everything:

  • head: the index of the front item (the next to leave).
  • tail: the index where the next item will be written.

Both move forward only, and both use modular arithmetic to wrap: index = (index + 1) % capacity.

The full-versus-empty puzzle

When head == tail, is the queue empty or completely full? Both situations give the same two indexes, so you need one more piece of information. There are two classic solutions.

Solution A: keep a count. Store size. Empty means size == 0, full means size == capacity. All slots are usable. This is the simplest and what we will use.

Solution B: leave one slot unused. Declare the queue full when (tail + 1) % capacity == head. Empty is head == tail. This wastes one slot but needs no counter, which matters in lock-free code where two threads own different indexes.

Approach Empty test Full test Usable slots
Size counter size == 0 size == capacity capacity
One slot wasted head == tail (tail + 1) % capacity == head capacity - 1

Implementation with a size counter

Python Circular queue with a fixed-size list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second printed array shows the wrap-around: the new items 50 and 60 live at the start of the array while the older items 30 and 40 sit at the end, yet they leave in the right order.

Tracing the indexes

For capacity 4, the sequence enqueue 10, 20, 30, 40, dequeue, dequeue, enqueue 50, enqueue 60 looks like this:

TEXT
operation     data                    head size tail
enqueue 10    [10, -,  -,  - ]         0    1    1
enqueue 20    [10, 20, -,  - ]         0    2    2
enqueue 30    [10, 20, 30, - ]         0    3    3
enqueue 40    [10, 20, 30, 40]         0    4    0   (tail wrapped; queue full)
dequeue  ->10 [-,  20, 30, 40]         1    3    0
dequeue  ->20 [-,  -,  30, 40]         2    2    0
enqueue 50    [50, -,  30, 40]         2    3    1
enqueue 60    [50, 60, 30, 40]         2    4    2   (full again)

Notice that tail is never stored. It is computed as (head + size) % capacity. One fewer variable means one fewer thing to keep consistent.

Why modulo and not an if-statement?

(i + 1) % capacity is correct for every slot, including the last one. Newcomers often write if i == capacity - 1: i = 0 else: i += 1, which works too. A modulo is shorter and extends to "advance by k": (i + k) % capacity. When the capacity is a power of two, & (capacity - 1) does the same job with a single bitwise instruction, a trick used in high-performance buffers.

Overwrite mode: keep the latest N items

Sometimes you do not want an error when the buffer is full. A log viewer that shows only the last 100 lines, or an audio buffer that must never block, prefers to drop the oldest item and accept the new one. The only change is in enqueue: when full, advance head to discard the front item.

Python Overwriting ring buffer: the last N items

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python's own tool for this is collections.deque(maxlen=n), which drops from the opposite end automatically:

Python deque with maxlen as a ring buffer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity

Operation Time Notes
enqueue O(1) one write, one modulo
dequeue O(1) one read, one modulo
peek, is_empty, is_full O(1)
Space O(capacity) allocated once, never grows

Compare with the naive array queue, where each dequeue shifts n items (see queues). The circular version trades flexibility (a fixed capacity) for speed and a predictable memory footprint.

Making it growable

If the capacity must not be a hard limit, you can resize when full: allocate an array twice as large, copy the items in logical order (starting from head, not from index 0), reset head to 0, and continue. The copy is O(n) but happens rarely, so enqueue stays amortized O(1), exactly the same argument as for dynamic arrays. Forgetting to copy in logical order is the most common bug here: copying the raw array leaves the items scrambled whenever the buffer has wrapped.

Common mistakes

  • Mixing up full and empty when only head and tail are stored. Use a counter or sacrifice a slot.
  • Forgetting the modulo on one of the two indexes, which leads to IndexError after the first wrap.
  • Computing the tail from the wrong formula. The tail is (head + size) % capacity, not head + size - 1.
  • Resizing by copying the raw array, which scrambles the order after a wrap.
  • Reading garbage: slots outside the live range hold stale data. Clear them on dequeue or never read them.

Where it is used

  • Producer-consumer buffers: keyboard input, sensor data, audio and video frames.
  • Network stacks: packet queues in drivers and sockets.
  • Fixed-memory logging: the last N events before a crash.
  • Sliding statistics: the last k samples for a moving average.
  • Scheduling: round-robin rotation of a fixed set of tasks (compare circular linked lists).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What problem does a circular queue solve compared with a plain array queue?

    By wrapping indexes around the end of the array, slots freed at the front become available again with no shifting.
  2. 2. With capacity 5, head = 3 and size = 4, where will the next item be written?

    tail = (head + size) % capacity = (3 + 4) % 5 = 2.
  3. 3. If you store only head and tail and they are equal, what is ambiguous?

    Both an empty queue and a completely full queue produce head == tail, so you need a counter or a deliberately unused slot.
  4. 4. What does an overwriting ring buffer do when it is full and a new item arrives?

    It advances head past the oldest item, so the buffer always holds the most recent capacity items.
  5. 5. When growing a full circular queue, how must the items be copied to the larger array?

    After a wrap, raw index order is not queue order. Copy from head, wrapping around, then set head to 0.

Summary

  • A circular queue stores items in a fixed array and wraps head and tail with % capacity, giving O(1) enqueue and dequeue with no shifting.
  • Distinguish full from empty with a size counter (simplest) or by leaving one slot unused.
  • tail = (head + size) % capacity can be computed instead of stored.
  • An overwriting ring buffer keeps the latest N items; deque(maxlen=n) does the same in Python.
  • To grow the buffer, copy in logical order from head and reset head to 0.

Next: Deques and Monotonic Queues