Стек - История изменений

СВ: /* Устройство */

2026-10-25T20:30:22Z

Устройство

← Предыдущая		Версия 20:30, 25 октября 2026
Строка 60:		Строка 60:
	* '''Односвязный список.''' Вершина — первый узел <code>head</code>. <code>push</code> добавляет узел в начало, <code>pop</code> сдвигает <code>head</code>. Нет фиксированной ёмкости, но есть накладные расходы на узлы.		* '''Односвязный список.''' Вершина — первый узел <code>head</code>. <code>push</code> добавляет узел в начало, <code>pop</code> сдвигает <code>head</code>. Нет фиксированной ёмкости, но есть накладные расходы на узлы.

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

	[[Файл:stack-02-implementations.svg\|frame\|none\|700px\|Рис. 2. Массив с индексом вершины и односвязный список с вершиной в голове; обе реализации дают <math>O(1)</math> на <code>push</code>/<code>pop</code>.]]		[[Файл:stack-02-implementations.svg\|frame\|none\|700px\|Рис. 2. Массив с индексом вершины и односвязный список с вершиной в голове; обе реализации дают <math>O(1)</math> на <code>push</code>/<code>pop</code>.]]

СВ: /* Источники */

2026-09-30T19:05:12Z

Источники

← Предыдущая		Версия 19:05, 30 сентября 2026
Строка 433:		Строка 433:
	# Dijkstra E. W. Algol 60 Translation (алгоритм «сортировочной станции»). — 1961/1965.		# Dijkstra E. W. Algol 60 Translation (алгоритм «сортировочной станции»). — 1961/1965.
	# Wikipedia: Stack (abstract data type). URL: https://en.wikipedia.org/wiki/Stack_(abstract_data_type).		# Wikipedia: Stack (abstract data type). URL: https://en.wikipedia.org/wiki/Stack_(abstract_data_type).

			[[Category:Алгоритмы и структуры данных]]

СВ: /* Корректность и оценка сложности */

2026-09-29T21:09:12Z

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

← Предыдущая		Версия 21:09, 29 сентября 2026
Строка 332:		Строка 332:
	== Корректность и оценка сложности ==		== Корректность и оценка сложности ==

	~~'''~~Лемма ~~1 (~~LIFO~~).'''~~ После любой последовательности операций <code>push</code>/<code>pop</code> порядок элементов в стеке — это порядок их добавления, а <code>pop</code> возвращает последний добавленный из оставшихся.		{{Лемма
			\|about=LIFO
			\|statement=После любой последовательности операций <code>push</code>/<code>pop</code> порядок элементов в стеке — это порядок их добавления, а <code>pop</code> возвращает последний добавленный из оставшихся.
			\|proof=Индукция по числу операций. <code>push</code> добавляет элемент в конец (на вершину); <code>pop</code> удаляет из конца. Последовательность хранится как стек-массив <code>a[0..top]</code>; вершина — <code>a[top]</code>.
			}}

	~~''Доказательство.'' Индукция по числу операций.~~ <code>~~push~~</code> ~~добавляет элемент в конец (на вершину);~~ <~~code~~>~~pop~~</~~code~~> ~~удаляет из конца. Последовательность хранится как стек~~-~~массив~~ <~~code~~>~~a[0~~..~~top~~]</~~code~~>~~; вершина~~ — <~~code~~>~~a[top]~~</~~code~~>. <math>~~\blacksquare~~</math>		{{Лемма
			\|about=корректность монотонного стека
			\|statement=<code>Next-Greater</code> для каждого <math>i</math> возвращает ближайший <math>j > i</math> с <math>A[j] > A[i]</math> либо <math>-1</math>.
			\|proof=В стеке поддерживаются индексы с убывающими значениями. При поступлении <math>A[i]</math> снимаются все меньшие вершины — для них <math>i</math> и есть ближайший больший справа (все промежуточные уже сняты ранее и не могли быть большими). Оставшиеся больше <math>A[i]</math> и ждут своего большего.
			}}

	'''Лемма 2 (корректность монотонного стека).''' <code>Next-Greater</code> для каждого <math>i</math> возвращает ближайший <math>j > i</math> с <math>A[j] > A[i]</math> либо <math>-1</math>.		{{Теорема
			\|about=амортизированная стоимость
	''Доказательство.'' В стеке поддерживаются индексы с убывающими значениями. При поступлении <math>A[i]</math> снимаются все меньшие вершины — для них <math>i</math> и есть ближайший больший справа (все промежуточные уже сняты ранее и не могли быть большими). Оставшиеся больше <math>A[i]</math> и ждут своего большего. <math>\blacksquare</math>		\|statement=Последовательность из <math>n</math> операций <code>push</code> в стек с удвоением ёмкости стоит <math>O(n)</math> суммарно.
			\|proof=Копирование при удвоении стоит <math>O</math>(размер). Сумма по всем удвоениям геометрическая: <math>1 + 2 + 4 + \dots + n/2 < n</math>. Значит, суммарно <math>O(n)</math>, то есть <math>O(1)</math> амортизированно на <code>push</code>.
	~~'''Теорема 3 (~~амортизированная стоимость~~).'''~~ Последовательность из <math>n</math> операций <code>push</code> в стек с удвоением ёмкости стоит <math>O(n)</math> суммарно.		}}

	~~''Доказательство.''~~ Копирование при удвоении стоит <math>O</math>(размер). Сумма по всем удвоениям геометрическая: <math>1 + 2 + 4 + \dots + n/2 < n</math>. Значит, суммарно <math>O(n)</math>, то есть <math>O(1)</math> амортизированно на <code>push</code>. ~~<math>\blacksquare</math>~~

	'''Оценка.''' <code>push</code>/<code>pop</code>/<code>top</code> — <math>O(1)</math> (в массиве амортизированно); память <math>O(n)</math>; <code>balanced</code> и <code>nextGreater</code> — <math>O(n)</math> времени.		'''Оценка.''' <code>push</code>/<code>pop</code>/<code>top</code> — <math>O(1)</math> (в массиве амортизированно); память <math>O(n)</math>; <code>balanced</code> и <code>nextGreater</code> — <math>O(n)</math> времени.

