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

Вказівки

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

Спочатку кільцевий буфер порожній і має певну заздалегідь визначену довжину. Наприклад, ось буфер на 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