サーキュラーバッファ（リングバッファ）とは何ですか？また、どのような場合に使用しますか？

Question

Accepted Answer

**サーキュラーバッファ** は固定サイズの配列で、その両端が環に繋がっているかのように扱われます。2つのインデックス — **head**（読み取り）と **tail**（書き込み）— はモジュロ演算を使用して進み、ラップアラウンドします。これにより、作成後は**メモリ割り当てがない** O(1) の FIFO キューが実現されます。

## ラップアラウンドの仕組み

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

| 操作 | 時間計算量 |
|---|---|
| enqueue / dequeue | O(1) |
| 空間 | O(n) 固定 |

## 使用する場合

- **ストリーミング / オーディオ / ビデオバッファ** — 有界で、スループットが一定。
- **プロデューサ–コンシューマ** パイプライン（バックプレッシャー付き）。
- **最後の N イベントをログに記録** （最古のものを上書き）。

## なぜ重要なのか

リングバッファは予測可能でメモリ割り当てのない FIFO 動作を提供し、動的割り当てが遅すぎるか危険である実時間システムおよび組み込みシステムで不可欠です。

その有界なサイズは自然なバックプレッシャーとしても機能し、高速なプロデューサがメモリを枯渇させることを防ぎます。