Кільцевий буфер

Вказівки

Круговий буфер, циклічний буфер або кільцевий буфер - це структура даних, яка використовує один буфер фіксованого розміру, ніби його зʼєднано кінець із кінцем.

Спочатку кільцевий буфер порожній і має певну попередньо визначену довжину. Наприклад, ось буфер на 7 елементів:

[ ][ ][ ][ ][ ][ ][ ]

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

[ ][ ][ ][1][ ][ ][ ]

Потім припустімо, що додаються ще два елементи (2 і 3), які дописуються після 1:

[ ][ ][ ][1][2][3][ ]

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

[ ][ ][ ][ ][ ][3][ ]

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

[5][6][7][8][9][3][4]

Коли буфер заповнений, виникне помилка, яка повідомляє клієнта, що подальші записи заблоковано, доки не звільниться слот.

Коли буфер заповнений, клієнт може вирішити перезаписати найстаріші дані примусовим записом. У цьому випадку додаються ще два елементи (A і B), які перезаписують 3 і 4:

[5][6][7][8][9][A][B]

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

[ ][ ][7][8][9][A][B]

Оскільки є вільне місце, якщо клієнт знову використає перезапис, щоб зберегти C і D, то буде використано місце, де раніше зберігалися 5 і 6, а не позиція 7 і 8. 7 усе ще найстаріший елемент, і буфер знову повний.

[C][D][7][8][9][A][B]

---

Джерело

Wikipedia