Стек

Стек (

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

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

В некоторых языках (например,

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

Но также часто стек располагается в

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

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

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

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

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

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

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

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

        if (num == -1)
            break;

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

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

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

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

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

    return 0;
}

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

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

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

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

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

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

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

	Имеется викиучебник по теме «Реализации алгоритмов/Стек»