Стек

TL;DR

Стек (stack) — простейшая структура данных с доступом по принципу LIFO (last in, first out): элементы добавляются и удаляются только с одного конца — вершины. Операции push (положить наверх), pop (снять верхний), top/peek (посмотреть верхний) и empty выполняются за [math]\displaystyle{ O(1) }[/math]. Реализуется динамическим массивом или односвязным списком; в массивном варианте push амортизированно [math]\displaystyle{ O(1) }[/math] благодаря удвоению ёмкости. Стек лежит в основе стека вызовов (рекурсия), вычисления выражений, проверки скобок, обхода в глубину, отмены действий и монотонного стека (следующий больший элемент за [math]\displaystyle{ O(n) }[/math]). Ограничение — доступ только к вершине: к середине стека обратиться нельзя.

Свойство	Значение
Класс	Линейная структура данных; абстрактный тип «последним пришёл — первым вышел»
Порядок доступа	LIFO (last in, first out)
Операции	push, pop, top/peek, empty, size
Сложность	все операции [math]\displaystyle{ O(1) }[/math] (в массиве — амортизированно)
Память	[math]\displaystyle{ O(n) }[/math]
Реализации	динамический массив (std::vector, std::stack), односвязный список
Доступ	только к вершине (нет произвольного доступа)
Родственники	очередь (FIFO), двусторонняя очередь (deque), дек с ограничением
Где встречается	стек вызовов, парсеры, вычисление выражений, DFS, отмена действий, монотонные задачи

Определения

Стек — коллекция элементов, в которой добавление и удаление происходят с одного конца, называемого вершиной (top). Элемент, добавленный последним, удаляется первым (LIFO).

Операции:

• push(x) — положить [math]\displaystyle{ x }[/math] на вершину;
• pop() — снять и вернуть верхний элемент;
• top() / peek() — посмотреть верхний элемент, не снимая;
• empty() / size() — пуст ли стек и сколько в нём элементов.

Инвариант. Элементы хранятся в порядке добавления; снимается всегда последний добавленный. Стек либо пуст, либо имеет ровно одну вершину.

Переполнение/недостача. pop/top на пустом стеке — недостача (underflow, ошибка). Переполнение (overflow) возможно при фиксированной ёмкости; в динамическом массиве его нет, но возможен исчерпание памяти или переполнение стека вызовов.

Обозначения. [math]\displaystyle{ n }[/math] — число элементов; top — индекс/указатель вершины; амортизированные оценки — по последовательности операций.

Рис. 1. Операции стека выполняются только над вершиной; последний добавленный элемент снимается первым.

Мотивация и интуиция

Многие процессы вложены: функция вызывает функцию, скобка открывается внутри скобки, HTML-тег внутри тега, действие отменяется последним первым. Все они имеют «обратный» порядок разрешения: то, что открылось позже, закрывается раньше. Именно этот порядок LIFO и моделирует стек.

Достаточно хранить элементы «стопкой»: новый кладётся сверху, снимается тоже сверху. Никакого поиска, перестановок или индексации — все операции тривиальны и стоят [math]\displaystyle{ O(1) }[/math]. Простота стека обманчива: из него вырастают стек вызовов (на котором основана вся рекурсия), алгоритмы разбора и обхода, а его вариация — монотонный стек — решает целый класс задач за линейное время.

Интуитивная картинка: стопка тарелок — можно взять только верхнюю; чтобы достать нижнюю, надо снять верхние.

Устройство

Два классических представления:

• Динамический массив. Элементы лежат подряд, top — индекс последнего занятого. push пишет в a[++top], pop уменьшает top. При заполнении ёмкость удваивается (амортизированно [math]\displaystyle{ O(1) }[/math]).
• Односвязный список. Вершина — первый узел head. push добавляет узел в начало, pop сдвигает head. Нет фиксированной ёмкости, но есть накладные расходы на узлы.

В массиве push амортизированно [math]\displaystyle{ O(1) }[/math] (худший случай — [math]\displaystyle{ O(n) }[/math] при удвоении ёмкости), а pop/top — [math]\displaystyle{ O(1) }[/math]; в списке push/pop — строго [math]\displaystyle{ O(1) }[/math]. На практике чаще берут массив (кэш-дружелюбность) — так устроены std::stack (по умолчанию поверх std::deque) и std::vector.

