Открыть сервисСервис

Стек — структура данных 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)
  • Таненбаум Э. — «Архитектура компьютера»
Заметили ошибку или не согласны с информацией в статье? Напишите нам support@bfometr.ru