СВ: /* Пример: стек вызовов и рекурсия */

2026-09-29T21:06:27Z

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

← Предыдущая		Версия 21:06, 29 сентября 2026
Строка 128:		Строка 128:
	'''Разбор.''' <code>fact(3)</code>: кадры <code>main → fact(3) → fact(2) → fact(1)</code>; <code>fact(1)</code> возвращает 1, затем кадры снимаются в обратном порядке (рис. 3).		'''Разбор.''' <code>fact(3)</code>: кадры <code>main → fact(3) → fact(2) → fact(1)</code>; <code>fact(1)</code> возвращает 1, затем кадры снимаются в обратном порядке (рис. 3).

	[[Файл:stack-03-callstack.svg\|~~thumb~~\|700px\|Рис. 3. Кадры рекурсии <code>fact(3)</code>: при вызовах стек растёт, при возвратах — снимается в обратном порядке.]]		[[Файл:stack-03-callstack.svg\|frame\|none\|700px\|Рис. 3. Кадры рекурсии <code>fact(3)</code>: при вызовах стек растёт, при возвратах — снимается в обратном порядке.]]

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

СВ: Новая страница: «== TL;DR == Стек (stack) — простейшая структура данных с доступом по принципу '''LIFO''' (last in, first out):...»

2026-09-29T21:05:44Z

Новая страница: «== TL;DR == Стек (stack) — простейшая структура данных с доступом по принципу '''LIFO''' (last in, first out):...»

Новая страница

== TL;DR ==

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

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

== Определения ==

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

'''Операции:'''

* <code>push(x)</code> — положить <math>x</math> на вершину;
* <code>pop()</code> — снять и вернуть верхний элемент;
* <code>top()</code> / <code>peek()</code> — посмотреть верхний элемент, не снимая;
* <code>empty()</code> / <code>size()</code> — пуст ли стек и сколько в нём элементов.

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

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

'''Обозначения.''' <math>n</math> — число элементов; <code>top</code> — индекс/указатель вершины; амортизированные оценки — по последовательности операций.

[[Файл:stack-01-adt.svg|thumb|700px|Рис. 1. Операции стека выполняются только над вершиной; последний добавленный элемент снимается первым.]]

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

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

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

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

== Устройство ==

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

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

Обе реализации дают <math>O(1)</math> на операцию. На практике чаще берут массив (кэш-дружелюбность) — так устроены <code>std::stack</code> (по умолчанию поверх <code>std::deque</code>) и <code>std::vector</code>.

[[Файл:stack-02-implementations.svg|frame|none|700px|Рис. 2. Массив с индексом вершины и односвязный список с вершиной в голове; обе реализации дают <math>O(1)</math> на <code>push</code>/<code>pop</code>.]]

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

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

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

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

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

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

'''Псевдокод.'''

<syntaxhighlight lang="text">
Алгоритм 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]]
</syntaxhighlight>

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

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

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

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

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

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

'''Псевдокод.'''

