Стек (Англ. stack - стопка) - структура даних з методом доступу до елементів LIFO (Англ. Last In - First Out, «останнім прийшов - першим вийшов»). Стек - це часто зустрічається в програмуванні конструкція. У радянській літературі стек іноді називають магазином за аналогією з магазином автомата, з якого патрони виходять в порядку, зворотному порядку їх додавання.
Приклад: На стіл кладеться книга. Зверху на неї ще одна книга. Зверху ще одна і т.д. Перша книга внизу. Щоб її дістати, спочатку потрібно зняти всі книги, які лежать на ній і тільки після цього з'явиться доступ до першої.
Додавання елемента в (на) стек називається проштовхуванням (push).
Витяг (видалення) елемента з (зі) стека називається виштовхування (pop).
Типові помилки, що виникають при роботі зі стеком: переповнення стека і вичерпання стека.
Одне з найбільш важливих застосувань стека - організація виклику підпрограм. У точці виклику на стеку зберігається адреса повернення з підпрограми після її завершення (і, можливо, передані параметри). При кожному вкладеному (в т.ч. при рекурсивному) виклику підпрограм на стек додаються нові адреси повернення. При кожній операції повернення з підпрограми (return), Зі стека знімається адресу повернення і управління передається по ньому. Це застосування є настільки важливим для програмування, що в більшості процесорів стек повернення реалізований апаратно в системі команд. Однак в інших випадках стек доводиться моделювати на більш загальних структурах даних.
Найбільш поширені дві принципу реалізації стека: на базі масиву і на базі пов'язаного списку. У першому випадку для зберігання значень в пам'яті відводиться суцільний масив осередків, які використовуються в міру необхідності. У другому - для кожного елемента стека замовляється блок пам'яті, достатній для зберігання значення і посилань на попередній і наступний елементи стека. Реалізація на базі масиву простіше, ефективніше і економніше по витраті пам'яті, але вона вимагає заздалегідь знати граничний розмір стека і може призводити до важко виявляти помилки. Реалізація на базі списків більш надійна, але менш ефективна.
Нижче наводиться приклад програми на мові Сі, що моделює стек цілочисельних значень на базі масиву.
=====================
int stack [10] - / * відводимо на на стек 10 осередків * /
int in_stack = 0- / * скільки зараз елементів в стеку * /
/ * Занесення значення в стек * /
void push (int x)
{
stack [in_stack] = x-
in_stack ++ -
}
/ * Зняти значення зі стека * /
int pop ()
{
if (in_stack == 0)
{
printf ("Стек порожній, помилка. n") -
return (-1) -
}
in_stack ---
return stack [in_stack] -
}
void main ()
{
push (1) -
push (2) -
push (3) -
while (in_stack> 0)
{
printf ("top =% d n", pop ()) -
}
}
=====================