Mi a körkörös puffer (ring buffer) és mikor használnál egyet?

Question

IT Interview Practice · Accepted Answer

A **körkörös puffer** egy fix méretű tömb, amelyet úgy kezelünk, mintha a végei egy gyűrűbe lennének összekapcsolva. Két index — **head** (olvasás) és **tail** (írás) — előre halad és burkolódik körül modulo aritmetika segítségével, O(1) FIFO sorral adva **nincs allokáció** a létrehozás után.

## Hogyan működik a burkolás

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

| Művelet | Idő |
|---|---|
| enqueue / dequeue | O(1) |
| tér | O(n) rögzített |

## Mikor kell használni

- **Streaming / audio / videó pufferek** — korlátozott, stabil átvitel.
- **Gyártó–fogyasztó** csatornák visszacsatolási nyomással.
- **Az utolsó N esemény naplózása** (a legrégebbit írja felül).

## Miért fontos

A körkörös puffer előrejelezhető, allokáció nélküli FIFO viselkedést biztosít, ami kritikus a valós idejű és beágyazott rendszerekben, ahol a dinamikus allokáció túl lassú vagy kockázatos.

A korlátozott mérete természetes visszacsatolási nyomásként is működik, megakadályozva a gyors gyártókat a memória kifogyasztásában.

Hogyan működik a burkolás

Code

Mikor kell használni

Miért fontos

Kapcsolódó kérdések