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

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

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

Применение

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

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

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

Предположим, что в середину буфера записывается 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