Стек — структура данных LIFO¶
Стек — линейная структура данных, основанная на принципе «последний вошёл — первый вышел» (LIFO, Last In First Out). Элементы добавляются и извлекаются только с одного конца, называемого вершиной стека. Операции добавления элемента называются push, извлечения — pop. Стек широко применяется в компьютерных программах, алгоритмах и операционных системах.
¶История
Термин «стек» в информатике закрепился благодаря Эдсгеру Дейкстре, который в 1960-х годах использовал его в работах по структурированному программированию. Идея стека как модели исполнения программ возникла в контексте разработки компиляторов: при вызове подпрограмм необходимо сохранять адрес возврата и локальные переменные — для этого естественно подходит стековый механизм.
Ранние реализации стека появились в ассемблерах и системах программирования 1950-х годов. В 1947 году Алан Тьюринг описал в докладе «О вычислимых числах» механизм, фактически представляющий собой стек вызовов. Позднее стек стал основой архитектуры большинства процессоров, включая x86, ARM и RISC-V.
¶Основные операции
Стек поддерживает ограниченный набор операций:
- push — добавление элемента на вершину;
- pop — извлечение элемента с вершины;
- peek (или top) — просмотр верхнего элемента без удаления;
- isEmpty — проверка на пустоту;
- size — получение количества элементов.
При переполнении стека (stack overflow) попытка push приводит к ошибке, при попытке pop из пустого стека возникает underflow.
¶Реализации
¶Массивная реализация
Наиболее простой способ — выделить массив фиксированного размера и хранить индекс вершины. Операции выполняются за O(1), но размер стека ограничен.
¶Списочная реализация
Динамический стек строится на связном списке: каждый новый элемент становится новой вершиной. Размер ограничен только памятью. В языках программирования с автоматическим управлением памятью (Java, C#, Python) стек обычно реализуется именно так.
¶Стек на кольцевом буфере
Кольцевой буфер позволяет реализовать стек с переиспользованием памяти, что полезно во встроенных системах с ограниченными ресурсами.
¶Стек вызовов
Одно из ключевых применений стека — хранение кадров вызовов (call stack). При вызове подпрограммы в стек помещаются адрес возврата, локальные переменные и параметры. При возврате из подпрограммы эти данные извлекаются. Глубина стека вызовов ограничена размером стековой памяти процесса; превышение этой глубины приводит к ошибке stack overflow, которая является частой причиной падения программ при бесконечной рекурсии.
В большинстве систем стек растёт вниз (от высоких адресов к низким), хотя это зависит от архитектуры. На x86 стековый указатель ESP/RSP уменьшается при вызове функции.
¶Стек в алгоритмах
Стек применяется при решении ряда классических задач:
- Обратный польский калькулятор — вычисление выражений в постфиксной нотации (изобретён польским математиком Яном Лукасевичем в 1920-х годах);
- Обход графов — алгоритм поиска в глубину (DFS) использует стек для хранения узлов;
- Синтаксический разбор — компиляторы применяют стек для проверки скобок и построения синтаксических деревьев;
- Откат (backtracking) — при переборе решений (например, в алгоритме нахождения лабиринта) стек хранит путь.
¶Стек в языках программирования
В большинстве языков локальные переменные функции размещаются в стеке автоматически. В C и C++ переменные с ключевым словом auto (по умолчанию) живут в стеке и уничтожаются при выходе из области видимости. В языках с управляемой памятью (Java, C#) объекты размещаются в куче, но ссылки на них и локальные переменные — в стеке.
Стек также используется для реализации механизма исключений: при возникновении ошибки стек вызовов «раскручивается» (stack unwinding), освобождая ресурсы.
¶Стек в аппаратном обеспечении
Современные процессоры имеют аппаратную поддержку стека: регистр стекового указателя, команды push и pop, механизм прерываний, при котором текущий контекст сохраняется в стеке. В защищённом режиме x86 стековая память защищена механизмом сегментации и страницами.
¶См. также
- Очередь (структура данных)
- Рекурсия
- Алгоритм поиска в глубину
¶Источники
- Кормен Т., Лейзерсон Ч., Ривест Р., Штейн К. — «Введение в алгоритмы»
- Кнут Д. — «Искусство программирования», том 1
- Дейкстр Э. — «Go To Statement Considered Harmful» (1968)
- Таненбаум Э. — «Архитектура компьютера»
