Page 38 - 6110

9.3 Черга
Черга в програмуванні – динамічна структура даних, що
працює за принципом “перший прийшов - перший пішов” (FIFO:
first in, first out). У черги є голова (head) та хвіст (tail). Елемент, що
додається до черги, опиняється в її хвості. Елемент, що видаляється
з черги, знаходиться в її голові.
Така черга повністю аналогічна звичній “базарній” черзі, в якій
хто перший встав в неї, той першим буде обслуженим (але, на
відміну від реальної черги, імовірність пройти поза чергою
виключена).

9.3.1 Основні операції з чергою
Еnqueue – “поставити в чергу”. Операція додавання елемента в
“хвіст” черги. При цьому довжина черги збільшується на одиницю.
Якщо відбувається намагання додати елемент у вже заповнену
чергу, відбувається її переповнення (queue overflow).
Dequeue – “отримання з черги”. Операція, яка повертає елемент
з голови та видаляє його з черги, таким чином встановлюючи
голову на наступний за видаленим елемент та зменшуючи довжину
на одиницю. При намаганні видалити елемент з пустої черги,
виникає ситуація “незаповнення” (queue underflow).

9.3.2 Реалізація черги на мовах програмування
Черга може бути реалізована за допомогою масива Q[1...n], в
якому зберігаються дані та двох додаткових змінних head[Q] та
tail[Q], в яких зберігаються індекси відповідно “голови” та “хвоста”
черги, lenght[Q] – довжина черги.

Тоді операції enqueue та dequeue запишуться так:

ENQUEUE (Q, x)
1 Q[tail[Q]] := x
2 if tail[Q] = length[Q]
3 then tail[Q] := 1
4 else tail[Q] := tail[Q] + 1

DEQUEUE (Q)
1 x := Q[head[Q]]
2 if head[Q] = length[Q]
3 then head[Q] := 1
4 else head[Q] := head[Q] + 1
5 return x

37