Pointer Walk

Ring Buffers

A queue that never moves its data: a circle of slots with a head and a tail chasing each other.

Data StructuresBeginner7 min read

A queue in an array

A queue takes items in at the back and hands them out at the front, in the order they arrived. The obvious way to build one is an array: add at the end, remove from the start.

The trouble is the removing. Take the first item out of an array and every other item has to shift down one place to close the gap. With a thousand items, that is a thousand moves for one removal.

A ring buffer (also called a circular buffer) is a queue that never moves its data. Instead of shifting the items, it moves two markers.

Two markers chasing each other

  1. Use a fixed array and treat it as a circle

    After the last slot comes the first slot again.

  2. tail marks where the next item is written

    Write there, then move tail one step forward.

  3. head marks the oldest item

    Read from there, then move head one step forward.

  4. When a marker passes the last slot, it wraps to slot 0

    Slots that were read are free again, so the writing just continues around.

A ring buffer with 8 slotsInteractive
0headtail
1
2
3
4
5
6
7

Start. Eight slots in a circle, all empty. head marks the oldest item (the next to be read). tail marks where the next write goes.

Items
0 / 8
head (read here)
slot 0
tail (write here)
slot 0

Watch one written item. From the moment it is stored until it is read, it never changes slot. Only head and tail move, and each moves one step per operation.

The wrap-around is one line of arithmetic: the remainder after dividing by the size.

python
class RingBuffer:
    def __init__(self, size):
        self.slots = [None] * size
        self.head = 0      # oldest item
        self.tail = 0      # next free slot
        self.count = 0

    def write(self, item):
        self.slots[self.tail] = item
        self.tail = (self.tail + 1) % len(self.slots)     # wrap around
        if self.count == len(self.slots):
            self.head = self.tail                         # full: the oldest was overwritten
        else:
            self.count += 1

    def read(self):
        item = self.slots[self.head]
        self.head = (self.head + 1) % len(self.slots)
        self.count -= 1
        return item

What happens when it is full

When tail catches up with head, every slot is in use. There are two reasonable things to do, and which one is right depends on the data.

When fullBehaviourGood for
Overwrite the oldestThe newest data always fits. Old data is lostLogs, audio, sensor readings, "the last 100 events"
Refuse the writeNothing is lost. The writer must waitWork queues where every item matters

The animation overwrites. The second choice is the queue limit described in Queues and Backpressure.

Good at

  • Add and remove in one step each, with nothing shifted or copied
  • Memory is allocated once and never grows
  • Items sit side by side, which processors read quickly

Where it bites

  • The size is fixed in advance
  • When it is full you must lose data or make the writer wait

Where you will meet it

  • Audio and video: the sound card reads samples from one end while the program writes them at the other.
  • Network cards and keyboards: incoming data waits in a ring until the program collects it.
  • Logging "the last N things": overwrite mode keeps recent history in fixed memory.

Key takeaways

  • A ring buffer is a queue in a fixed array that is treated as a circle.
  • Writes happen at tail and reads at head. Both markers move forward and wrap around.
  • The stored items never move, so both operations take one step.
  • When tail meets head it is full: overwrite the oldest, or make the writer wait.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    6 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress