Що таке стек в програмуванні?

Стек (англ. 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 ());
}
}

=====================

Джерела інформації:

  • ru.wikipedia.org – Вікіпедія: Стек;
  • firststeps.ru – що таке стек;
  • progclub.ru – стек.

Category: Медицина і здоров'я

Comments (Прокоментуй!)

There are no comments yet. Why not be the first to speak your mind.

Leave a Reply