Was ist ein zirkulärer Puffer (Ring Buffer) und wann würde man einen verwenden?

Question

Accepted Answer

Ein **zirkulärer Puffer** ist ein Array mit fester Größe, das so behandelt wird, als würden seine Enden zu einem Ring verbunden. Zwei Indizes — **head** (Lesen) und **tail** (Schreiben) — rücken vor und umwickeln sich mit Modulo-Arithmetik, was eine O(1) FIFO-Warteschlange mit **keiner Speicherallokation** nach der Erstellung ergibt.

## Wie das Umwickeln funktioniert

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

| Operation | Zeit |
|---|---|
| enqueue / dequeue | O(1) |
| space | O(n) fest |

## Wann man es verwendet

- **Streaming- / Audio- / Videopuffer** — begrenzt, gleichmäßiger Durchsatz.
- **Produzent–Konsument** Pipelines mit Backpressure.
- **Protokollierung der letzten N Ereignisse** (älteste überschreiben).

## Warum es wichtig ist

Ein Ring Buffer bietet vorhersehbares, allokationsfreies FIFO-Verhalten, das in Echtzeit- und eingebetteten Systemen essentiell ist, wo dynamische Speicherallokation zu langsam oder riskant ist.

Seine begrenzte Größe wirkt auch als natürliche Backpressure und verhindert, dass schnelle Produzenten den Speicher erschöpfen.