Hva er en circular buffer (ring buffer) og når ville du brukt en?

Question

Accepted Answer

En **circular buffer** er en array med fast størrelse som behandles som om endene er sammenføyd til en ring. To indekser — **head** (lesing) og **tail** (skriving) — avanserer og omslutter ved hjelp av modulo-aritmetikk, noe som gir en O(1) FIFO-kø **uten tildeling** etter opprettelse.

## Hvordan omslutning fungerer

```text
capacity 5, after writing A,B,C,D and reading A,B:
index:  0   1   2   3   4
      [ . ][ . ][ C ][ D ][ . ]
              head^       tail^   (tail wraps to 0 next write)
```

## Kode

```python
class RingBuffer:
    def __init__(self, n):
        self.buf = [None]*n
        self.head = self.tail = self.size = 0
        self.cap = n
    def enqueue(self, x):                  # O(1)
        if self.size == self.cap: raise Exception("full")
        self.buf[self.tail] = x
        self.tail = (self.tail + 1) % self.cap   # wrap
        self.size += 1
    def dequeue(self):                     # O(1)
        x = self.buf[self.head]
        self.head = (self.head + 1) % self.cap    # wrap
        self.size -= 1
        return x
```

| Operasjon | Tid |
|---|---|
| enqueue / dequeue | O(1) |
| plass | O(n) fast |

## Når du skal bruke det

- **Streaming / lyd / video-buffere** — begrenset, jevn gjennomstrømning.
- **Producer–consumer** rørledninger med mottrykk.
- **Logging de siste N hendelsene** (overskriv eldste).

## Hvorfor det er viktig

En ring buffer gir forutsigbar, tildeling-fri FIFO-atferd, som er essensiell i sanntids- og innebygde systemer der dynamisk tildeling er for sakte eller risikabel.

Den begrensede størrelsen fungerer også som naturlig mottrykk, noe som hindrer raske produsenter fra å bruke opp minne.