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

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

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

Применение[править | править вики-текст]

Кольцевой буфер находит очень широкое применение в том числе при программировании МК. Кольцевые буферы часто используют для организации различных очередей сообщений и буферов приёма-передачи различных коммуникационных интерфейсов. Популярность КБ обусловлена тем, что это один из самых простых и эффективных способов организовать FIFO (англ. first in — first out, «первым пришёл — первым вышел») без использования динамической памяти. Существует множество разновидностей КБ.

Как он устроен[править | править вики-текст]

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

Circular buffer - empty.svg

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

Circular buffer - XX1XXXX.svg

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

Circular buffer - XX123XX.svg

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

Circular buffer - XXXX3XX.svg

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

Circular buffer - 6789345.svg

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

Circular buffer - 6789AB5.svg

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

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

Circular buffer - X789ABX.svg


Ссылки[править | править вики-текст]