Circular Buffer (Ring Buffer)

Lineær

En fast-størrelse buffer der bruger et enkelt, fixed-size array som om enderne var forbundet i en ring.

Kompleksitet

Operation	Tidskompleksitet
Access	`O(1)`
Search	`O(n)`
Insertion	`O(1) enqueue`
Deletion	`O(1) dequeue`

Beskrivelse

Circular Buffer, også kaldet Ring Buffer eller Cyclic Buffer, er en elegant datastruktur der effektivt implementerer en FIFO (First-In-First-Out) kø med fast kapacitet. Den bruger et array af fast størrelse og to pointers: head (read position) og tail (write position). Når tail når slutningen af arrayet, wrapper den rundt til starten - deraf navnet circular. Dette eliminerer behovet for at flytte elementer når vi fjerner fra front, hvilket gør enqueue og dequeue O(1) operationer. Circular Buffers er utroligt populære i embedded systems, audio/video streaming, network buffers, og producer-consumer problems fordi de har forudsigelig memory footprint, ingen dynamic allocation overhead, og excellent cache locality. De kommer i to varianter: overwrite mode hvor nye data overskriver gamle når bufferen er fuld, og blocking mode hvor writes fejler/venter når fuld. Circular Buffers bruges massivt i hardware drivers, real-time systems, og low-latency applications.

Kode Eksempel

// JavaScript Circular Buffer Implementation
class CircularBuffer {
  constructor(capacity) {
    this.capacity = capacity;
    this.buffer = new Array(capacity);
    this.head = 0; // Read position
    this.tail = 0; // Write position
    this.size = 0; // Current number of elements
  }

  // Add element to buffer
  enqueue(item) {
    this.buffer[this.tail] = item;
    this.tail = (this.tail + 1) % this.capacity;
    
    if (this.size < this.capacity) {
      this.size++;
    } else {
      // Buffer full, overwrite mode: move head
      this.head = (this.head + 1) % this.capacity;
    }
  }

  // Remove and return element from buffer
  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    
    const item = this.buffer[this.head];
    this.buffer[this.head] = undefined; // Clear reference
    this.head = (this.head + 1) % this.capacity;
    this.size--;
    
    return item;
  }

  // Peek at front element without removing
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.buffer[this.head];
  }

  // Check if buffer is empty
  isEmpty() {
    return this.size === 0;
  }

  // Check if buffer is full
  isFull() {
    return this.size === this.capacity;
  }

  // Get current size
  getSize() {
    return this.size;
  }

  // Get capacity
  getCapacity() {
    return this.capacity;
  }

  // Clear buffer
  clear() {
    this.head = 0;
    this.tail = 0;
    this.size = 0;
    this.buffer.fill(undefined);
  }

  // Convert to array (for debugging)
  toArray() {
    const result = [];
    let count = this.size;
    let index = this.head;
    
    while (count > 0) {
      result.push(this.buffer[index]);
      index = (index + 1) % this.capacity;
      count--;
    }
    
    return result;
  }
}

// Non-overwriting variant (throws when full)
class BoundedCircularBuffer extends CircularBuffer {
  enqueue(item) {
    if (this.isFull()) {
      throw new Error('Buffer is full');
    }
    
    this.buffer[this.tail] = item;
    this.tail = (this.tail + 1) % this.capacity;
    this.size++;
  }
}

// Brug
const buffer = new CircularBuffer(5);

// Add elements
buffer.enqueue('A');
buffer.enqueue('B');
buffer.enqueue('C');
console.log('Buffer:', buffer.toArray()); // ['A', 'B', 'C']

// Remove elements
console.log('Dequeue:', buffer.dequeue()); // 'A'
console.log('Buffer:', buffer.toArray()); // ['B', 'C']

// Add more elements
buffer.enqueue('D');
buffer.enqueue('E');
buffer.enqueue('F');
buffer.enqueue('G');
console.log('Buffer:', buffer.toArray()); // ['C', 'D', 'E', 'F', 'G']
console.log('Is full:', buffer.isFull()); // true

// Overwrite mode: adding more overwrites oldest
buffer.enqueue('H');
console.log('Buffer:', buffer.toArray()); // ['D', 'E', 'F', 'G', 'H']

// Producer-Consumer Example
function producerConsumerExample() {
  const buffer = new CircularBuffer(3);
  
  // Producer adds data
  const produce = (data) => {
    console.log(`Producing: ${data}`);
    buffer.enqueue(data);
  };
  
  // Consumer reads data
  const consume = () => {
    if (!buffer.isEmpty()) {
      const data = buffer.dequeue();
      console.log(`Consuming: ${data}`);
      return data;
    }
    console.log('Buffer empty');
    return null;
  };
  
  produce(1);
  produce(2);
  consume(); // 1
  produce(3);
  produce(4);
  consume(); // 2
  consume(); // 3
  consume(); // 4
  consume(); // Buffer empty
}

producerConsumerExample();

Anvendelsesområder

•Audio/video streaming buffers
•Network packet buffers
•Producer-consumer problems
•Keyboard/mouse input buffers
•Real-time data logging

Fordele

✓O(1) enqueue og dequeue
✓Fast memory footprint - ingen allocation
✓Excellent cache locality
✓Perfekt til embedded systems
✓Lock-free implementation mulig

Ulemper

✗Fast kapacitet - kan ikke vokse
✗Kan overskrive data når fuld (i overwrite mode)
✗Waste af space hvis ikke fuldt udnyttet
✗Modulo operation kan være langsom på nogle CPUs
✗Kompleksitet ved resizing (kræver ny buffer)

Eksempler fra den virkelige verden

•Audio driver buffers i operativsystemer
•UART receive buffers i embedded systems
•Video frame buffers i streaming
•Network card receive/transmit rings
•Keyboard input buffer (typeahead)

Relaterede strukturer

QueueArrayDequeBounded Queue