Стек

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Иллюстрация организации стека

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

Область применения[править | править вики-текст]

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

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

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

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

Аппаратный стек[править | править вики-текст]

При вызове подпрограммы (процедуры) процессор кладёт в стек адрес команды, следующей за командой вызова подпрограммы «адрес возврата» из подпрограммы. По команде возврата из подпрограммы из стека вынимается адрес возврата и осуществляется переход по этому адресу. Аналогичные процессы происходят при прерывании (процессор X86 при прерывании сохраняет в стеке ещё и регистр флагов). Кроме того, компиляторы размещают локальные переменные процедур в стеке (если в процессоре предусмотрен доступ к произвольному месту стека).

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

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

Примечания[править | править вики-текст]