Кольцевой буфер: реализация на массиве и индексах

Кольцевой буфер (circular buffer, ring buffer) - это структура данных с фиксированным размером, которая ведёт себя как очередь, но физически хранится в обычном массиве без сдвига элементов. Вместо того чтобы после каждого чтения сдвигать все оставшиеся элементы влево, буфер просто пускает индексы записи и чтения по кругу: дойдя до конца массива, они перескакивают обратно к нулю. Ниже разберём, как это реализовать на практике - какие поля нужны, как вывести формулы для индексов через остаток от деления и почему наивная реализация с двумя указателями обязательно спотыкается на одном и том же вопросе: буфер сейчас полон или пуст. Чтобы сразу увидеть, как индексы двигаются и где происходит перенос через край, покрутите калькулятор ниже - он строит схему массива по вашим числам.

Зачем нужен кольцевой буфер

Кольцевой буфер решает конкретную практическую задачу: нужно накапливать поток данных ограниченного объёма без постоянных перевыделений памяти. Классические примеры - буфер аудиосэмплов между звуковой картой и обработчиком, буфер сетевых пакетов между сетевой картой и приложением, кольцевой лог последних N событий, очередь заданий между производителем и потребителем в конвейере. Во всех этих случаях важны две вещи: операции добавления и извлечения элемента должны выполняться за константное время $O(1)$, и память должна выделяться один раз, а не расти безгранично. Обычный массив с постоянным сдвигом элементов при извлечении даёт $O(n)$ на операцию - для потоковых данных это неприемлемо. Кольцевой буфер убирает сдвиг совсем: элемент просто остаётся на своём месте, пока индекс чтения не дойдёт до него.

Массив и два индекса: базовая реализация

Основа реализации - фиксированный массив длиной $N$ (ёмкость буфера) и два индекса: head - физический индекс самого старого элемента, который будет прочитан следующим, и tail - физический индекс, куда попадёт следующая запись. Запись элемента (enqueue) кладёт значение в ячейку tail и сдвигает tail на одну позицию вперёд; чтение (dequeue) забирает значение из ячейки head и сдвигает head на одну позицию вперёд. Хитрость в том, что сдвиг делается не простым +1, а по кругу: дойдя до последней ячейки массива, индекс должен вернуться к нулю, а не выйти за границу.

Рассчитать для своей задачи

Именно этот перенос через край и даёт буферу название «кольцевой»: логически ячейки образуют круг, хотя физически это по-прежнему линейный участок памяти. Реализация не хранит никакого «кольца» - она просто применяет остаток от деления к обычному линейному индексу.

Формулы head, tail и переноса через модуль

Пусть $N$ - ёмкость буфера, а $w$ и $r$ - счётчики операций: $w$ считает, сколько записей всего было успешно выполнено с момента создания буфера, $r$ - сколько было успешно выполнено чтений. Важно, что оба счётчика монотонно растут и никогда не убывают и не оборачиваются сами - оборачивается только их проекция на физический индекс:

$\text{tail} = w \bmod N, \qquad \text{head} = r \bmod N.$

Число элементов, реально хранящихся в буфере прямо сейчас, - это разница счётчиков:

$\text{count} = w - r, \qquad 0 \le \text{count} \le N.$

Свободных ячеек, соответственно, $N - \text{count}$. Занятые физические индексы - это count ячеек подряд начиная с head: $(\text{head} + k) \bmod N$ для $k = 0, 1, \dots, \text{count}-1$. Если это множество индексов «перепрыгивает» через конец массива (то есть $\text{head} + \text{count} > N$), значит, часть элементов физически лежит в хвосте массива, а часть - в начале: это и есть тот самый перенос через край.

Рассчитать для своей задачи

Проблема head == tail: буфер полон или пуст

Если реализовать буфер наивно - хранить только физические индексы head и tail без отдельных счётчиков - возникает неприятная неоднозначность. Пустой буфер, из которого ничего не читали и не писали, имеет head == tail (оба указывают на нулевую ячейку). Но полностью заполненный буфер, где записали ровно $N$ элементов без единого чтения, после $N$-й записи получает tail, снова равный head: индекс просто обошёл круг целиком и вернулся туда, откуда начал. По одним лишь физическим индексам эти два состояния - «нет ни одного элемента» и «занято абсолютно всё» - неотличимы.

Рассчитать для своей задачи

Это классическая ошибка при реализации кольцевого буфера «в лоб»: код инициализирует head = tail = 0, а потом сравнивает их равенство как признак пустоты - и первая же попытка заполнить буфер полностью незаметно превращается в баг, который выглядит как «буфер внезапно опустел», хотя на самом деле он полон.

Решение через монотонные счётчики операций