Рис. 2. Массив с индексом вершины и односвязный список с вершиной в голове; обе реализации дают [math]\displaystyle{ O(1) }[/math] на push/pop.

Операции и алгоритмы

Операция: push / pop / top

Идея. Работать только с вершиной.

Пошаговое описание (массив).

1. push(x): увеличить top, записать x в a[top] (при необходимости расширить массив).
2. pop(): запомнить a[top], уменьшить top.
3. top(): вернуть a[top]; empty(): top < 0.

Инвариант. Элементы a[0..top] — содержимое стека, a[top] — вершина.

Псевдокод.

Алгоритм Push(S, x)
1  top[S] ← top[S] + 1
2  a[top[S]] ← x

Алгоритм Pop(S)
3  if top[S] < 0
4      error "недостача: стек пуст"
5  x ← a[top[S]]
6  top[S] ← top[S] − 1
7  return x

Алгоритм Top(S)
8  if top[S] < 0
9      error "недостача: стек пуст"
10 return a[top[S]]

Сложность: O(1) на операцию (в массиве — амортизированно). Память O(n).

Корректность: операции затрагивают только вершину, порядок элементов сохраняется.

Крайние случаи. pop/top на пустом стеке — ошибка. push при заполненной ёмкости — расширение.

Операция: динамический рост (амортизация)

Идея. При заполнении массива удвоить ёмкость и скопировать элементы; pop обычно не сжимает (или сжимает при сильном опустошении).

Инвариант. size ≤ capacity; при удвоении копия сохраняет порядок.

Псевдокод.

Алгоритм Push-Growable(S, x)
1  if size[S] = capacity[S]
2      capacity[S] ← 2 · capacity[S]
3      скопировать a в массив новой ёмкости
4  a[size[S]] ← x;  size[S] ← size[S] + 1

Сложность: худший случай одного push — O(n), но n операций суммарно O(n), то есть амортизированно O(1).

Пример: стек вызовов и рекурсия

Любая рекурсия использует стек вызовов: каждый вызов создаёт кадр (аргументы, локальные, адрес возврата). Кадры накапливаются вниз по рекурсии и снимаются на возвратах. Глубина рекурсии равна числу кадров; рекурсия без базы переполняет стек. Любую рекурсию можно переписать явным стеком.

Разбор. fact(3): кадры main → fact(3) → fact(2) → fact(1); fact(1) возвращает 1, затем кадры снимаются в обратном порядке (рис. 3).

Рис. 3. Кадры рекурсии fact(3): при вызовах стек растёт, при возвратах — снимается в обратном порядке.

Пример: монотонный стек (следующий больший элемент)

Идея. Хранить в стеке индексы с убывающими значениями. Пока новый элемент больше вершины, вершина снимается — для неё найден следующий больший. Каждый индекс входит и снимается один раз → [math]\displaystyle{ O(n) }[/math].

Алгоритм Next-Greater(A[1..n])
1  создать стек индексов S;  res[1..n] ← −1
2  for i ← 1 to n
3      while S не пуст и A[top[S]] < A[i]
4          res[top[S]] ← A[i]
5          Pop(S)
6      Push(S, i)
7  return res

Сложность: O(n) — каждый индекс кладётся и снимается по разу.

Рис. 4. Следующий больший элемент для [math]\displaystyle{ [2,1,5,3,4] }[/math] через убывающий монотонный стек.

Реализация на C++

Две реализации стека (массив и список), плюс два классических применения.

#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <stdexcept>

// Стек на динамическом массиве
template <typename T>
class ArrayStack {
    std::vector<T> a_;
public:
    void push(const T& x) { a_.push_back(x); }
    void pop() {
        if (a_.empty()) throw std::underflow_error("pop on empty stack");
        a_.pop_back();
    }
    const T& top() const {
        if (a_.empty()) throw std::underflow_error("top on empty stack");
        return a_.back();
    }
    bool empty() const { return a_.empty(); }
    std::size_t size() const { return a_.size(); }
};

