Реалізація стеку на базі масиву

Реалізація стеку на базі масиву є класикою програмування. Іноді навіть саме поняття стеку не цілком коректно ототожнюється із цією реалізацією.

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

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

У наведеній реалізації стек росте убік збільшення індексів елементів масиву. Часто використовується інший варіант реалізації стеку на базі вектора, коли дностеку міститься в останньому елементі масиву, тобто в елементі з індексом N - 1. Елементи стеку займають безперервний відрізок масиву, починаючи із елемента, індекс якого зберігається у вказівнику стеку, і закінчуючи останнім елементом масиву. У цьому варіанті стек росте убік зменшення індексів. Якщо стек порожній, то вказівник стеку містить значення N, яке на одиницю більше, ніж індекс останнього елемента масиву).

Черги

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

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

2) доступ до елементів aбo їх виключення завжди здійснюється з другого боку послідовності.

Наприклад, нехай послідовність Q=Q₁...,Q_n зображує чергу. Тоді елемент Q₁, називають "головою" черги і він вказує на місце для виключення елемента; а елемент Q_n називають "хвостом" черги і він вказує на місце для включення елемента в чергу.

Чергу можна представити у вигляді трубки. В один кінець трубки можна додавати кульки — елементи черги, з іншого кінця вони видаляються. Елементи в середині черги, тобто кульки усередині трубки, недоступні. Кінець трубки, у який додаються кульки, відповідає кінцю черги, кінець, з якого вони видаляються — початку черги. Таким чином, кінці трубки не симетричні, кульки усередині трубки рухаються тільки в одному напрямку.

Отже, в структурі черг потрібні два вказівники: один - для посилання на вершину послідовності (для включення елемента), другий - для посилання на основу послідовності (для виключення елемента). При кожному виключенні елемента із такої структури виключається завжди найстаріший елемент. Черги обслуговуються за дисципліною FIFO - "перший прийшов, перший пішов".

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

Чергу, для якої є можливість включати або виключати елементи з певної позиції в залежності від деяких її характеристик називають пріоритетною чергою. Прикладом пріоритетної черги може служити порядок розв'язування потоку задач на комп‘ютері у деяких операційних системах. Така черга зводиться до послідовності лінійних черг, якщо відомі пріоритети її елементів. Кожна черга з послідовності обслуговується за дисципліною FIFO, але елементи з другої черги обслуговуються тільки тоді, коли порожня попередня черга, а з третьої тоді, коли порожні перша і друга черги. При включенні елементи приєднуються до боку однієї з черг згідно з їх пріоритетом.

Черги, в яких елементи Q₁,Q₂, …,Q_n розміщуються так, що за елементом Q_n іде елемент Q₁ називаються циклічними (рис. 7.1). Циклічну чергу також можна зобразити лінійною послідовністю, але при записі нового елемента на відміну від лінійної черги вся послідовність зсувається на одне поле і новий елемент записується знову на її початку. Вибірка елемента буде також виконуватися за вказівником на кінець послідовності.

Рис.7.1. Графічне зображення циклічної черги

Прикладом циклічної черги може служити робота обчислювальної системи з розподілом часу, з якою одночасно працює багато користувачів. Оскільки така система має переважно один блок обробки, що називають процесором, і одну пам ' ять, то в кожний момент часу ці ресурси належать одному користувачу. Для кожного користувача виділяється певний інтервал часу. Тільки на відміну від пріоритетної черги одна задача до кінця не розв ' язується, а "порціями" протягом виділеного їй інтервалу часу. Програми, що чекають на виконання, утворюють циклічну чергу.