Есть несколько способов снять неоднозначность. Самый прямолинейный - завести отдельный флаг is_full или поле count, которое инкрементируется при записи и декрементируется при чтении. Другой популярный трюк - специально использовать только $N - 1$ ячеек из $N$ выделенных: буфер считается полным на одну ячейку раньше, чем физически заполнен весь массив, и тогда head == tail однозначно означает «пусто» - ценой одной вечно свободной ячейки.

Третий подход - тот, что использован в формулах выше и в калькуляторе - считать не физические индексы напрямую, а монотонные счётчики $w$ и $r$, которые растут без ограничения (или до переполнения типа, что на практике почти никогда не достигается для 32- или 64-битных счётчиков). Физические head и tail - это лишь проекция счётчиков на диапазон $[0, N)$ через остаток от деления. Поскольку $w$ и $r$ сами по себе никогда не совпадают случайно (они точно равны только когда буфер пуст: count = w - r = 0), сравнение w == r однозначно определяет пустоту, а w - r == N - полноту, без дополнительных флагов и без потери одной ячейки.

enqueue(value):
    if w - r == N: отклонить (буфер полон)
    buffer[w mod N] = value
    w = w + 1

dequeue():
    if w - r == 0: отклонить (буфер пуст)
    value = buffer[r mod N]
    r = r + 1
    return value

Где применяется кольцевой буфер на практике

В аудиообработке кольцевой буфер сглаживает разницу в скорости между потоком, который генерирует сэмплы (микрофон, декодер), и потоком, который их потребляет (звуковая карта, кодировщик): пока производитель немного опережает или отстаёт, буфер поглощает эту разницу без пропуска и без блокировки. В сетевом стеке кольцевые буферы используются в кольцах приёма и передачи сетевых карт (RX/TX ring) - драйвер и сетевая карта пишут и читают дескрипторы пакетов через общий кольцевой буфер без блокировок. В логировании кольцевой буфер фиксированного размера хранит последние $N$ записей: старые записи автоматически вытесняются новыми, память не растёт, а последняя история событий перед сбоем всегда доступна. Общая черта всех случаев - поток данных ограниченного темпа, где важна предсказуемая по времени работа без аллокаций в реальном времени.

Частые ошибки

• Сравнение head == tail как признак пустоты без дополнительного поля - не различает пустой и полный буфер, см. раздел выше.
• Инкремент индекса без взятия остатка: tail = tail + 1 без % N рано или поздно выйдет за границы массива.
• Отсутствие проверки переполнения при записи: без проверки count == N перед enqueue новая запись затирает ещё не прочитанный элемент, и данные теряются молча.
• Путаница, какой индекс двигать при записи, а какой при чтении: tail двигается при записи (enqueue), head - при чтении (dequeue); перепутанные роли ломают порядок FIFO.
• Использование знаковой арифметики без нормализации остатка: в некоторых языках операция % от отрицательного числа даёт отрицательный результат - при вычислении индексов это нужно учитывать отдельной нормализацией.

FAQ

Чем кольцевой буфер отличается от обычной очереди на массиве? Обычная очередь на массиве без циклических индексов после каждого извлечения сдвигает оставшиеся элементы к началу массива - это операция $O(n)$. Кольцевой буфер вместо сдвига переносит индексы по кругу через остаток от деления, поэтому запись и чтение остаются $O(1)$ независимо от того, сколько элементов уже прошло через буфер.

Что происходит при попытке записи в полный кольцевой буфер? Зависит от реализации: чаще всего запись либо отклоняется (вызывающий код получает сигнал «буфер полон» и должен подождать), либо буфер настроен на перезапись самого старого элемента (характерно для буферов логов и аудио, где свежие данные важнее старых).

Можно ли реализовать кольцевой буфер без счётчиков, только на head и tail? Можно, но тогда нужен либо отдельный флаг заполненности, либо намеренный отказ от использования последней ячейки (буфер ёмкостью $N$ реально хранит не больше $N-1$ элементов). Оба варианта работают, но счётчики операций $w$ и $r$ дают самую простую и наименее подверженную ошибкам формулу.

Коротко

Кольцевой буфер - это массив фиксированного размера с двумя индексами, head и tail, которые вместо выхода за границу массива переносятся обратно к нулю через остаток от деления: $\text{tail} = w \bmod N$, $\text{head} = r \bmod N$, где $w$ и $r$ - общее число выполненных записей и чтений. Число элементов в буфере - это $\text{count} = w - r$, и именно оно, а не сравнение самих индексов, надёжно отличает полный буфер от пустого, потому что при head == tail эти два состояния физически неразличимы без дополнительной информации. Такая реализация даёт запись и чтение за константное время без единой лишней аллокации памяти, поэтому кольцевые буферы - стандартный выбор для аудиопотоков, сетевых очередей и логов ограниченного размера.