WikiSort.ru - Кино и мультфильмы

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

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

Применение

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

Внутреннее устройство

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

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

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

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

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

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

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

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

Ссылки

• CircularBuffer на сайте Portland Pattern Repository (англ.)
• Boost: Templated Circular Buffer Container (англ.)
• Chapter 28: Digital Signal Processors / Steven W. Smith, The Scientist and Engineer's Guide to Digital Signal Processing  (англ.)

Это заготовка статьи по информатике. Вы можете помочь проекту, дополнив её.