Circular buffers

A circular buffer is a queue kept in a list of fixed size. When it reaches the end of the list, it carries on from the start. Nothing ever moves, and the memory never grows.

A queue in a fixed list

Lesson 3 showed that a list is a slow queue because items move when the front one leaves. A different plan: let the items stay where they are, and move a marker instead. Keep two numbers:

• head: the place of the front item;
• count: how many items are in the queue.

To leave, read the item at head and move head one place on. To join, write the item just after the last one. But the markers only ever move forwards, so they soon reach the end of the list, even if the start of the list is empty again.

Wrapping round with %

The answer is to treat the list as a circle: after the last place comes place 0 again. The % operator (remainder after division) does this. With a list of size cap, the place after k is (k + 1) % cap. For k = cap - 1 this is 0.

So the next free place is (head + count) % cap. Step through a buffer of 6 slots. Watch the pushes wrap round to the start:

Here is push. The buffer keeps a list slots of size cap, and the two numbers:

def push(self, x):
    if self.count == len(self.slots):
        return False                  # full
    free = (self.head + self.count) % len(self.slots)
    self.slots[free] = x
    self.count += 1
    return True

pop works the other way round. If count is 0, return None. Otherwise read the item at head, set that slot to None, move head one place on with %, and take 1 from count. Setting the slot to None is not needed for correctness, but it lets Python free a large item as soon as it leaves. STAQ-P4 asks you to write the whole class.

Every operation is a few sums and one list access: O(1), with no exceptions and no growing.

Full or empty?

When the buffer is full, the next free place (head + count) % cap is head itself. When it is empty, it is also head. So the two places alone cannot tell full from empty. Keeping count solves this.

What should happen on a push when the buffer is full? There are two usual choices:

• Refuse it, as above: the caller must wait. Used where no item may be lost.
• Overwrite the oldest item: write at head, then move head on. Used for “the last 1,000 readings”. This is what deque(maxlen=n) does.

Where they are used

Circular buffers are used wherever data flows at a steady rate and memory must stay fixed: sound and video playback, keyboard input, network cards, and logs that keep only recent lines. They need no memory after they are created, which matters in small devices.

Now try STAQ-P4, A ring of platforms.