Circular buffers

Wrapping means index = (index + 1) % n: the index runs 0, 1, …, n-1, 0, 1, …. The remainder operator does the wrap in one expression, so no separate if (index == n) index = 0 is needed.

Two Java details matter. First, % keeps the sign of the dividend, so -1 % 5 is -1, not 4; when an index can go backwards (for example addFirst on a deque) use Math.floorMod(i - 1, n). Second, when n is a power of two, i & (n - 1) is the same as the floored modulo, even for negative i, and it is cheaper than a division.

1class RingQueue {
2    private final int[] data; private int head, tail, size;
3    RingQueue(int capacity) { data = new int[capacity]; }
4    boolean offer(int x) {
5        if (size == data.length) return false;              // full
6        data[tail] = x;
7        tail = (tail + 1) % data.length;                   // wrap around
8        size++; return true;
9    }
10    Integer poll() {
11        if (size == 0) return null;                         // empty
12        int x = data[head];
13        head = (head + 1) % data.length;                   // wrap around
14        size--; return x;
15    }
16}

head is the slot of the oldest value and tail is the slot where the next value will be written (one past the newest). Enqueue writes at tail then advances it; dequeue reads at head then advances it. Neither moves any data.

The live values are data[head], data[head + 1], … taken modulo n, for size values. The number of live values is not tail - head once the indices have wrapped, which is why a ring needs either a separate size, a spare slot, or a different index scheme.

1static int[] snapshot(int[] data, int head, int size) {
2    int[] live = new int[size];
3    for (int k = 0; k < size; k++) live[k] = data[(head + k) % data.length];   // oldest first
4    return live;
5}

1class RingQueue {
2    private final int[] data; private int head, tail, size;
3    RingQueue(int capacity) { data = new int[capacity]; }
4    boolean offer(int x) {
5        if (size == data.length) return false;              // full
6        data[tail] = x;
7        tail = (tail + 1) % data.length;                   // wrap around
8        size++; return true;
9    }
10    Integer poll() {
11        if (size == 0) return null;                         // empty
12        int x = data[head];
13        head = (head + 1) % data.length;                   // wrap around
14        size--; return x;
15    }
16}

When the ring is empty, head == tail. When it is completely full, the tail has wrapped all the way around and head == tail again. The indices alone cannot tell the two states apart, so every ring design picks one of three fixes.

The animation uses the second fix: allocate one slot more than the usable capacity and never fill it, so head == tail can only mean empty and (tail + 1) % n == head means full. Compare it with the size-counter version in the previous topic.

1class RingQueue {
2    private final int[] data; private int head, tail;       // one slot always stays empty
3    RingQueue(int capacity) { data = new int[capacity + 1]; }
4    boolean offer(int x) {
5        if ((tail + 1) % data.length == head) return false;   // full
6        data[tail] = x;
7        tail = (tail + 1) % data.length;                   // wrap around
8        return true;
9    }
10    Integer poll() {
11        if (head == tail) return null;                      // empty
12        int x = data[head];
13        head = (head + 1) % data.length;                   // wrap around
14        return x;
15    }
16}

A ring buffer has a fixed capacity chosen up front. When it is full there are two policies. **Reject**: offer returns false and the producer must wait or drop the new value, which is right for work queues. **Overwrite**: the new value replaces the oldest one, which is right when only the latest data matters, such as the last 100 log lines or sensor samples.

The overwriting variant needs no full test at all: write at tail, and if the buffer was full, advance head as well so that the oldest value is dropped.

1class LatestN {
2    private final int[] data; private int head, size;
3    LatestN(int capacity) { data = new int[capacity]; }
4    void add(int x) {
5        int tail = (head + size) % data.length;
6        data[tail] = x;
7        if (size == data.length) head = (head + 1) % data.length;   // full: the oldest value is overwritten
8        else size++;
9    }
10    int[] latest() {
11        int[] out = new int[size];
12        for (int k = 0; k < size; k++) out[k] = data[(head + k) % data.length];
13        return out;
14    }
15}

A ring buffer trades flexibility for predictability. Memory is allocated once, no operation ever allocates or copies, and every operation is O(1) in the worst case, which is why rings are used in audio pipelines, network drivers and logging.

The cost is the fixed capacity: choosing it too small drops or rejects data, too large wastes memory. A growing queue such as ArrayDeque never rejects, but a resize copies every element, so one operation can be O(n).