Kas yra žiedinis buferis (ring buffer) ir kada jūs jį naudotumėte?

Question

Accepted Answer

**Žiedinis buferis** yra fiksuoto dydžio masyvas, kuris yra traktuojamas taip, tarsi jo galai būtų sujungti į žiedą. Du indeksai — **head** (skaitymas) ir **tail** (rašymas) — judėja ir susukami naudojant modulio aritmetiką, suteikiant O(1) FIFO eilę su **jokios išdėstymo** po sukūrimo.

## Kaip veikia suvyniojimas

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

| Operacija | Laikas |
|---|---|
| enqueue / dequeue | O(1) |
| vieta | O(n) fiksuota |

## Kada naudoti

- **Srautų / garso / vaizdo buferiai** — riboti, pastovus pralaidumas.
- **Gamintojo–vartotojo** konvejerai su atbuline slėgiu.
- **Paskutinių N įvykių žurnalas** (perrašyti seniausius).

## Kodėl tai svarbu

Žiedinis buferis suteikia nuspėjamą, išdėstymo nereikalingą FIFO elgesį, kuris yra būtinas realaus laiko ir įterptose sistemose, kuriose dinaminis išdėstymas yra per lėtas arba per rizikingas.

Jo ribota dydžio taip pat yra natūrali atbuline slėgio jėga, kuri neleidžia greitiems gamintojams išeikoti atminties.