A circular buffer (or ring buffer) is a Queue with one rule change that makes a real
difference: capacity is fixed forever. Instead of growing a backing array when it fills up —
what the Dynamic Array underneath a queue or
stack does — a ring buffer wraps its write position back to index 0 once it runs off the end,
reusing slots a pop() already freed. Nothing ever reallocates. That trades away
"grows forever" for a stronger guarantee: push and pop are
O(1) every single time, not just on average.
Push values on, pop them off. Capacity is fixed at 5 — once it's full, the "on full" setting
below decides what happens next. The solid block is the head (next to come out
on pop); the outlined block is the tail (where the next
push lands). Fill it, pop a few, then push past capacity to watch the tail wrap
back around to slot 0.
x at the tail slot, then
advance tail one step (wrapping to 0 past the last index).
O(1). If the buffer is already full, behavior depends on the implementation:
reject the write, or overwrite the oldest element and advance head too.head slot, advance head one
step (same wraparound), return what was read. O(1).head slot without advancing it.
O(1).There's no get(i) or search — same restricted "only touch the two ends"
interface as a Queue, just backed by a fixed block
instead of a growable one.
class CircularBuffer {
#data;
#capacity;
#head = 0;
#tail = 0;
#count = 0; // disambiguates "empty" from "full" — see Pitfalls
constructor(capacity) {
this.#capacity = capacity;
this.#data = new Array(capacity);
}
isFull() { return this.#count === this.#capacity; }
isEmpty() { return this.#count === 0; }
push(x, overwrite = false) {
if (this.isFull()) {
if (!overwrite) throw new Error('overflow: buffer full');
this.#data[this.#tail] = x;
this.#tail = (this.#tail + 1) % this.#capacity;
this.#head = (this.#head + 1) % this.#capacity; // oldest slot just got clobbered
return;
}
this.#data[this.#tail] = x;
this.#tail = (this.#tail + 1) % this.#capacity;
this.#count++;
}
pop() {
if (this.isEmpty()) throw new Error('underflow: buffer empty');
const x = this.#data[this.#head];
this.#head = (this.#head + 1) % this.#capacity;
this.#count--;
return x;
}
}The % this.#capacity in both push and pop is the
entire trick — it's the same fixed-size array a plain Dynamic Array starts with, minus the
#grow() step. A slot a pop() just freed becomes writable again the
moment tail wraps back onto it, so the buffer can absorb an unlimited number of
pushes over its lifetime while the backing array itself never changes size.
head === tail is ambiguous — and it's the one bug every naive ring buffer ships
with. The classic shortcut implementation skips #count and just compares
head to tail: equal means empty. That works right up until the buffer
is completely full, at which point they're also equal, because tail has
wrapped exactly one full lap past head. Checked against the reference
implementation above with capacity 4, pushing four values in a row:
A naive head === tail → isEmpty check reports this completely full buffer as
empty — the next push then silently overwrites live data the caller thinks is
still there, and the next pop hands back a value from a slot that was never
actually written in that lap. Tracking #count explicitly (or, the classic
alternative, deliberately wasting one slot and treating "one slot short of a full lap" as the
full condition) is what avoids it — the demo above and the reference implementation both use
the counter.
Overwrite mode has to move head, not just tail.
When a full buffer overwrites the oldest element, that element is gone — if head
stays put, pop() next returns the value that just got clobbered by the
overwriting push, not the item that was actually oldest going into that call.
The reference implementation advances both pointers together in the overflow branch for exactly
this reason; try it live above with overwrite enabled, fill the buffer, push once more, then pop
— the value that comes back is the second-oldest survivor, not the one that was just erased.
Reject vs. overwrite is a real design choice, not a default to leave unmade. A sensor sampling buffer usually wants overwrite — the newest reading matters more than one from several seconds ago, and losing old data silently is fine. A command queue usually wants reject — losing a command silently is a bug, and the caller needs to know the buffer is backed up before more work piles in. Picking the wrong one for the situation is a correctness bug that only shows up under load, once the buffer actually fills.
dmesg ring
buffer holds a fixed amount of the most recent kernel log output; once it's full, the oldest
lines are silently dropped to make room for new ones rather than letting logging consume
unbounded memory.Time: push, pop, and peek are all
O(1) — worst case, not just amortized, since there is no reallocation step to pay
for. This is the one guarantee a ring buffer gives that a growable Queue or Dynamic Array can't quite match. Search or
indexed access is O(n) and not part of the sanctioned interface anyway.
Space: exactly O(capacity), fixed at construction — and unlike a
dynamic array, that number is a hard ceiling, not a floor that grows to accommodate more data.
This site's guide, Choosing a Linear Data Structure, compares this entry against the other six Linear structures side by side.