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

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

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

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

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

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

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

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

Но также часто стек располагается в одномерном массиве с упорядоченными адресами. Такая организация стека удобна, если элемент информации занимает в памяти фиксированное количество слов, например, 1 слово. При этом отпадает необходимость хранения в элементе стека явного указателя на следующий элемент стека, что экономит память. При этом указатель стека ( Stack Pointer , — SP ) обычно является регистром процессора и указывает на адрес головы стека.

Предположим для примера, что голова стека расположена по меньшему адресу, следующие элементы располагаются по нарастающим адресам. При каждом вталкивании слова в стек SP сначала увеличивается на 1 и затем по адресу из SP производится запись в память. При каждом извлечении слова из стека (выталкивании) сначала производится чтение по текущему адресу из SP и последующее уменьшение содержимого SP на 1.

При организации стека в виде однонаправленного списка значением переменной стека является указатель на его вершину — адрес вершины. Если стек пуст, то значение указателя равно NULL.

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

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

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

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

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

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

#include <iostream>
#include <cassert>
#include <stack> // стандартная реализация стека в C++

int main()
{
    std::stack<int> stk; // стек элементов типа int

    std::cout << "Введите целые числа (-1, чтобы закончить ввод):" << std::endl;

    while (true)
    {
        int num;
        std::cin >> num;

        if (num == -1)
            break;

        stk.push(num); // добавляем элемент в стек
    }

    std::cout << "В стеке " << stk.size() << " элементов" << std::endl;

    // stk.size() изменяется при добавлении/удалении, поэтому
    // цикл 
    //  for (int i = 0; i < stk.size(); i++) { ... }
    // будет вести себя неправильно
    for (int i = stk.size(); i > 0; i--)
    {
        // выводим верхний элемент (peek)
        std::cout << "Верхний элемент: " << stk.top() << std::endl;

        // удаляем верхний элемент
        stk.pop();
    }

    assert(stk.empty()); // стек пустой

    return 0;
}

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

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

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

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

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

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

Другое название аппаратного стека — машинный стек. Работа с ним поддерживается аппаратно центральным процессором. Машинный стек используется для нужд выполняющейся программы: хранения переменных и вызова подпрограмм . При вызове подпрограммы (процедуры) процессор помещает в стек адрес команды, следующей за командой вызова подпрограммы «адрес возврата» из подпрограммы. По команде возврата из подпрограммы из стека извлекается адрес возврата в вызвавшую подпрограмму программу и осуществляется переход по этому адресу.

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

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

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

Примечания