Черга (структура даних)

Черга (англ. queue) — динамічна структура даних в програмуванні, що працює за принципом «перший прийшов — перший пішов» (англ. FIFO — first in, first out). У черги є голова (англ. head) та хвіст (англ. tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові.

Така черга повністю аналогічна звичній «базарній» черзі, у якій спочатку обслуговують того, хто прийшов першим, потім наступного і так далі.

Основні операції з чергою

• англ. enqueue — "поставити в чергу". Операція додавання елемента в "хвіст" черги. При цьому довжина черги збільшується на одиницю. Якщо відбувається намагання додати елемент у вже заповнену чергу, відбувається її переповнення (англ. queue overflow).

• англ. dequeue — "отримання з черги". Операція, яка повертає елемент з голови та видаляє його з черги, таким чином встановлюючи голову на наступний за видаленим елемент та зменшуючи довжину на одиницю. При намаганні видалити елемент з пустої черги, виникає ситуація "незаповненість" (англ. queue underflow).

Реалізація на мовах програмування

Черга може бути реалізована за допомогою масиву Q[1...n], в якому зберігаються дані та двох додаткових змінних head[Q] та tail[Q], в яких зберігаються індекси відповідно "голови" та "хвоста" черги, length[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

Джерела

• Дональд Кнут. Fundamental Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 1. — 650 с. — ISBN 0-201-89683-4.(англ.)
• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 10.1 Стеки і черги. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.