Циклічний буфер — Вікіпедія

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

Перевагою використання циклічного буфера є те, що при зчитуванні не потрібно переміщувати дані в буфері, тому що вказівник на поточну позицію переміщується сам. При використанні не кільцевих буферів було б необхідно переміщувати дані, коли його елементи стають непотрібними. Іншими словами кільцевий буфер добре застосовувати для реалізації буферу типу FIFO («перший прийшов — першим пішов»).

Циклічний буфер добре підходить для реалізації черг фіксованого розміру. Але якщо розмір черги є змінним, операція розширення кільцевого буфера є не ефективною, оскільки вимагає здійснення процедури переміщення пам'яті. В таких випадках краще використовувати зв'язаний список.

Такий тип буферу часто зустрічається при роботі з апаратним обладнанням та мікроконтролерами. При роботі з даними мультимедіа, обмежений циклічний буфер часто реалізує задачу постачальника-споживача, наприклад, при роботі зі звуковими картами^[1]. Карта зчитує для відтворення звуку дані з буфера з постійною швидкістю, в той час як постачальник (наприклад, аудіо-генератор) може перезаписувати старі дані.

В початковому стані буфер є пустим і має деяку визначену наперед довжину. Наприклад, так виглядає буфер для 7-ми елементів:

Допустимо, що в середину буфера в якійсь позиції записано значення 1 (конкретна початкова позиція не має значення для циклічного буферу):

Потім допустимо ми додали ще два елементи зі значеннями 2 і 3 — в позиції після значення 1:

Якщо необхідно видалити елементи з буферу, видалятимуться ті, що були записані раніше. Допустимо, що треба видалити два елементи, в такому випадку, значення 1 і 2 будуть видалені, а в буфері залишиться значення 3:

Якщо буфер містить 7 елементів тоді він є повністю заповненим:

Особливість кільцевого буфера полягає в тому, що коли він заповнений і відбувається новий запис даний, будуть перезаписані вже існуючі найстаріші елементи по колу. В такому випадку, два нових елементи — A і B — додаються і перезаписують значення 3 і 4:

Як альтернатива, ще одним із способів обробити ситуацію з заповненням буфера це запобігання перезапису шляхом повернення статусу помилки чи генерації винятку. Перезаписувати дані чи ні залишають на розсуд процедури або програмного додатку, які працюють з буфером.

І нарешті, якщо видалити два елементи то видалені будуть не комірки зі значеннями 3 і 4, а 5 і 6 оскільки A і B перезаписали значення 3 і 4 і буфер матиме наступний вміст:

• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 10. Елементарні структури даних. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
• CircularBuffer, Portland Pattern Repository
• Boost: Templated Circular Buffer Container
• http://www.dspguide.com/ch28/2.htm