Кольцевой буфер | это... Что такое Кольцевой буфер? (original) (raw)

Кольцевой буфер. Иллюстрация визуально показывает, что у буфера нет настоящего конца. Тем не менее, поскольку физическая память никогда не делается закольцованной, обычно используется линейное представление, как показано ниже.

Кольцевой буфер, или циклический буфер — это структура данных, использующая единственный буфер фиксированного размера, как будто бы после последнего элемента сразу же снова идет первый. Такая структура легко предоставляет возможность буферизации потоков данных.

Применение

Как он устроен

Кольцевой буфер создается пустым, с некоторой заранее определенной длинной. Например, это семиэлементный буфер:

Предположим, что в середину буфера записывается 1 (в кольцевом буфере точная начальная ячейка не имеет значения):

Затем предположим, что после единицы были добавлены еще два элемента — 2 и 3:

Если после этого два элемента должны быть удалены из буфера, то выбираются два наиболее старых элемента. В нашем случае удаляются элементы 1 и 2, в буфере остается только 3:

Если в буфере находится 7 элементов, то он заполнен:

Если продолжить запись в буфер, не принимая во внимание его заполненность, то новые данные начнут перезаписывать старые данные. В нашем случае, добавляя элементы A и B мы перезапишем 3 и 4:

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

Наконец, если теперь удалить из буфера два элемента, то удалены будут не 3 и 4, а 5 и 6, потому что A и B перезаписали элементы 3 и 4; буфер придет в состояние:

Ссылки

• CircularBuffer at the Portland Pattern Repository
• Boost: Templated Circular Buffer Container
• http://www.dspguide.com/ch28/2.htm

Структуры данных (список)
Типы	Коллекция • Контейнер
Массивы	Ассоциативный массив • Multimap • Множество • Мультимножество • Хеш-таблица
Списки	Связный список • Очередь (Кольцевой буфер • Двусвязная) • Стек • Список с пропусками
Деревья	B-дерево • Двоичное дерево поиска • Куча
Графы	Ориентированный граф • Направленный ациклический граф • Бинарная диаграмма решений • Гиперграф