<syntaxhighlight lang="text">
Алгоритм 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
</syntaxhighlight>

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

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

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

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

[[Файл:stack-03-callstack.svg|thumb|700px|Рис. 3. Кадры рекурсии <code>fact(3)</code>: при вызовах стек растёт, при возвратах — снимается в обратном порядке.]]

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

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

<syntaxhighlight lang="text">
Алгоритм 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
</syntaxhighlight>

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

[[Файл:stack-04-monotonic.svg|frame|none|700px|Рис. 4. Следующий больший элемент для <math>[2,1,5,3,4]</math> через убывающий монотонный стек.]]

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

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

<syntaxhighlight lang="cpp" line>
#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;
}
</syntaxhighlight>

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

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

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

{| class="wikitable"
|-
! Операция !! Худший !! Амортизированная !! Память !! Примечание
|-
| Push || <math>O(1)</math> (массив: <math>O(n)</math> при расширении) || <math>O(1)</math> || <math>O(1)</math> || список — строго <math>O(1)</math>
|-
| Pop || <math>O(1)</math> || <math>O(1)</math> || <math>O(1)</math> ||
|-
| Top / Peek || <math>O(1)</math> || <math>O(1)</math> || <math>O(1)</math> || просмотр вершины
|-
| Empty / Size || <math>O(1)</math> || <math>O(1)</math> || <math>O(1)</math> ||
|-
| Поиск элемента || <math>O(n)</math> || <math>O(n)</math> || <math>O(1)</math> || не свойственная стеку операция
|-
| Память структуры || <math>O(n)</math> || <math>O(n)</math> || <math>O(n)</math> || + запас ёмкости в массиве
|}

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

[[Файл:stack-05-complexity.svg|frame|none|700px|Рис. 5. Все операции — <math>O(1)</math>; в массиве <code>push</code> амортизированно <math>O(1)</math> из-за удвоения ёмкости.]]

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

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

{| class="wikitable"
|-
! Шаг !! Операция !! Стек (вершина слева) !! Результат
|-
| 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
|}

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

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

'''Лемма 1 (LIFO).''' После любой последовательности операций <code>push</code>/<code>pop</code> порядок элементов в стеке — это порядок их добавления, а <code>pop</code> возвращает последний добавленный из оставшихся.

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

'''Лемма 2 (корректность монотонного стека).''' <code>Next-Greater</code> для каждого <math>i</math> возвращает ближайший <math>j > i</math> с <math>A[j] > A[i]</math> либо <math>-1</math>.

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

'''Теорема 3 (амортизированная стоимость).''' Последовательность из <math>n</math> операций <code>push</code> в стек с удвоением ёмкости стоит <math>O(n)</math> суммарно.

''Доказательство.'' Копирование при удвоении стоит <math>O</math>(размер). Сумма по всем удвоениям геометрическая: <math>1 + 2 + 4 + \dots + n/2 < n</math>. Значит, суммарно <math>O(n)</math>, то есть <math>O(1)</math> амортизированно на <code>push</code>. <math>\blacksquare</math>

'''Оценка.''' <code>push</code>/<code>pop</code>/<code>top</code> — <math>O(1)</math> (в массиве амортизированно); память <math>O(n)</math>; <code>balanced</code> и <code>nextGreater</code> — <math>O(n)</math> времени.

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

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

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

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

# '''Стек вызовов и рекурсия.''' Любой вызов функции кладёт кадр на стек; хвостовая рекурсия и явный стек заменяют глубокую рекурсию.
# '''Вычисление выражений.''' Постфиксные (RPN) выражения вычисляются стеком; инфиксные переводятся в постфиксные (алгоритм сортировочной станции Дейкстры).
# '''Синтаксический анализ.''' Проверка скобок, разбор вложенных тегов/блоков, парсеры с рекурсивным спуском.
# '''Обход в глубину (DFS).''' Итеративный DFS хранит вершины в стеке; рекурсивный использует стек вызовов.
# '''Монотонный стек.''' Следующий больший/меньший элемент, гистограммы, «сколько дней до тепла» — за <math>O(n)</math>.
# '''Отмена действий (undo/redo) и «назад».''' Два стека для отмены и повтора; история в браузере.
# '''Oбработка отката и backtracking.''' Возврат по лабиринту, перебор с возвратом, рекурсивные алгоритмы с откатом.

[[Файл:stack-06-applications.svg|frame|none|700px|Рис. 6. Баланс скобок, вычисление постфиксных выражений, обход в глубину, отмена действий.]]

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

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

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

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

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

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

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

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

== Источники ==

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