Реалізація черги на базі масиву

Усі структури даних можна реалізовувати на основі масиву. Звичайно, така реалізація може бути багатоетапною, і не завжди масив виступає як безпосередня база реалізації. У випадку черги найбільш популярні дві реалізації: безперервна на базі масиву, яку називають також реалізацією на базі кільцевого буфера, і посилальна реалізація, або реалізація на базі списку.

При безперервній реалізації черги в якості бази виступає масив фіксованої довжини N, таким чином, черга обмежена й не може містити більш N елементів. Індекси елементів масиву змінюються в межах від 0 до N - 1. Крім масиву, реалізація черги зберігає три прості змінні: індекс початку черги, індекс кінця черги, число елементів черги. Елементи черги зберігаються у відрізку масиву від індексу початку до індексу кінця.

При додаванні нового елемента в кінець черги індекс кінця спочатку збільшується на одиницю, потім новий елемент записується в елемент масиву із цим індексом. Аналогічно, при видаленні елементу з початку черги вміст елементу масиву з індексом початку черги запам'ятовується як результат операції, потім індекс початку черги збільшується на одиницю. Як індекс початку черги, так і індекс кінця при роботі рухаються зліва направо. Що відбувається, коли індекс кінця черги досягає кінця масиву, тобто N - 1?

Ключова ідея реалізації черги полягає в тому, що масив подумки як би зациклюється в кільце. Вважається, що за останнім елементом масиву розміщений його перший елемент (останній елемент має індекс N-1, а перший - індекс 0). При зрушенні індексу кінця черги вправо у випадку, коли він указує на останній елементмасиву, він переходить на перший елемент. Таким чином, безперервний відрізок масиву, зайнятий елементами черги, може переходити через кінець масиву на його початок.

Циклічну чергу найкраще зображати циклічним або кільцевим списком, доповненим вказівниками на позицію для включення і виключення елементів із черги.

Деки

Деки - це впорядкована лінійна динамічно змінювана послідовність елементів, в якій виконуються такі умови:

1) новий елемент може приєднуватися з обох боків послідовності;

2) вибірка елементів можлива також з обох боків послідовності.

Наприклад, якщо послідовність D = D_1,..., D_n зображує дек, то її елементи D_{1 і} D_n вказують одночасно на місце включення і виключення елементів.

Деки бувають з обмеженнями з одного боку на виконання однієї з операцій (наприклад, один бік послідовності може бути закритий для вибірки елементів і відкритий тільки для приєднування, і навпаки).

Деки називають також реверсивними чергами або чергами з двома кінцями, в яких включення і виключення здійснюються з двох країв послідовності. Як і у випадку звичайних черг, для обслуговування деків також потрібно два вказівники, по одному на кожний кінець послідовності. Деки є найбільш загальною лінійною динамічною структурою даних.