Cirkulær buffer (ringbuffer)

Lineær

En buffer med fast størrelse der bruger et enkelt array af fast størrelse 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

Cirkulær buffer, også kaldet ringbuffer eller cyklisk 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 pointere: head (læseposition) og tail (skriveposition). Når tail når slutningen af arrayet, wrapper den rundt til starten - deraf navnet cirkulær. Dette eliminerer behovet for at flytte elementer når vi fjerner fra front, hvilket gør enqueue og dequeue til O(1) operationer. Cirkulære buffere er utroligt populære i indlejrede systemer, audio/video-streaming, netværksbuffere og producent-forbruger-problemer fordi de har forudsigelig hukommelsesfodaftryk, ingen dynamisk allokerings-overhead og fremragende cache-lokalitet. De kommer i to varianter: overskrivningstilstand hvor nye data overskriver gamle når bufferen er fuld, og blokerende tilstand hvor skrivninger fejler/venter når den er fuld. Cirkulære buffere bruges massivt i hardwaredrivere, realtidssystemer og applikationer med lav latenstid.

Kode Eksempel

// JavaScript Circular Buffer Implementation
class CircularBuffer {
  constructor(capacity) {
    this.capacity = capacity;
    this.buffer = new Array(capacity);
    this.head = 0; // Læseposition
    this.tail = 0; // Skriveposition
    this.size = 0; // Nuværende antal elementer
  }

  // Tilføj element til buffer
  enqueue(item) {
    this.buffer[this.tail] = item;
    this.tail = (this.tail + 1) % this.capacity;
    
    if (this.size < this.capacity) {
      this.size++;
    } else {
      // Buffer fuld, overskrivningstilstand: flyt head
      this.head = (this.head + 1) % this.capacity;
    }
  }

  // Fjern og returner element fra buffer
  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    
    const item = this.buffer[this.head];
    this.buffer[this.head] = undefined; // Ryd reference
    this.head = (this.head + 1) % this.capacity;
    this.size--;
    
    return item;
  }

  // Kig på front-element uden at fjerne
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.buffer[this.head];
  }

  // Tjek om buffer er tom
  isEmpty() {
    return this.size === 0;
  }

  // Tjek om buffer er fuld
  isFull() {
    return this.size === this.capacity;
  }

  // Få nuværende størrelse
  getSize() {
    return this.size;
  }

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

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

// Tilføj elementer
buffer.enqueue('A');
buffer.enqueue('B');
buffer.enqueue('C');
console.log('Buffer:', buffer.toArray()); // ['A', 'B', 'C']

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

Anvendelsesområder

-Audio/video-streamingbuffere
-Netværkspakkebuffere
-Producent-forbruger-problemer
-Tastatur/mus-inputbuffere
-Realtidsdatalogning

Fordele

+O(1) enqueue og dequeue
+Fast hukommelsesfodaftryk - ingen allokering
+Fremragende cache-lokalitet
+Perfekt til indlejrede systemer
+Låsefri implementering mulig

Ulemper

-Fast kapacitet - kan ikke vokse
-Kan overskrive data når fuld (i overskrivningstilstand)
-Spild af plads hvis ikke fuldt udnyttet
-Modulo-operation kan være langsom på nogle CPU'er
-Kompleksitet ved størrelsesændring (kræver ny buffer)

Eksempler fra den virkelige verden

-Audiodriverbuffere i styresystemer
-UART-modtagebuffere i indlejrede systemer
-Videorammebuffere i streaming
-Netværkskort modtage/sende-ringe
-Tastaturinputbuffer (typeahead)

Relaterede strukturer

QueueArrayDequeBounded Queue