Поняття черги
Чергою FIFO (First - In - First - Out - "першим прийшов - першим виключається") називається такий послідовний список змінної довжини, в якому включення елементів виконується тільки з одного боку списку (цю сторону часто називають кінцем або хвостом черги), а виняток - з іншого (називається початком або головою черги). Черги до прилавків та кас є типовим побутовим прикладом черги FIFO.
Основні операції над чергою – самі, як і над стеком – включення, виняток, визначення розміру, очищення, читання, що не руйнує.
Мал. 13.1. Подання черги масивом
Очевидно, що згодом покажчик на кінець при черговому включенні елемента досягне верхньої межі тієї області пам'яті, яка виділена для черги. Однак якщо операції включення чергувалися з операціями виключення елементів, то в початковій частині пам'яті відведеної під чергу є вільне місце. Для того, щоб місця, займані виключеними елементами, могли бути повторно використані, черга замикається в кільце: покажчики (на початок і на кінець), досягнувши кінця виділеної області пам'яті, перемикаються на її початок. Така організація черги у пам'яті називаєтьсякільцевою чергою.
Можливі, звичайно, й інші варіанти організації: наприклад, щоразу, коли покажчик кінця досягне верхньої межі пам'яті, зрушувати всі непусті елементи черги до початку області пам'яті, але як цей, так і інші варіанти вимагають переміщення в пам'яті елементів черги і менш ефективні, ніж кільцева черга.
У вихідному стані покажчики початку і кінець вказують початку області пам'яті. Рівність цих двох покажчиків (за будь-якого їх значення) єознакою порожньої черги. Якщо в процесі роботи з кільцевою чергою кількість операцій включення перевищує кількість операцій виключення, то може виникнути ситуація, в якій покажчик кінця «наздожене» покажчик початку. Це ситуація заповненої черги, але якщо в цій ситуації покажчики зрівняються, ця ситуація буде невідмінною від ситуації порожньої черги. Для розрізнення цих двох ситуацій до кільцевої черги висувається вимога, щоб між покажчиком кінця та покажчиком початку залишався «зазор» із вільних елементів. Коли цей зазор скорочується до одного елемента, черга вважається заповненою, і подальші спроби запису в неї блокуються. Очищення черги зводиться до запису того самого (загалом не обов'язково початкового) значення обидва покажчика. Визначення розміру полягає у обчисленні різниці покажчиків з урахуванням кільцевої природи черги.
Дек - особливий вид черги. Дек (від англ. deq - double ended queue, тобто черга з двома кінцями) - це такий послідовний список, в якому як включення, так і виключення елементів може здійснюватися з будь-якого з двох кінців списку. Окремий випадок дека – дек з обмеженим входом та дек з обмеженим виходом. Логічна та фізична структури дека аналогічні логічній та фізичній структурі кільцевої FIFO-черги. Однак стосовно деку доцільно говорити не про початок і кінець, а про лівий і правий кінець.
Операції над деками:
- включення елемента праворуч;
- включення елемента зліва;
- виключення елемента праворуч;
- виключення елемента зліва;
Фізична структура дека у статичній пам'яті ідентична структурі кільцевої черги. Динамічна реалізація є очевидним об'єднанням стека та черги.
Завдання, що вимагають структури дека,зустрічаються в обчислювальній техніці та програмуванні набагато рідше, ніж завдання, що реалізуються на структурі стека або черги. Як правило, вся організація дека виконується програмістом без будь-яких спеціальних засобів системної підтримки.
Прикладом дека може бути, наприклад, певний термінал, в який вводяться команди, кожна з яких виконується певний час. Якщо ввести наступну команду не дочекавшись, поки закінчиться виконання попередньої, то вона стане в чергу і почне виконуватися, як тільки звільниться термінал. Це FIFO-черга. Якщо ж ввести додатково операцію скасування останньої введеної команди, виходить дек.