Что такое циклический буфер (ring buffer) и когда его использовать?

Question

Accepted Answer

**Циклический буфер** — это массив фиксированного размера, который рассматривается так, как будто его концы соединены в кольцо. Два индекса — **head** (чтение) и **tail** (запись) — продвигаются и оборачиваются с помощью модульной арифметики, обеспечивая очередь FIFO O(1) **без выделения памяти** после создания.

## Как работает обвязка

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

## Код

```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 без выделения памяти, что критически важно в системах реального времени и встроенных системах, где динамическое выделение памяти слишком медленно или рискованно.

Его ограниченный размер также действует как естественное противодавление, предотвращая быстрых производителей от исчерпания памяти.

Операция	Время
enqueue / dequeue	O(1)
память	O(n) фиксированная