25900 авторів і 91 редактор відповіли на 98952 питання,
розмістивши 129771 посилання на 81900 сайтів, приєднуйтесь!

Реклама партнерів:

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

РедагуватиУ обранеДрук

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

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

Реклама партнерів:

РедагуватиУ обранеДрук

Схожі питання


Увага, тільки СЬОГОДНІ!
«Що таке стек в програмуванні?»

В інших пошукових системах:

GoogleЯndexRamblerВікіпедія

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