// Стек на односвязном списке
template <typename T>
class LinkedStack {
    struct Node { T val; Node* next; };
    Node* head_ = nullptr;
    std::size_t n_ = 0;
public:
    LinkedStack() = default;
    ~LinkedStack() { while (head_) { Node* t = head_; head_ = head_->next; delete t; } }
    LinkedStack(const LinkedStack&) = delete;
    LinkedStack& operator=(const LinkedStack&) = delete;

    void push(const T& x) { head_ = new Node{x, head_}; ++n_; }
    void pop() {
        if (!head_) throw std::underflow_error("pop on empty stack");
        Node* t = head_;
        head_ = head_->next;
        delete t;
        --n_;
    }
    const T& top() const {
        if (!head_) throw std::underflow_error("top on empty stack");
        return head_->val;
    }
    bool empty() const { return head_ == nullptr; }
    std::size_t size() const { return n_; }
};

// Проверка сбалансированности скобок
bool balanced(const std::string& s) {
    ArrayStack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (st.empty()) return false;
            char o = st.top();
            st.pop();
            if ((c == ')' && o != '(') ||
                (c == ']' && o != '[') ||
                (c == '}' && o != '{')) return false;
        }
    }
    return st.empty();
}

// Следующий больший элемент (монотонный стек)
std::vector<int> nextGreater(const std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    std::vector<int> res(n, -1);
    ArrayStack<int> st;                 // хранит индексы
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && a[st.top()] < a[i]) {
            res[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    return res;
}

int main() {
    // 1) базовые операции над массивом
    ArrayStack<int> s;
    for (int x : {1, 2, 3}) s.push(x);
    assert(s.top() == 3 && s.size() == 3);
    s.pop();
    assert(s.top() == 2);

    // 2) LIFO-порядок на списке
    LinkedStack<int> l;
    for (int x : {1, 2, 3, 4}) l.push(x);
    std::vector<int> out;
    while (!l.empty()) { out.push_back(l.top()); l.pop(); }
    assert((out == std::vector<int>{4, 3, 2, 1}));

    // 3) скобки
    assert(balanced("([]{})"));
    assert(!balanced("([)]"));
    assert(!balanced("("));

    // 4) следующий больший
    std::vector<int> a = {2, 1, 5, 3, 4};
    std::vector<int> g = nextGreater(a);
    assert((g == std::vector<int>{5, 5, -1, 4, -1}));

    std::cout << "ok\n";
    return 0;
}

Замечания по реализации.

• В стандартной библиотеке C++ стек — std::stack<T, Container>; по умолчанию контейнер std::deque, можно взять std::vector.
• std::stack предоставляет только push/pop/top/empty/size — без обхода.
• Реализация на массиве кэш-дружелюбнее; список обходится без перевыделения.
• Не забывайте про недостачу: top/pop на пустом стеке — ошибка (в std::stack — UB, проверяйте empty()).

Сводная таблица сложности

Операция	Худший	Амортизированная	Память	Примечание
Push	[math]\displaystyle{ O(1) }[/math] (массив: [math]\displaystyle{ O(n) }[/math] при расширении)	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	список — строго [math]\displaystyle{ O(1) }[/math]
Pop	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]
Top / Peek	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	просмотр вершины
Empty / Size	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]
Поиск элемента	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(1) }[/math]	не свойственная стеку операция
Память структуры	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math]	+ запас ёмкости в массиве

Примечание. Отдельный push в динамическом массиве может стоить [math]\displaystyle{ O(n) }[/math] (копирование при удвоении), но серия из [math]\displaystyle{ n }[/math] добавлений — [math]\displaystyle{ O(n) }[/math] суммарно, значит амортизированно [math]\displaystyle{ O(1) }[/math] на операцию (тот же аргумент «геометрического роста», что у динамического массива). Списочный стек даёт строгое [math]\displaystyle{ O(1) }[/math], но платит аллокацией узлов.

Рис. 5. Все операции — [math]\displaystyle{ O(1) }[/math]; в массиве push амортизированно [math]\displaystyle{ O(1) }[/math] из-за удвоения ёмкости.

Трассировка примера

Операции над стеком (слева — вершина). Покажем содержимое после каждой команды.

Шаг	Операция	Стек (вершина слева)	Результат
1	push(10)	[10]	—
2	push(20)	[20, 10]	—
3	push(30)	[30, 20, 10]	—
4	top()	[30, 20, 10]	30
5	pop()	[20, 10]	30
6	pop()	[10]	20
7	push(40)	[40, 10]	—
8	pop()	[10]	40
9	empty()	[10]	false
10	pop()	[]	10

