Кольцевой буфер: очередь без сдвига головы

Если ты понимаешь, как кольцевой буфер даёт enqueue и dequeue за O(1) через индексы head/tail с обёртыванием по остатку от деления, листай до «Теперь сам».

Как думаешь, обязательно ли двигать элементы, чтобы снять голову

Наивная очередь сдвигает весь хвост влево после каждого dequeue - лишь бы голова снова оказалась в ячейке 0. Но кто сказал, что голова обязана быть в нулевой ячейке? Мы двигаем ДАННЫЕ, чтобы указатель остался на месте. Можно наоборот: оставить данные где лежат, а двигать УКАЗАТЕЛЬ. Тогда снять голову - это просто «запомнить, что теперь голова на одну ячейку дальше», без единого перемещения. Эта перестановка и рождает кольцевой буфер.

На что это похоже

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

Механизм: два индекса и обёртывание

Берём массив ёмкости size и два индекса: head - откуда снимать, tail - куда класть. Плюс счётчик count - сколько элементов сейчас в очереди (он отличает пустую очередь от полной, когда head и tail совпали).

• enqueue(x): кладём x в ячейку tail, сдвигаем tail на следующую, count += 1.
• dequeue(): читаем ячейку head, сдвигаем head на следующую, count -= 1.

«Сдвинуть на следующую» с обёртыванием - это остаток от деления: tail = (tail + 1) % size. Когда tail был на последней ячейке (size − 1), (size − 1 + 1) % size = 0 - индекс прыгает в начало. Массив как будто замкнут в кольцо: за последней ячейкой снова нулевая.

Ни enqueue, ни dequeue не трогают чужие элементы - только пишут/читают одну ячейку и сдвигают один индекс. Обе операции O(1), серия из n - O(n). Сдвиг хвоста исчез.

Правило

Кольцевой буфер - массив плюс индексы head (откуда снимать) и tail (куда класть) и счётчик count. enqueue пишет в tail, dequeue читает из head, каждый сдвигает свой индекс с обёртыванием (i + 1) % size. Ничего не сдвигается - обе операции O(1). Ёмкость фиксирована; заполнился (count == size) - выделяют вдвое больший буфер и переносят элементы, как динамический массив.

Разбор: почему нужен count, а не сравнение head и tail

Заманчиво определять пустоту и полноту по индексам: «пусто, когда head == tail». Но head == tail бывает в ДВУХ случаях - когда очередь пуста и когда она полна (tail обошёл кольцо и догнал head сзади). По самим индексам эти два состояния не различить. Есть два лечения. Первое - держать счётчик count: пусто при count == 0, полно при count == size, однозначно. Второе (как в классическом изложении CLRS) - жертвовать одной ячейкой: считать очередь полной уже при head == tail + 1 (по кольцу), тогда head == tail всегда означает «пусто». Мы берём count - он проще и не теряет ячейку. Суть одна: без дополнительного признака кольцо не отличает пустоту от полноты.

Разбор: обёртывание - это остаток от деления

Почему именно % size? Индексы должны бегать по кругу 0, 1, ..., size−1, 0, 1, .... Остаток от деления ровно это и делает: (size − 1 + 1) % size = size % size = 0. Пока tail + 1 < size, остаток равен самому tail + 1 (ничего не меняется); как только tail + 1 дорос до size, остаток обнуляет его в 0. Без % пришлось бы писать if tail + 1 == size: tail = 0 else: tail += 1 - то же самое, только длиннее. Остаток от деления - это компактная запись «считай по кругу», и стоит она столько же, O(1). Тот же приём (индекс по модулю размера) ты встретишь всюду, где что-то ходит циклически: хеш-таблицы, круговые расписания, буферы аудио и видео.

Что ломается без этого

Первая ошибка - забыть про обёртывание и писать просто tail += 1: индекс вылезет за границу массива, и enqueue упадёт, хотя в начале буфера полно свободных ячеек (их освободил dequeue). Кольцо не замкнётся, и вся идея не сработает. Вторая - определять пустоту через head == tail без счётчика и спутать пустую очередь с полной: то потеряешь данные (примешь «полно» за «пусто» и перезапишешь), то зря откажешь. Третья - забыть про рост: у кольцевого буфера ёмкость конечна, и если поток enqueue обгоняет dequeue, без удвоения буфера очередь переполнится.

Зачем это в работе

Кольцевой буфер - стандартный способ сделать быструю очередь на массиве, и он повсюду там, где данные текут потоком: буферы клавиатуры, звука и видео (продюсер пишет в tail, потребитель читает из head), журналы последних событий фиксированной длины, очереди пакетов в сетевых картах. Его любят за предсказуемость: память выделена заранее одним куском, операции O(1), никаких сдвигов и никакого разброса узлов по памяти, как у связного списка, - значит, ещё и локальность на его стороне. Когда слышишь «ring buffer» или «circular queue» - это ровно он, и теперь ты знаешь, почему он O(1).

Теперь сам

Кольцевой буфер ёмкости size = 4, сейчас head = 3, а в буфере два элемента (count = 2, лежат в ячейках 3 и 0). Делаем enqueue(x). В какую ячейку ляжет x и чему станет равен tail после? Почему это O(1), а не сдвиг?