Стек в информатике¶

Стек — структура данных, организованная по принципу LIFO (Last In, First Out — «последний вошёл, первый вышел»): элемент, добавленный последним, извлекается первым. Стек относится к линейным структурам данных и широко применяется в программировании, операционных системах и аппаратной архитектуре процессоров. Основные операции над стеком — это push (добавление элемента на вершину) и pop (извлечение элемента с вершины); также поддерживаются операции peek (просмотр вершины без удаления) и проверка на пустоту.

¶Принцип работы

Стек можно представить как вертикальную стопку элементов, где доступ разрешён только к верхнему. Добавление нового элемента помещает его поверх предыдущего, а извлечение снимает именно его. Если стек переполнен, операция push завершается ошибкой; если стек пуст, pop также невозможен. В языках программирования с динамической памятью (Python, JavaScript) стек часто реализуется поверх списков или массивов, а ограничение на размер снимается динамическим расширением.

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

¶Реализации

¶На массиве

Массивная реализация хранит элементы в непрерывной области памяти и поддерживает индекс вершины. Операции push и pop выполняются за O(1). Недостаток — фиксированный максимальный размер (хотя можно использовать динамический массив, увеличивающийся при переполнении).

¶На связном списке

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

¶Двухсторонний стек (дек)

Иногда реализуют двунаправленный стек, где элементы можно добавлять и извлекать с обоих концов — это по сути дек (deque).

¶Стек в языках программирования

В большинстве языков стек используется неявно: локальные переменные функции, адреса возврата и параметры вызовов размещаются в стеке вызовов (call stack). Рекурсивные алгоритмы активно нагружают стек: каждое рекурсивное вложение создаёт новый кадр (frame). Глубокая рекурсия может привести к переполнению стека (stack overflow) — типичная причина падения программы.

В языках со статической типизацией (C, C++, Java, C#) стек часто является встроенной структурой данных: в C++ это std::stack, в Java — класс Stack из пакета java.util (рекомендуется использовать Deque как более универсальную альтернативу), в C# — Stack<T>. В Python стек имитируется через список (append/pop) или через collections.deque.

¶Применение

Стек применяется в самых разных областях:

• Обратная польская запись (ОПН) — вычисление выражений через стек операндов; алгоритм сортировки в стеке (stack sort).
• Обход графов и деревьев — алгоритм поиска в глубину (DFS) использует стек для хранения узлов.
• Синтаксический разбор — парсеры используют стек для отслеживания вложенности скобок и построения дерева разбора.
• Откат (undo) — редакторы и приложения хранят историю действий в стеке.
• Управление памятью — локальные переменные, параметры функций и адреса возврата размещаются в стеке вызовов.
• Аппаратная реализация — процессоры содержат аппаратный стек для вызовов подпрограмм (например, PUSH/POP в x86, STMFD/LDMFD в ARM).

¶Стек и очередь

Стек часто противопоставляют очереди (FIFO — First In, First Out), где обслуживается элемент, добавленный первым. Обе структуры являются частными случаями более общих абстракций — деков и приоритетных очередей. Выбор между стеком и очередью определяется логикой алгоритма: стек удобен для задач с вложенной структурой (рекурсия, разбор выражений), очередь — для обхода в ширину и моделирования процессов.

¶Стек в теории вычислимости

В теории автоматов и вычислимости стек играет центральную роль: стековый автомат — модель вычислительной машины, использующая стек как основное рабочее хранилище. Контекстно-свободные грамматики и языки описываются с помощью стековых автоматов, что делает стек фундаментальным понятием теории формальных языков.

Источники:

• Кнут Д. «Искусство программирования», том 1: основные алгоритмы
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ»
• Уорс Р., Фергюсон М. «Язык C»
• Энциклопедия современных вычислительных технологий