Ring Buffers: A Queue in a Fixed Array

Head and tail wrap round to index 0, so neither enqueue nor dequeue ever shifts.

A ring buffer is a queue stored in an array of fixed size, in which the positions of the front and the back move round the array and wrap from the last index to index 0, so no operation ever shifts an element. This card covers its two indexes, the arithmetic that wraps them, and how it tells a full buffer from an empty one.

A keyboard driver, the code that receives keystrokes from the hardware, collects them faster than a program may read them, into a fixed block of memory, and the first key pressed must be read first. It needs a queue, but dequeuing from the front of an array would shift every waiting key, and a linked list would ask for new memory with every key.

A ring buffer keeps an array whose size, its capacity, never changes, and two indexes into it. head is the slot holding the front item, the next to dequeue, and tail is the slot the next enqueue will write. An enqueue writes into tail and moves it on, and a dequeue reads from head and moves it on. Moving on means adding one and taking the remainder after dividing by the capacity, written (index + 1) % capacity, so from the last slot an index moves to slot 0. A third number, count, records how many items the buffer holds.

A run took a buffer of capacity 5 from empty through four enqueues, two dequeues and two more enqueues.

Before the trace: after those eight operations, which slot holds the 6?

Slot 0. The 5 fills slot 4, the last one, so tail wraps round to 0 and the 6 is written there.

In the trace, _ is an empty slot, and head and tail mark the two indexes:

A ring buffer of capacity 5

Inputenqueue 1, 2, 3, 4; dequeue twice; enqueue 5, 6

Start: empty, count 0
1. _headtail
2. _
3. _
4. _
5. _
Five slots, all empty. head is the slot to dequeue from and tail the slot to write next.
Enqueue 1, count 1
1. 1head
2. _tail
3. _
4. _
5. _
1 goes into slot 0, and tail moves to (0 + 1) mod 5 = 1.
Enqueue 2, count 2
1. 1head
2. 2
3. _tail
4. _
5. _
2 goes into slot 1.
Enqueue 3, count 3
1. 1head
2. 2
3. 3
4. _tail
5. _
3 goes into slot 2.
Enqueue 4, count 4
1. 1head
2. 2
3. 3
4. 4
5. _tail
4 goes into slot 3, and only slot 4 is free.
Dequeue returns 1, count 3
1. _
2. 2head
3. 3
4. 4
5. _tail
Dequeue reads slot 0 and moves head to 1. Nothing shifts.
Dequeue returns 2, count 2
1. _
2. _
3. 3head
4. 4
5. _tail
Dequeue reads slot 1 and moves head to 2. Slots 0 and 1 are free again.
Enqueue 5, count 3
1. _tail
2. _
3. 3head
4. 4
5. 5
5 goes into slot 4, and tail wraps: (4 + 1) mod 5 = 0.
Enqueue 6, count 4
1. 6
2. _tail
3. 3head
4. 4
5. 5
6 goes into slot 0: first in the array, but last in the queue, behind 3, 4 and 5.

ResultThe queue holds 3 4 5 6 from front to back, and 6 sits in slot 0 because the tail wrapped round.

In general, a ring buffer turns an array into a queue whose every operation is O(1), because only the two indexes move. Its price is the fixed capacity: once count equals the capacity, an enqueue has nowhere to write, and the buffer must refuse it or overwrite the oldest item. The count is also what tells full from empty, because in both states head equals tail. The same run enqueued 7 into slot 1, which filled the buffer with head and tail both at 2, and then refused an eighth item with an error.

A queue that must grow without limit is not a fixed ring buffer: Java's ArrayDeque wraps its indexes in the same way, but copies its items into a larger array when it fills. Where the capacity is known and memory must not grow, as in keyboard, audio and network drivers, the ring buffer is the queue to use.

On the Data Structures cheatsheet

← → move through sections and cards