Back to Catalog
Data Structures
Fixed-Capacity Buffers
Circular Buffer (Ring Buffer)
Fixed-size array that wraps around — O(1) enqueue and dequeue with no allocation.
Intent & Description
Real-world Use Case
Audio processing — a ring buffer holds 4096 samples. Hardware writes new samples, DSP thread reads them. No allocation, no GC, deterministic latency. OS kernel networking — sk_buff ring buffer for packet I/O. Log rotation — circular buffer of the last N log lines, always O(1) to append.
Source
📌 TL;DR
Circular Buffer = fixed-size queue with zero allocations. Pre-allocate once, reuse forever. O(1) enqueue/dequeue, cache-friendly, GC-free. The go-to for audio, networking, and real-time data pipelines with known max throughput.
Advantages
- Zero allocations after init — no GC pressure, deterministic performance
- Cache-friendly — contiguous pre-allocated array, sequential access pattern
- O(1) enqueue and dequeue with no pointer chasing
- Fixed memory footprint — safe for memory-constrained embedded and real-time systems
Disadvantages
- Fixed capacity — overflow requires either blocking, overwriting oldest, or rejecting new entries
- More complex to implement correctly than a simple linked-list queue
- Not suitable when queue size is genuinely unbounded
- Full/empty detection requires careful pointer arithmetic (off-by-one is the classic bug)
Implementation Example
// ─── Circular Buffer (Ring Buffer) ───────────────────────────
class CircularBuffer {
#buffer;
#capacity;
#head = 0; // Read pointer (next position to dequeue)
#tail = 0; // Write pointer (next position to enqueue)
#count = 0;
constructor(capacity) {
this.#capacity = capacity;
this.#buffer = new Array(capacity); // Pre-allocated — no further allocations
}
// O(1) — Write at tail, advance tail with wrap-around
enqueue(value) {
if (this.isFull()) throw new Error('Buffer full');
this.#buffer[this.#tail % this.#capacity] = value;
this.#tail++;
this.#count++;
}
// O(1) — Read from head, advance head with wrap-around
dequeue() {
if (this.isEmpty()) throw new Error('Buffer empty');
const value = this.#buffer[this.#head % this.#capacity];
this.#buffer[this.#head % this.#capacity] = undefined; // Help GC
this.#head++;
this.#count--;
return value;
}
peek() { return this.isEmpty() ? null : this.#buffer[this.#head % this.#capacity]; }
isFull() { return this.#count === this.#capacity; }
isEmpty() { return this.#count === 0; }
get size() { return this.#count; }
// Overwriting variant — discard oldest on overflow (useful for log buffers)
enqueueOverwrite(value) {
if (this.isFull()) {
this.#head++; // Discard oldest
this.#count--;
}
this.enqueue(value);
}
}
// ─── Usage: Fixed-size sliding log buffer ────────────────────
const logBuffer = new CircularBuffer(5);
for (let i = 1; i <= 7; i++) logBuffer.enqueueOverwrite(`log_${i}`);
// Buffer holds last 5: log_3, log_4, log_5, log_6, log_7
const results = [];
while (!logBuffer.isEmpty()) results.push(logBuffer.dequeue());
console.log(results); // ['log_3', 'log_4', 'log_5', 'log_6', 'log_7']
// ─── Real-world: Audio DSP simulation ────────────────────────
const audioBuffer = new CircularBuffer(4096);
// Producer (hardware interrupt): audioBuffer.enqueue(sample)
// Consumer (DSP thread): const sample = audioBuffer.dequeue()
// Both run independently — no allocation, no GC, deterministic latency