Стек — структура данных¶
Стек — структура данных, организованная по принципу «последним вошёл — первым вышел» (LIFO, Last In First Out). Элементы стека добавляются и извлекаются только с одного конца — его называют вершиной (top). Другой конец, называемый дном, недоступен для прямого доступа. Стек относится к линейным структурам данных и применяется в программировании, вычислительной технике и математике.
¶История
Понятие стека ввёл в математику и информатику Эдсгер Дейкстра в 1960-х годах в контексте описания работы подпрограмм. Термин «stack» («стопка») отражает наглядную аналогию со стопкой тарелок: новую тарелку кладут сверху, а убирают тоже сверху. В ранних языках программирования, таких как ALGOL и Fortran, стек использовался для хранения адресов возврата при вызове подпрограмм. Впоследствии стек стал одним из фундаментальных понятий теории алгоритмов и структур данных.
¶Основные операции
Стек поддерживает ограниченный набор операций:
| Операция | Описание |
|---|---|
push(x) | добавление элемента на вершину стека |
pop() | извлечение элемента с вершины стека |
peek() / top() | просмотр элемента на вершине без удаления |
isEmpty() | проверка, пуст ли стек |
size() | получение количества элементов |
При выполнении pop() на пустом стеке возникает ошибка (или исключение) — это называется стековым переполнением (stack underflow). При попытке добавить элемент в стек, заполненный до предела, происходит переполнение (stack overflow).
¶Реализация
¶Массивная реализация
Простейший способ реализовать стек — использовать массив фиксированного размера. Индекс вершины хранится в отдельной переменной. Такая реализация обеспечивает константное время выполнения всех операций, но ограничена размером массива.
¶Реализация на связном списке
Динамическая реализация основана на односвязном списке, где вставка и удаление выполняются в голове списка. Преимущество — отсутствие ограничения на размер, недостаток — дополнительные затраты памяти на хранение указателей.
¶Стек в программировании
¶Стек вызовов (call stack)
В большинстве языков программирования стек используется для управления вызовами подпрограмм. При вызове функции её локальные переменные, параметры и адрес возврата помещаются на стек вызовов. При завершении функции эти данные извлекаются. Стек вызовов обычно размещается в оперативной памяти процесса и имеет ограниченный размер; его переполнение приводит к ошибке stack overflow, часто проявляющейся в виде аварийного завершения программы.
¶Стек в вычислительных машинах
В архитектуре ЭВМ стек может выступать в роли набора регистров для арифметических операций. Стековые процессоры (например, Burroughs B5000, созданный в 1960-е годы) используют стек как основное рабочее пространство для вычислений. В языках Forth и PostScript вычисления также основаны на стековой модели.
¶Применение
- Обратный польский калькулятор — вычисление выражений в обратной польской нотации с помощью стека.
- Синтаксический анализ — проверка парности скобок, обработка вложенных конструкций.
- Обход графов — алгоритм поиска в глубину (DFS) реализуется с использованием стека.
- Отмена действий (undo) — хранение истории операций в редакторах.
- Управление памятью — аллокация локальных переменных, рекурсивные вызовы.
- Сериализация данных — форматы вроде JSON и S-expression используют стековую логику разбора.
¶Стек и очередь
Стек часто противопоставляется очереди — другой линейной структуре данных, работающей по принципу FIFO (первым вошёл — первым вышел). Если стек подходит для задач с вложенной структурой (рекурсия, разбор выражений), то очередь используется там, где важен порядок поступления (обход графа в ширину, планирование задач).
¶Интересные факты
- Стековые переполнения являются распространённым источником уязвимостей в программном обеспечении: злоумышленник может подменить адрес возврата на стеке и перехватить управление программой. Для защиты от таких атак современные системы используют механизмы ASLR и стековые канарейки (stack canaries).
- В математике стек соответствует операции снятия элемента с вершины, а обратная операция — добавление. Стековые машины Тьюринга являются важной моделью в теории вычислимости.
¶Источники
- Кормен Т., Лейзерсон Ч., Ривест Р., Штейн К. — «Алгоритмы: построение и анализ»
- Кнут Д. — «Искусство программирования», том 1
- Дейкстра Э. — «Вычислительные машины и информационные сети»
- Вирт Н. — «Алгоритмы + структуры данных = программы»
- Резник Ю. — «Алгоритмы и структуры данных на C++»