|
Циклічний буфер Циклічний буфер або кільцевий буфер — це структура даних, яка має фіксований розмір і використовується так ніби кінець буферу і початок замкнені в кільце, тобто при досягненні кінця буфера знов переміщуються в його початок. Така структура дає можливість здійснювати буферизацію потоків даних. ЗастосуванняПеревагою використання циклічного буфера є те, що при зчитуванні не потрібно переміщувати дані в буфері, тому що вказівник на поточну позицію переміщується сам. При використанні не кільцевих буферів було б необхідно переміщувати дані, коли його елементи стають непотрібними. Іншими словами кільцевий буфер добре застосовувати для реалізації буферу типу FIFO («перший прийшов — першим пішов»). Циклічний буфер добре підходить для реалізації черг фіксованого розміру. Але якщо розмір черги є змінним, операція розширення кільцевого буфера є не ефективною, оскільки вимагає здійснення процедури переміщення пам'яті. В таких випадках краще використовувати зв'язаний список. Такий тип буферу часто зустрічається при роботі з апаратним обладнанням та мікроконтролерами. При роботі з даними мультимедіа, обмежений циклічний буфер часто реалізує задачу постачальника-споживача, наприклад, при роботі зі звуковими картами[1]. Карта зчитує для відтворення звуку дані з буфера з постійною швидкістю, в той час як постачальник (наприклад, аудіо-генератор) може перезаписувати старі дані. Принцип роботиВ початковому стані буфер є пустим і має деяку визначену наперед довжину. Наприклад, так виглядає буфер для 7-ми елементів: Допустимо, що в середину буфера в якійсь позиції записано значення 1 (конкретна початкова позиція не має значення для циклічного буферу): Потім допустимо ми додали ще два елементи зі значеннями 2 і 3 — в позиції після значення 1: Якщо необхідно видалити елементи з буферу, видалятимуться ті, що були записані раніше. Допустимо, що треба видалити два елементи, в такому випадку, значення 1 і 2 будуть видалені, а в буфері залишиться значення 3: Якщо буфер містить 7 елементів тоді він є повністю заповненим: Особливість кільцевого буфера полягає в тому, що коли він заповнений і відбувається новий запис даний, будуть перезаписані вже існуючі найстаріші елементи по колу. В такому випадку, два нових елементи — A і B — додаються і перезаписують значення 3 і 4: Як альтернатива, ще одним із способів обробити ситуацію з заповненням буфера це запобігання перезапису шляхом повернення статусу помилки чи генерації винятку. Перезаписувати дані чи ні залишають на розсуд процедури або програмного додатку, які працюють з буфером. І нарешті, якщо видалити два елементи то видалені будуть не комірки зі значеннями 3 і 4, а 5 і 6 оскільки A і B перезаписали значення 3 і 4 і буфер матиме наступний вміст: Примітки
Джерела
|
