Vad är en cirkulär buffert (ring buffer) och när skulle du använda en?

Question

Accepted Answer

En **cirkulär buffert** är en array med fast storlek som behandlas som om dess ändar är sammanslutna i en ring. Två index — **head** (läsning) och **tail** (skrivning) — framåtgår och lindas runt med moduloaritmetik, vilket ger en O(1) FIFO-kö utan **allokeringar** efter skapandet.

## Hur lindning fungerar

```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)
```

## Kod

```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
```

| Operation | Tid |
|---|---|
| enqueue / dequeue | O(1) |
| utrymme | O(n) fixerat |

## När du ska använda det

- **Streaming / audio / video buffers** — begränsade, jämn genomströmning.
- **Producent–konsument** pipelines med motövertryck.
- **Loggning av de senaste N händelserna** (skriv över äldsta).

## Varför det är viktigt

En ringbuffert ger förutsebar, allokeringsfri FIFO-beteende, vilket är väsentligt i realtids- och inbäddade system där dynamisk allokering är för långsam eller riskabel.

Its begränsade storlek fungerar också som naturligt motövertryck, vilket förhindrar snabba producenter från att förbruka minnet.