Apa itu circular buffer (ring buffer) dan kapan Anda menggunakannya?

Question

IT Interview Practice · Accepted Answer

**circular buffer** adalah array berukuran tetap yang diperlakukan seolah-olah ujungnya digabungkan menjadi cincin. Dua indeks — **head** (baca) dan **tail** (tulis) — maju dan membungkus menggunakan aritmetika modulo, memberikan antrian FIFO O(1) **tanpa alokasi** setelah pembuatan.

## Cara pembungkusan bekerja

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

| Operasi | Waktu |
|---|---|
| enqueue / dequeue | O(1) |
| ruang | O(n) tetap |

## Kapan digunakan

- **Buffer streaming / audio / video** — throughput terbatas dan stabil.
- **Pipa produsen–konsumen** dengan tekanan balik.
- **Mencatat N peristiwa terakhir** (timpa yang tertua).

## Mengapa ini penting

Buffer cincin menyediakan perilaku FIFO yang dapat diprediksi dan bebas alokasi, yang penting dalam sistem waktu nyata dan tertanam di mana alokasi dinamis terlalu lambat atau berisiko.

Ukurannya yang terbatas juga bertindak sebagai tekanan balik alami, mencegah produsen cepat menghabiskan memori.

Cara pembungkusan bekerja

Code

Kapan digunakan

Mengapa ini penting

Pertanyaan terkait