Порядок извлечения 30, 20, 40, 10 — «обратный» порядку добавления (с учётом промежуточной вставки 40): это и есть LIFO.

Корректность и оценка сложности

Лемма (LIFO):

После любой последовательности операций push/pop порядок элементов в стеке — это порядок их добавления, а pop возвращает последний добавленный из оставшихся.

Доказательство:

Индукция по числу операций. push добавляет элемент в конец (на вершину); pop удаляет из конца. Последовательность хранится как стек-массив a[0..top]; вершина — a[top].

[math]\displaystyle{ \blacksquare }[/math]

Лемма (корректность монотонного стека):

Next-Greater для каждого [math]\displaystyle{ i }[/math] возвращает ближайший [math]\displaystyle{ j \gt i }[/math] с [math]\displaystyle{ A[j] \gt A[i] }[/math] либо [math]\displaystyle{ -1 }[/math].

Доказательство:

В стеке поддерживаются индексы с убывающими значениями. При поступлении [math]\displaystyle{ A[i] }[/math] снимаются все меньшие вершины — для них [math]\displaystyle{ i }[/math] и есть ближайший больший справа (все промежуточные уже сняты ранее и не могли быть большими). Оставшиеся больше [math]\displaystyle{ A[i] }[/math] и ждут своего большего.

[math]\displaystyle{ \blacksquare }[/math]

Теорема (амортизированная стоимость):

Последовательность из [math]\displaystyle{ n }[/math] операций push в стек с удвоением ёмкости стоит [math]\displaystyle{ O(n) }[/math] суммарно.

Доказательство:

Копирование при удвоении стоит [math]\displaystyle{ O }[/math](размер). Сумма по всем удвоениям геометрическая: [math]\displaystyle{ 1 + 2 + 4 + \dots + n/2 \lt n }[/math]. Значит, суммарно [math]\displaystyle{ O(n) }[/math], то есть [math]\displaystyle{ O(1) }[/math] амортизированно на push.

[math]\displaystyle{ \blacksquare }[/math]

Оценка. push/pop/top — [math]\displaystyle{ O(1) }[/math] (в массиве амортизированно); память [math]\displaystyle{ O(n) }[/math]; balanced и nextGreater — [math]\displaystyle{ O(n) }[/math] времени.

Сравнение с альтернативами

Структура	Порядок доступа	push	pop	Произвольный доступ
Стек	LIFO	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	нет
Очередь (queue)	FIFO	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	нет
Двусторонняя очередь (deque)	оба конца	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	нет
Очередь с приоритетом	по приоритету	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	нет
Динамический массив	по индексу	[math]\displaystyle{ O(1) }[/math] аморт.	[math]\displaystyle{ O(1) }[/math] с конца	да, [math]\displaystyle{ O(1) }[/math]
Связный список	по позиции	[math]\displaystyle{ O(1) }[/math] в начало	[math]\displaystyle{ O(1) }[/math] из начала	нет, [math]\displaystyle{ O(n) }[/math]

Вердикт. Стек выбирают, когда важен вложенный порядок разрешения: вызовы, скобки, отмена, обход в глубину, монотонные задачи. Если нужен порядок «пришёл первым — ушёл первым» — берут очередь; если нужен произвольный доступ — массив.

Где применяется

1. Стек вызовов и рекурсия. Любой вызов функции кладёт кадр на стек; хвостовая рекурсия и явный стек заменяют глубокую рекурсию.
2. Вычисление выражений. Постфиксные (RPN) выражения вычисляются стеком; инфиксные переводятся в постфиксные (алгоритм сортировочной станции Дейкстры).
3. Синтаксический анализ. Проверка скобок, разбор вложенных тегов/блоков, парсеры с рекурсивным спуском.
4. Обход в глубину (DFS). Итеративный DFS хранит вершины в стеке; рекурсивный использует стек вызовов.
5. Монотонный стек. Следующий больший/меньший элемент, гистограммы, «сколько дней до тепла» — за [math]\displaystyle{ O(n) }[/math].
6. Отмена действий (undo/redo) и «назад». Два стека для отмены и повтора; история в браузере.
7. Oбработка отката и backtracking. Возврат по лабиринту, перебор с возвратом, рекурсивные алгоритмы с откатом.

