Кольцевой буффер

Делаю задания с книги Algorithms, 4th Edition by Robert Sedgewick :

1.3.37 Кольцевой буфер.

Кольцевой или кольцевая очередь - это структура данных с правилом FIFO фиксированного размера N, удобная для передачи данных между асинхронными процессами или для хранения файлов журналов. Если буфер пуст, получатель ждет поступления в него данных; если буфер полон, отправитель ждет, когда можно будет поместить данные.
Разработайте API - интерфейс для типа RingBuffer и реализуйте его на основе массива.

Здесь для меня все понятно, кроме того как можно закольцевать массив, не лучше ли реализация на основе списка? Спасибо за внимание.

0

Сообщение от TheNooob как можно закольцевать массив

1

Кольцевые списки

1

Shamil1, Это Wrap Around - т.е зацикливание самого индекса.
TheNooob, У кольцевого буфера(очереди) все веселее.
Т.е. имеется два указателя(индекса) - голова и хвост в начале равные нулю (указывают на первый элемент). При добавлении в буфер (очередь) новый элемент пишется в положение хвоста и хвост сдвигается на единицу вперед с учетом wrap around. При извлечении элемент извлекается из головы и вперед смещается голова тоже с учетом wrap around. Если голова догнала хвост то буфер пуст и их можно обнулить. Если хвост догнал голову то буфер переполнен.
Т.е. аналог закольцованной ленты с раздельными головками чтения и записи.

Добавлено через 8 минут

Сообщение от TheNooob не лучше ли реализация на основе списка

Реализацию того же самого функционала на основе связного списка обычно можно расценивать как диверсию. Преимущество кольцевого буфера в том что он не требует перераспределения динамической памяти под элементы при их добавлении/извлечении, память распределяется один раз на старте использующей его системы. Используются такие буфера обычно в системах реального времени. Поэтому переполнение буфера (а тем более созданного с небольшим запасом)по условиям системы невозможно. Т.е. если под новый элемент в буфере нет места, то проблема не в том что места нет, а проблема в том что система не смогла отработать элементы очереди в заданный лимит времени и уже считается поломавшейся по определению системы реального времени.

Добавлено через 2 часа 11 минут
При использовании же кольцевого буфера в качестве журнала, считается что актуальными являются последние N записей, т.е. когда головка записи проходит по кругу она просто переписывает более старые записи которые уже неактуальны. Аналог - бортовой самописец (черный ящик). Лента рассчитана на продолжительность полета и закольцована. Т.е. данные накопленные в течение предыдущего полета просто переписываютсяя данными текущего полета, потому что в случае аварии данные предыдущего полета не актуальны, соответственно их можно просто переписать, что как экономит сам носитель так и исключает невозможность записи по причине "забыли заменить заполнившийся носитель при предполетной подготовке".

1