Стек

Организация стека в виде одномерного упорядоченного по адресам массива. Показаны операции вталкивания и выталкивания данных из стека операциями push и pop.

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

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

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

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

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

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

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

При проталкивании (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 используют стековую модель вычислений[7].

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