Стек (англ. 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());
}
}
=====================
Источники информации: