Стек

Матеріал з Вікіпедії — вільної енциклопедії.

СТЕК в інформатиці та програмуванні -- різновид лінійного списку, структура даних, яка працює за принципом (дисципліною) "останнім прийшов -- першим пішов" (LIFO, last in, first out). Всі операції (наприклад, видалення елементу) в стеку можна проводити тільки з одним елементом, який знаходиться на верхівці стеку та був введений в стек останнім.

Стек можна розглядати як певну аналогію до стопки тарілок, з якої можна взяти верхню, і на яку можна покласти верхню тарілку (інша назва стеку -- "магазин", за аналогією з принципом роботи магазину в автоматичній зброї)

[ред.] Операції зі стеком

push ("заштовхнути елемент"): елемент додається в стек та розміщується в його верхівці. Розмір стеку збільшуеться на одиницю. При перевищенні розміра стека граничної величини, відбувається переповнення стека (stack overflow)

pop ("виштовхнути елемент"): отримує елемент з верхівки стеку. При цьому він видаляється зі стеку і його місце в верхівці стеку займає наступний за ним відповідно до правила LIFO, а розмір стеку зменшується на одиницю. При намаганні "виштовхнути" елемент з вже пустого стеку, відбувається ситуація "незаповнення" стеку (stack underflow)

Кожна з цих операцій зі стеком виконується за фіксований час O(1) і не залежить від розміру стеку.

Додаткові операції (присутні не у всіх реалізаціях стеку):

isEmpty: перевірка наявності елементів в стеку; результат: істина (true), коли в стеку немає елементів.
isFull: перевірка заповненості стека. Результат: істина, коли додавання нового елементу неможливе
clear: звільнити стек (видалити усі елементи).
top: отримати верхній елемент (без виштовхування).
size: отримати розмір (кількість елементів) стека.
swap: поміняти два верхніх елементи місцями.

[ред.] Організація в пам'яті комп'ютера

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

Багато процесорів ЕОМ мають спеціалізовані регістри, які використовуються як вказівники на верхівку стеку, або використовують деякі з регістрів загального вжитку для цієї спеціальної функції в певних режимах адресації пам'яті.

[ред.] Приклади застосування

Калькулятори, які використовують зворотню польську нотацію, використовують стек для збереження даних обчислень.

Існує велика кількість "стеко-орієнтованих" мов програмування (Forth, PostScript), які використовують стек як базову структуру даних при виконанні багатьох операцій (арифметичних, логічних, вводу-виводу тощо).

Стеко-орієнтованими є багато з віртуальних машин, наприклад віртуальна машина Java.

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

[ред.] Реалізація базових алгоритмів

На високорівневих мовах програмування, стек може бути реалізований за допомогою масиву та додаткової змінної:

Для зберігання елементів стеку резервується масив S[1..n] певного розміру та додаткова змінна top[S], яка буде зберігати індекс верхівки стеку.

Операції push та pop тоді можуть бути записані так (без перевірки на переповнення та "незаповнення"):

PUSH (S, x)
1 top[S]:= top[S]+1 //збільшення індексу на 1
2 S[top[S]]:=x //запис нового елемента у верхівку стека

POP (S)
1 top[S]:=top[S]-1 // зменшення індексу на 1
2 return S[top[S]+1] //повернення колишньої верхівки стеку