Стек — структура данных, в которой элементы добавляются и удаляются только с
одного конца.
Этот конец называется верхушкой стека.
Главное правило стека:
LIFO = Last In, First Out
То есть:
последний добавленный элемент удаляется первым
Пример:
push(7)
push(3)
push(9)
push(1)
Состояние стека:
bottom top
7 3 9 1
Если выполнить:
pop()
то будет удалён 1, потому что он находится на верхушке.
Термины
stack -> стек
top -> верхний элемент
bottom -> нижний элемент
size -> количество элементов в стеке
push(x) -> положить x на верхушку
pop() -> снять верхний элемент
peek() -> посмотреть верхний элемент без удаления
isEmpty() -> проверить, пуст ли стек
Стек задаётся тремя вещами:
1. набор элементов
2. порядок добавления элементов
3. верхушка, через которую идут основные операции
Структура стека
Структура отвечает на вопрос:
Что внутри и как расположено?
У стека есть:
элементы
верхушка
нижняя часть
порядок добавления
размер
Стек можно представить как вертикальную стопку:
top
↓
[1]
[9]
[3]
[7]
↑
bottom
Новые элементы кладутся сверху. Удаляются тоже сверху.
Свойства
Короткая карта свойств стека как структуры:
верхушка -> основная точка доступа к стеку
LIFO -> последним вошёл, первым вышел
ограниченный доступ -> доступен только верхний элемент
размер -> количество элементов в стеке
порядок добавления -> порядок влияет на порядок удаления
пустота -> стек может не содержать элементов
Конечность здесь является общей предпосылкой:
конкретный стек содержит конечное число элементов
Но для стека важнее операциональная форма этой конечности:
size = n
пустой стек = size == 0
непустой стек = size > 0
верхушка существует только у непустого стека
Важно отделять свойства стека от характеристик конкретного стека:
свойство: у стека есть верхушка
характеристика: верхний элемент этого стека = 1
свойство: у стека есть размер
характеристика: размер этого стека = 4
Верхушка
Верхушка — это единственная позиция, через которую стек обычно предоставляет
доступ к элементам.
top(stack)
Для стека:
[7, 3, 9, 1]
верхний элемент:
top = 1
LIFO
Стек работает по правилу:
Last In, First Out
Если элементы добавлены в таком порядке:
7, 3, 9, 1
то удаляться они будут в обратном порядке:
1, 9, 3, 7
Ограниченный доступ
В отличие от массива, стек не даёт произвольный доступ по индексу как базовую
операцию.
arr[i] -> обычная операция массива
stack[i] -> не базовая операция стека
Стек скрывает внутренние позиции и даёт работать с верхушкой:
push
pop
peek
Размер
Размер стека — это количество элементов в нём.
size(stack) = n
Размер меняется при операциях:
push(x) -> size увеличивается на 1
pop() -> size уменьшается на 1
Пустота
Стек может быть пустым.
stack = []
size = 0
Для пустого стека нельзя корректно выполнить:
pop()
peek()
если реализация явно не задаёт специальное поведение для этих случаев.
Базовые операции
Создание
stack = []
Обычно:
O(1)
Push
Добавить элемент на верхушку стека:
push(stack, x)
Пример:
stack = [7, 3, 9]
push(1)
stack = [7, 3, 9, 1]
Обычно:
O(1)
Если стек реализован через динамический массив, отдельная операция может стоить
O(n) при расширении внутреннего хранилища, но амортизированно это:
amortized O(1)
Pop
Удалить и вернуть верхний элемент:
pop(stack)
Пример:
stack = [7, 3, 9, 1]
pop() -> 1
stack = [7, 3, 9]
Условие:
size(stack) > 0
Обычно:
O(1)
Peek / Top
Посмотреть верхний элемент без удаления:
peek(stack)
top(stack)
Пример:
stack = [7, 3, 9, 1]
peek() -> 1
stack = [7, 3, 9, 1]
Условие:
size(stack) > 0
Сложность:
O(1)
Is Empty
Проверить, пуст ли стек:
isEmpty(stack)
Пример:
[] -> true
[7, 3, 9] -> false
Сложность:
O(1)
Size
Получить количество элементов:
size(stack)
Обычно:
O(1)
если размер хранится отдельно.
Проход по стеку
Если нужно обработать все элементы через стековые операции, стек можно
постепенно разбирать:
while not isEmpty(stack):
x = pop(stack)
use x
Сложность:
O(n)
Важно: такой проход изменяет стек, потому что pop() удаляет элементы.
Таблица сложностей
| Операция | Сложность |
|---|---|
| создание | O(1) |
push(x) |
O(1) / amortized O(1) |
pop() |
O(1) |
peek() / top() |
O(1) |
isEmpty() |
O(1) |
size() |
O(1) |
| проход с удалением всех элементов | O(n) |
| поиск произвольного значения | O(n) |
Реализация
Стек — это абстрактная структура данных. Его можно реализовать разными способами.
Через динамический массив
Верхушка стека обычно совпадает с концом массива:
stack = [7, 3, 9, 1]
^
top
Тогда:
push(x) -> append(x)
pop() -> remove last element
peek() -> last element
Такой вариант даёт быстрые операции на верхушке.
Через связный список
Верхушка стека может быть головой списка:
top -> [1] -> [9] -> [3] -> [7]
Тогда:
push(x) -> добавить новый узел в голову
pop() -> удалить голову
peek() -> прочитать голову
Стек и массив
Массив даёт доступ по индексу:
arr[i]
Стек даёт доступ к верхушке:
top(stack)
Массив удобен, когда важны позиции и произвольный доступ.
Стек удобен, когда важен порядок вложенности, отката или ожидания:
последнее открытое закрывается первым
последнее действие отменяется первым
последняя нерешённая задача обрабатывается первой
Типичные применения
проверка скобок
отмена действий
обход графа в глубину
обработка рекурсии
монотонный стек
Min Stack
вычисление выражений
Формальная схема
Stack = {
elements: e1, e2, ..., en,
top: en,
size: n,
rule: LIFO
}
Операции стека изменяют или используют одну из трёх сущностей:
верхушка
размер
порядок удаления
Примеры:
push(x) -> меняет верхушку и увеличивает размер
pop() -> возвращает верхушку и уменьшает размер
peek() -> читает верхушку без изменения стека
isEmpty() -> проверяет размер
Минимальная формулировка:
стек = структура с доступом к последнему добавленному элементу
