Черга () — динамічна структура даних в програмуванні, що працює за принципом «перший прийшов — перший пішов» (). У черги є голова () та хвіст (). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові.
Така черга повністю аналогічна звичній «базарній» черзі, у якій спочатку обслуговують того, хто прийшов першим, потім наступного і так далі.
Основні операції з чергою — "поставити в чергу". Операція додавання елемента в "хвіст" черги. При цьому довжина черги збільшується на одиницю. Якщо відбувається намагання додати елемент у вже заповнену чергу, відбувається її переповнення ().
— "отримання з черги". Операція, яка повертає елемент з голови та видаляє його з черги, таким чином встановлюючи голову на наступний за видаленим елемент та зменшуючи довжину на одиницю. При намаганні видалити елемент з пустої черги, виникає ситуація "незаповненість" ().
Реалізація на мовах програмування Черга може бути реалізована за допомогою масиву 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
Джерела