Штабель — упорядоченная структура данных¶
Штабель (от нем. Stapel — стопка, штабель) — линейная структура данных, организованная по принципу «последним пришёл — первым вышел» (LIFO, Last In First Out). К элементам штабеля возможен доступ только к верхнему (последнему добавленному) элементу; для доступа к остальным элементам требуется последовательное удаление верхних. Штабель является одним из фундаментальных абстрактных типов данных наряду с очередью и используется во всех областях программирования — от компиляторов до системного программного обеспечения.
¶Основные операции
Штабель поддерживает два базовых действия:
- push (положить) — добавление элемента на вершину штабеля;
- pop (снять) — извлечение элемента с вершины штабеля.
Дополнительно реализуются вспомогательные операции:
- peek / top — просмотр элемента на вершине без его удаления;
- isEmpty — проверка на пустоту;
- size — получение количества элементов.
При попытке извлечь элемент из пустого штабеля возникает состояние переполнения (underflow), при попытке добавить элемент в заполненный до предела штабель — переполнение (overflow). В языках программирования с динамической памятью ограничение на размер обычно отсутствует.
¶Реализации
¶Стек на массиве
Простейшая реализация использует массив фиксированного размера и индекс вершины. Push выполняется за O(1): элемент записывается по индексу top, после чего индекс увеличивается. Pop также выполняется за O(1). Недостаток — необходимость заранее задавать максимальный размер.
¶Стек на связном списке
Второй классический способ — односвязный список, где операции push и pop выполняются в голове списка. Такая реализация не ограничена размером и не требует сдвига элементов, но требует дополнительной памяти на хранение ссылок.
¶Динамическое расширение
В современных языках (Java, C#, Python) штабель реализуется через динамический массив, который расширяется при достижении предела. Амортизированная сложность операций остаётся O(1).
¶Стек вызовов
Одно из ключевых применений штабеля — стек вызовов (call stack) в системах программирования. При вызове функции её адрес возврата и локальные переменные помещаются на стек вызовов; при завершении функции эти данные извлекаются. Стек вызовов позволяет реализовать рекурсию: каждый рекурсивный вызов создаёт новый кадр (frame) на стеке. Глубокая рекурсия может привести к переполнению стека вызовов (stack overflow) — типичная причина падения программы.
¶Применение
Штабель применяется в широком спектре задач:
- Обратная польская запись — вычисление арифметических выражений с помощью двух стеков (операндов и операторов).
- Синтаксический анализ — проверка парности скобок, построение синтаксических деревьев (алгоритм сортировочной станции Дейкстры).
- Обход графов — алгоритм поиска в глубину (DFS) использует стек для хранения вершин.
- Отмена действий — в текстовых редакторах история изменений хранится в стеке.
- Разворот строк — классическая задача, решаемая стеком.
- Управление памятью — автоматическое выделение и освобождение локальных переменных.
¶Связь с математикой
Штабель соответствует структуре стека в теории формальных языков и автоматов. Машина со стеком (стековый автомат) — модель вычислений, в которой память организована как стек. Стековые автоматы по выразительности эквивалентны машинам Тьюринга. В комбинаторике штабель связан с понятием стековых перестановок — перестановок, которые можно получить последовательным добавлением и извлечением элементов из стека.
¶См. также
- Очередь (структура данных)
- Дек (двойная очередь)
- Рекурсия
- Алгоритм Дейкстры (обратная польская запись)
¶Источники
- Кнут Д. «Искусство программирования», том 1: основные алгоритмы
- Кормен Т., Лейзерсон Ч., Ривест Р., Штейн К. «Алгоритмы: построение и анализ»
- Уорс Р. «Алгоритмы и структуры данных на C»