Рис. 6. Баланс скобок, вычисление постфиксных выражений, обход в глубину, отмена действий.

Историческая справка

• 1946–1950-е. Идея стека возникла вместе с архитектурой вычислительных машин; Тьюринг и фон Нейман использовали стекоподобную организацию для возврата из подпрограмм ⚠️ точные детали.
• 1957. Ф. Бауэр и К. Замельсон ввели термин «стек» (нем. Keller) и структуры ввода-вывода стека; позже термин закрепился в программировании ⚠️.
• 1960-е. Стеки стали основой стековых машин и языков (Forth, PostScript) и вычислителей выражений.
• 1965. Э. Дейкстра описал алгоритм «сортировочной станции» для перевода выражений со стеком.
• Стек вызовов — неотъемлемая часть большинства архитектур и языков с процедурами.

Типичные ошибки и подводные камни

• Недостача (underflow). pop/top на пустом стеке — ошибка (в std::stack — UB); проверяйте empty().
• Переполнение стека вызовов. Глубокая рекурсия без базы или с [math]\displaystyle{ O(n) }[/math] глубиной переполняет стек; используйте явный стек или хвостовую рекурсию.
• Фиксированная ёмкость. Массивный стек без расширения переполняется; используйте динамический.
• Путаница LIFO/FIFO. Стек — «последним пришёл», очередь — «первым пришёл»; не путайте.
• Доступ к середине. У стека его нет; если нужен — возьмите массив/список.
• Итерация по std::stack. Нельзя без извлечения; std::stack не даёт итераторов.
• std::stack::pop() не возвращает значение. Сначала top(), затем pop().
• Забыть про сжатие ёмкости. Долго живущий стек после массовых pop может держать большой буфер.
• Изменение ёмкости и инвалидация. При росте массива ссылки/указатели на элементы становятся недействительными.
• Рекурсия и явный стек. Переписывая рекурсию на стек, легко потерять порядок обхода (перепутать push соседей).

Задачи для практики

1. Реализация. Реализуйте стек массивом и списком; проверьте LIFO и амортизацию. Подсказка: удвоение ёмкости.
2. Баланс скобок. Проверьте строку со скобками ()[]{}. Подсказка: стек открытых скобок.
3. Постфиксное выражение. Вычислите RPN-выражение стеком. Подсказка: число — push, операция — два pop.
4. Инфикс → постфикс. Реализуйте сортировочную станцию. Подсказка: стек операций и приоритеты.
5. Минимум в стеке. Реализуйте min() за [math]\displaystyle{ O(1) }[/math] (дополнительный стек минимумов). Подсказка: два стека.
6. Следующий больший. Решите монотонным стеком за [math]\displaystyle{ O(n) }[/math]. Подсказка: убывающий стек индексов.
7. Очередь двумя стеками. Реализуйте FIFO-очередь на двух стеках. Подсказка: входной и выходной.
8. Итеративный DFS. Обойдите граф в глубину явным стеком. Подсказка: порядок push соседей обратен порядку обхода.

Связанные темы

• Очередь — противоположный порядок FIFO; стек и очередь — два крайних случая deque.
• Персистентный стек — стек, сохраняющий все версии за [math]\displaystyle{ O(1) }[/math] на операцию.
• Очередь с приоритетом — структура с другим порядком извлечения.
• Графы (план) — обход в глубину на стеке.
• Двоичная куча — другой пример линейного/древовидного контейнера.
• Асимптотическая сложность — нотация [math]\displaystyle{ O }[/math] и амортизация.

Источники

1. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 10 «Elementary Data Structures» (стек, очередь, связные списки).
2. Knuth D. E. The Art of Computer Programming. Vol. 1: Fundamental Algorithms. — Addison-Wesley, 3rd ed., 1997. — §2.2.1 «Stacks, Queues, and Deques».
3. Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — Гл. 1.3 (стек, очередь, вычисление выражений).
4. Dijkstra E. W. Algol 60 Translation (алгоритм «сортировочной станции»). — 1961/1965.
5. Wikipedia: Stack (abstract data type). URL: https://en.wikipedia.org/wiki/Stack_(abstract_data_type).