Черга (структура даних)
Черга – структура даних типу «список», що дозволяє додавати елементи лише у кінець списку, і витягувати їх із початку. Вона функціонує за принципом FIFO (First In, First Out – «першим прийшов – першим вийшов»), для якого характерно, що всі елементи a1, a2, …, an-1, an, додані раніше елемента an+1, мають бути видалені перед видаленням елемента an+1. Також черга може бути визначена як окремий випадок однозв'язкового списку, який обслуговує елементи в порядку їх надходження. Як і в «живій» черзі, тут першим буде обслужено той, хто прийшов першим.
- додавання елемента;
- видалення елемента;
- Читання першого елемента.
Тільки якщо щодо стека в момент додавання або видалення елемента допустимо задіяння лише його вершини, то щодо черги ці дві операції повинні бути застосовані так, як це регламентовано у визначенні цієї структури даних, тобто додавання - в кінець, видалення - з початку. Далі при реалізації інтерфейсу черги список стандартних операцій буде розширено.
Виділяють два способи програмної реалізації черги. Перший заснований на базі масиву, а другий на базі покажчиків (зв'язкового списку). Перший спосіб - статичний, тому що черга представляється у вигляді простого статичного масиву, другий - динамічний.
Реалізація черги з допомогою масиву.
Даний спосіб дозволяє організувати та згодом обробляти чергу, що має фіксований розмір. Визначимо список операцій, який використовуватиметься як для реалізації статичної черги, і динамічної:
- Creation(Q) - створення черги Q;
- Full (Q) - перевірка черги Q на порожнечу;
- Add(Q) – додавання елемента до черги Q (йогозначення визначається з функції);
- Delete(Q) – видалення елемента з черги Q;
- Top(Q) – виведення початкового елемента черги Q;
- Size(Q) – розмір черги Q.
У програмі кожна з цих операцій постане у вигляді окремої підпрограми. Крім того, потрібно описати масив данихdata[N], по суті, є сховищем даних місткістю N, а також покажчик на кінець черги (на ту позицію, до якої буде додано черговий елемент) -last. Спочатку last дорівнює 0.
З усіх підпрограм особливої уваги заслуговує функція Delete. Видалення елемента з черги здійснюється шляхом зсуву всіх елементів на початок, тобто значення елементів переписуються: data[0] записується значення елемента data[1], data[1] – data[2] і т. д.; покажчик кінця зміщується назад. Виходить, що це операція вимагає лінійного часу O(n), де n – розмір черги, тоді як інші операції виконуються за константний час. Ця проблема піддається вирішенню.
Замість «мігруючої» черги, найбільш прийнятно реалізувати чергу на базі циклічного масиву. Тут напрошується аналогія з «живою» чергою: якщо в першому випадку покупці підходили до продавця, то тепер продавець підходитиме до покупців (звичайно, така тактика виявилася б марною, наприклад, у супермаркетах тощо). У наведеній реалізації черга вважалася заповненою тоді, коли покажчик last знаходився над останнім осередком, тобто на відстані N елементів від початку.
У циклічному варіанті розширюється інтерпретація визначення позиції last щодо початку черги. Нехай спочатку вказує зміннаfirst. Уявімо масив у вигляді кола – замкнутої структури. Після останнього елемента йде перший і тому можнаГоворити, що черга заповнила весь масив, тоді коли осередки з покажчиками last і first знаходяться поряд, а саме за last слід first. Тепер, видалення елемента з черги здійснюється простим усуненням покажчика first однією позицію вправо (за годинниковою); щоб додати елемент потрібно записати його значення в комірку last масиву data і змістити покажчик last на одну позицію правіше. Щоб не вийти за межі масиву скористаємося такою формулою:
(A mod N) + 1
Тут A – одне із покажчиків, N – розмір масиву, а mod – операція взяття залишку від розподілу.
У циклічній реалізації, як і раніше, черга не містить елементів тоді, коли first і last вказують на ту саму комірку. Але в такому разі виникає одна невелика відмінність цієї реалізації від попередньої. Розглянемо випадок заповнення черги, що базується на базі масиву, розмір якого 5:
| Елементи | перший | last |
| - | 1 | 1 |
| 1 | 1 | 2 |
| 1, 2 | 1 | 3 |
| 1, 2, 3 | 1 | 4 |
| 1, 2, 3, 4 | 1 | 5 |
У лівому стовпці записані довільні значення елементів, а двох інших значення покажчиків при відповідному стані черги. Необхідно зауважити, що масив розміром 5 вдалося помістити тільки 4 елементи. Вся справа в тому, що ще один елемент вимагає усунення покажчика last на позицію 1. Тоді last = first. Але саме ця ситуація є необхідною та достатньою умовою відсутності в черзі елементів. Отже, ми можемо зберігати в масиві більше N-1 елементів.
У наступній програмі реалізовано інтерфейс черги,заснованої на базі циклічного масиву: