Hvad er en cirkulær buffer (ring buffer) og hvornår ville du bruge en?

Question

Accepted Answer

En **cirkulær buffer** er et array med fast størrelse, som behandles som om dets ender er forbundet til en ring. To indekser — **head** (læsning) og **tail** (skrivning) — rykker frem og vikler rundt ved hjælp af modulo-aritmetik, hvilket giver en O(1) FIFO-kø med **ingen allokering** efter oprettelse.

## Hvordan ombrydning 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)
```

## Code

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

| Handling | Tid |
|---|---|
| enqueue / dequeue | O(1) |
| space | O(n) fast |

## Hvornår man bruger det

- **Streaming- / lyd- / videobuffere** — afgrænset, stabil gennemstrømning.
- **Producent–forbruger** rørledninger med backpressure.
- **Logning af de sidste N begivenheder** (overskrivning af ældste).

## Hvorfor det er vigtigt

En ring buffer giver forudsigeligt, allokeringsfrit FIFO-adfærd, som er vigtig i realtids- og indlejrede systemer, hvor dynamisk allokering er for langsom eller risikabel.

Dens begrænsede størrelse fungerer også som naturlig backpressure, der forhindrer hurtige producenter i at opbruge hukommelsen.