Стек (англ. stack — стопка; читается стэк) — структура данных, представляющая собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.

В цифровом вычислительном комплексе стек называется магазином — по аналогии с магазином в огнестрельном оружии (стрельба начнётся с патрона, заряженного последним).

В 1946 Алан Тьюринг ввёл понятие стека^[1]. А в 1957 году немцы Клаус Самельсон и Фридрих Л. Бауэр запатентовали идею^[2].

В некоторых языках (например, Lisp, Python^[3]) стеком можно назвать любой список, так как для них доступны операции pop и push. В языке C++ стандартная библиотека имеет класс с реализованной структурой и методами^[4]. И т. д.

Программный стек

Организация в памяти

Зачастую стек реализуется в виде однонаправленного списка (каждый элемент списка указывает только на следующий). Но в таком случае невозможно применить операцию обхода элементов. А доступ возможен только к верхнему элементу структуры. Для обхода такой проблемы можно взять за основу двусвязный список (каждый элемент указывает на обоих соседей справа и слева). Кроме того, можно организовать его на обыкновенном массиве.

Значением переменной стека является указатель на вершину стека. Если стек пуст, то значение указателя равно NULL.

Пример реализации стека на языке Си:

struct stack
{
    char *data;
    struct stack *next;
};

Операции со стеком

Возможны три операции со стеком: добавление элемента (иначе проталкивание, push), удаление элемента (pop) и чтение головного элемента (peek)^[5].

При проталкивании (push) указывается новый элемент, указывающий на элемент, бывший до этого головой. Новый элемент теперь становится головным.

При удалении элемента убирается первый, а головным становится тот, на который был указатель у этого объекта (следующий элемент).

void push( STACK *ps, int x ) // Добавление в стек нового элемента
{
    if ( ps->size == STACKSIZE ) // Не переполнен ли стек?
    {
        fputs( "Error: stack overflow\n", stderr );
        abort();
    }
    else
    {
        ps->items[ps->size++] = x;
    }
}
 
int pop( STACK *ps ) // Удаление из стека
{
    if ( ps->size == 0 ) // Не опустел ли стек?
    {
        fputs( "Error: stack underflow\n", stderr );
        abort();
    }
    else
    {
        return ps->items[--ps->size];
    }
}

Аппаратный стек

В архитектуре X86 аппаратный стек — непрерывная область памяти, адресуемая специальными регистрами ESP (указатель стека) и SS (селектор сегмента стека)^[6].

До использования стека он должен быть инициализирован так, чтобы регистры SS:ESP указывали на область реальной оперативной памяти (стек в ПЗУ, естественно, работать не может). Прикладные программы, как правило, от операционной системы получают готовый к употреблению стек. В защищенном режиме сегмент состояния задачи содержит четыре селектора сегментов стека (для разных уровней привилегий), но в каждый момент используется только один стек^[7].

Область применения

Аппаратный стек

Стек применяется в случаях, когда необходимо организовать прерывания вызовов и возвратов (см. локальная область видимости у функций в си-подобных языках), либо в случаях, когда нужно организовать временное хранилище данных места в памяти (переменные, параметры функции)^[6].

Программный стек

Программный вид стека используется для обхода структур данных, например, дерево или граф. При использовании рекурсивных функций также будет применяться стек, но аппаратный его вид. Кроме этих назначений, стек используется для организации стековой машины.

Для отслеживания точек возврата из подпрограмм используется стек вызовов.

Арифметические сопроцессоры, программируемые микрокалькуляторы и язык Forth используют стековую модель вычислений^[8].

Идея стека используется в стековой машине среди стековых языков программирования.

Примечания