Структура данных стек: принцип LIFO, операции и реализация на Python
Что такое стек в программировании: принцип LIFO, операции push и pop, реализация на Python через list, deque и связный список. Стек вызовов, скобки, undo и обход в глубину.
Коротко
| Вопрос | Ответ |
|---|---|
| Что это | Структура данных, где добавлять и забирать элементы можно только с одного конца |
| Принцип | LIFO, Last In — First Out: последним пришёл, первым ушёл |
| Операции | push (положить), pop (снять), peek (посмотреть верхний), проверка на пустоту |
| Сложность | Все операции за , память |
| Стек в Python | Обычный list: append вместо push, pop вместо pop, stack[-1] вместо peek |
| Где встречается | Стек вызовов функций, проверка скобок, undo в редакторах, обход графа в глубину |
| Когда вспоминать о нём | Когда последнее начатое дело нужно закончить первым: вложенность, откат, «вернуться» |
Что такое стек
Стек — это структура данных, в которой у элементов один вход и он же выход. Новый элемент кладётся сверху, и забрать можно тоже только верхний. До того, что лежит ниже, не добраться, пока не снимешь всё, что сверху.
Классическая картинка — стопка тарелок. Чистую тарелку ставят наверх, берут тоже сверху. Вытащить третью снизу, не разобрав стопку, нельзя.
push(1) push(2) push(3) pop() → 3 pop() → 2
┌───┐
│ 3 │
┌───┐ ├───┤ ┌───┐
│ 2 │ │ 2 │ │ 2 │
┌───┐ ├───┤ ├───┤ ├───┤ ┌───┐
│ 1 │ │ 1 │ │ 1 │ │ 1 │ │ 1 │
└───┘ └───┘ └───┘ └───┘ └───┘
Это правило называется LIFO — Last In, First Out: последним пришёл, первым ушёл. Положили 1, 2, 3 — достанем 3, 2, 1. Стек разворачивает порядок, и на этом свойстве держится половина его применений.
Верхний элемент называют вершиной стека (top). Это единственное место, с которым стек разрешает работать.
Стек — абстракция, а не конкретный способ хранения. Он описывает, что можно делать с данными, а не как они лежат в памяти. Внутри может быть массив, связный список или что-то ещё: если наружу торчат только push и pop с одного конца, это стек. Вместе с очередью, массивом и связным списком он относится к линейным структурам данных; как они соотносятся с деревьями, графами и хеш-таблицами, есть в обзоре структур данных.
Операции со стеком
Набор операций маленький, и в этом весь смысл.
| Операция | Что делает | Сложность | В Python (list) |
|---|---|---|---|
push(x) | Кладёт элемент на вершину | stack.append(x) | |
pop() | Снимает верхний элемент и возвращает его | stack.pop() | |
peek() | Возвращает верхний элемент, не снимая | stack[-1] | |
is_empty() | Проверяет, пуст ли стек | not stack | |
size() | Количество элементов | len(stack) |
Чего в стеке нет: доступа по индексу, поиска, вставки в середину. Если в задаче нужно что-то из этого, стек — не та структура.
Может показаться, что ограничения — недостаток: массив умеет всё то же и больше. Но ограничения здесь и есть польза. Когда в коде написано «стек», читателю сразу понятно, в каком порядке обрабатываются данные, и случайно залезть в середину не выйдет.
Стек в Python
Отдельного типа Stack в Python нет, и он не нужен: обычный список закрывает все операции.
stack = [] stack.append('a') # push stack.append('b') stack.append('c') print(stack[-1]) # c — peek, элемент остаётся в стеке print(stack.pop()) # c print(stack.pop()) # b print(len(stack)) # 1 print(not stack) # False — стек не пуст
Вершина стека — конец списка. Это важно, и вот почему.
Почему вершина — в конце списка
Список в Python — динамический массив: элементы лежат в памяти подряд. Добавить или убрать элемент в конце дёшево, остальные никуда не двигаются. А insert(0, x) и pop(0) сдвигают все элементы на одну позицию — это на каждую операцию.
Разница не теоретическая. Положим в стек 100 000 элементов и снимем их обратно двумя способами:
import timeit n = 100_000 def right(): st = [] for i in range(n): st.append(i) while st: st.pop() def left(): st = [] for i in range(n): st.insert(0, i) while st: st.pop(0) print(timeit.timeit(right, number=1)) # ~0.006 с print(timeit.timeit(left, number=1)) # ~2 с
Цифры с моего ноутбука, у вас будут другие, но порядок сохранится: вариант с началом списка медленнее в сотни раз, и чем больше n, тем хуже.
Откуда O(1), если массив иногда расширяется
Когда в списке кончается место, Python выделяет новый блок памяти побольше и копирует туда элементы. Такой append стоит . Но память берётся с запасом, поэтому случается это редко:
import sys st = [] last = None for i in range(40): size = sys.getsizeof(st) if size != last: print(len(st), size) last = size st.append(i)
В CPython 3.9 размер меняется на длинах 0, 1, 5, 9, 17, 25, 33 — а не на каждом шаге (в других версиях числа могут отличаться). Если размазать стоимость редких копирований по всем вставкам, выйдет константа на операцию. Это называется амортизированной сложностью : отдельный append может оказаться медленным, но серия из вставок всегда укладывается в .
deque и LifoQueue
В стандартной библиотеке есть ещё два варианта.
from collections import deque from queue import LifoQueue d = deque() d.append(1) d.append(2) print(d.pop()) # 2 print(d[-1]) # 1 q = LifoQueue() q.put(1) q.put(2) print(q.get()) # 2 print(q.get()) # 1
collections.deque— двусторонняя очередь.appendиpopработают за честное без копирований всего массива. Для стека выигрыш передlistобычно незаметен;dequeпо-настоящему нужен, когда элементы забирают с начала, то есть для очереди.queue.LifoQueue— стек с блокировками для обмена данными между потоками. В однопоточном коде он только медленнее, аget()на пустом стеке не бросит исключение, а будет ждать вечно. На алгоритмическом собеседовании он не нужен.
Практический вывод: в задачах и в обычном коде берите list.
Своя реализация стека
На собеседовании и в учебных курсах часто просят написать стек «руками». Вариантов два.
На списке
Обёртка над list, которая прячет всё лишнее и оставляет только операции стека:
class Stack: def __init__(self): self._items = [] def push(self, item): self._items.append(item) def pop(self): if not self._items: raise IndexError('pop из пустого стека') return self._items.pop() def peek(self): if not self._items: raise IndexError('peek из пустого стека') return self._items[-1] def is_empty(self): return not self._items def __len__(self): return len(self._items) s = Stack() for x in (10, 20, 30): s.push(x) print(s.peek()) # 30 print(s.pop()) # 30 print(s.pop()) # 20 print(len(s)) # 1 print(s.is_empty()) # False
Что делать при pop из пустого стека — решение автора. Здесь бросается исключение, как делает сам list. Возвращать None хуже: пустой стек становится неотличим от стека, в который положили None.
На связном списке
Второй классический вариант — односвязный список, где вершина стека — голова списка. push создаёт новый узел и ставит его перед головой, pop передвигает голову на следующий узел.
class Node: def __init__(self, value, next=None): self.value = value self.next = next class LinkedStack: def __init__(self): self._head = None self._size = 0 def push(self, value): self._head = Node(value, self._head) self._size += 1 def pop(self): if self._head is None: raise IndexError('pop из пустого стека') node = self._head self._head = node.next self._size -= 1 return node.value def peek(self): if self._head is None: raise IndexError('peek из пустого стека') return self._head.value def __len__(self): return self._size s = LinkedStack() for x in (1, 2, 3): s.push(x) print(s.pop()) # 3 print(s.peek()) # 2 print(len(s)) # 2
Сравнение двух подходов:
Массив (list) | Связный список | |
|---|---|---|
push / pop | амортизированно | всегда |
| Память | Компактно, но с запасом на рост | Отдельный объект и ссылка на каждый элемент |
| Скорость на практике | Быстрее: данные лежат рядом | Медленнее: узлы разбросаны по памяти |
В Python вариант на связном списке почти всегда проигрывает и нужен в основном для того, чтобы показать понимание. Счётчик _size хранится отдельно не случайно: без него len пришлось бы считать обходом за .
Где применяется стек
Стек вызовов
Главный стек в жизни программиста — тот, который он не создавал. Когда функция вызывает другую функцию, интерпретатор должен запомнить, куда вернуться и какие значения были у локальных переменных. Эта запись называется кадром (frame), и кадры складываются в стек вызовов: вызвали функцию — push, функция вернула результат — pop.
Порядок здесь именно LIFO: функция, вызванная последней, завершится первой. Стек вызовов видно в любом трейсбэке:
def c(): raise ValueError('упс') def b(): c() def a(): b() a()
Traceback (most recent call last):
File "example.py", line 13, in <module>
a()
File "example.py", line 10, in a
b()
File "example.py", line 6, in b
c()
File "example.py", line 2, in c
raise ValueError('упс')
ValueError: упс
Трейсбэк — это содержимое стека в момент ошибки, от дна к вершине: a вызвала b, b вызвала c.
На стеке вызовов работает и рекурсия: каждый рекурсивный вызов — новый кадр. Стек не бесконечен, поэтому слишком глубокая рекурсия заканчивается ошибкой. В CPython лимит по умолчанию — 1000 кадров:
import sys def factorial(n): if n <= 1: return 1 return n * factorial(n - 1) print(factorial(5)) # 120 print(sys.getrecursionlimit()) # 1000 factorial(100_000) # RecursionError: maximum recursion depth exceeded
Это и есть переполнение стека, тот самый stack overflow. Лечится оно заменой неявного стека на явный — собственный список, который живёт в куче и ограничен только памятью:
def factorial_iter(n): stack = [] while n > 1: stack.append(n) n -= 1 result = 1 while stack: result *= stack.pop() return result print(factorial_iter(5)) # 120 print(len(str(factorial_iter(100_000)))) # 456574 цифры, без RecursionError
Для факториала стек, конечно, избыточен, хватило бы цикла. Но приём общий: любую рекурсию можно переписать на цикл с явным стеком. Подробнее о том, как устроены рекурсивные вызовы, — в статье про рекурсию.
Проверка скобок
Задача, с которой стек обычно и начинают: дана строка, нужно понять, правильно ли в ней расставлены скобки. {[()]} — правильно, ([)] — нет.
Идея: закрывающая скобка всегда должна соответствовать последней незакрытой открывающей. «Последняя из незакрытых» — это ровно вершина стека.
def is_valid(s): pairs = {')': '(', ']': '[', '}': '{'} stack = [] for ch in s: if ch in '([{': stack.append(ch) elif ch in pairs: if not stack or stack.pop() != pairs[ch]: return False return not stack print(is_valid('{[()]}')) # True print(is_valid('([)]')) # False print(is_valid('((')) # False — остались незакрытые print(is_valid(')')) # False — закрывать нечего print(is_valid('print(a[0])')) # True — прочие символы пропускаем
Как это работает на строке ([)]:
( открывающая → в стек стек: (
[ открывающая → в стек стек: ( [
) ждёт '(', а на вершине '[' → False
Две проверки, которые забывают чаще всего: not stack перед pop (строка )) и return not stack в конце (строка ((). Тем же способом редактор кода подсвечивает парные скобки, а парсер проверяет вложенность тегов в HTML. Полный разбор с вариациями — в статье про правильную скобочную последовательность.
Отмена действий: undo и redo
Ctrl+Z отменяет последнее действие, потом предпоследнее и так далее — чистый LIFO. Для redo нужен второй стек: отменённое состояние перекладывается туда.
class Editor: def __init__(self): self.text = '' self._undo = [] self._redo = [] def type(self, chunk): self._undo.append(self.text) self._redo.clear() self.text += chunk def undo(self): if self._undo: self._redo.append(self.text) self.text = self._undo.pop() def redo(self): if self._redo: self._undo.append(self.text) self.text = self._redo.pop() e = Editor() e.type('Привет') e.type(', мир') e.type('!') e.undo() print(e.text) # Привет, мир e.undo() print(e.text) # Привет e.redo() print(e.text) # Привет, мир e.type('?') e.redo() # ничего не происходит print(e.text) # Привет, мир?
Обратите внимание на self._redo.clear() в методе type: после нового действия старая ветка «вперёд» теряет смысл. Так ведут себя почти все редакторы. По той же схеме из двух стеков устроены кнопки «Назад» и «Вперёд» в браузере.
Здесь стек хранит копии текста целиком — для примера это нормально, а настоящие редакторы хранят сами операции («вставили 5 символов в позицию 12») и умеют применять их в обратную сторону.
Обход в глубину
Обход в глубину (DFS) идёт по графу так: от вершины уходим как можно дальше, упираемся в тупик, возвращаемся к последней развилке и пробуем другой путь. «Последняя развилка» — снова вершина стека.
graph = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': [], } def dfs(graph, start): visited = set() order = [] stack = [start] while stack: node = stack.pop() if node in visited: continue visited.add(node) order.append(node) for neighbor in reversed(graph[node]): if neighbor not in visited: stack.append(neighbor) return order print(dfs(graph, 'A')) # ['A', 'B', 'D', 'E', 'F', 'C']
reversed нужен только для порядка: стек разворачивает то, что в него кладут, и без него соседи обходились бы справа налево. Проверка if node in visited после pop обязательна: вершина может попасть в стек дважды (здесь F — и через C, и через E).
Рекурсивный DFS делает то же самое, просто стеком служит стек вызовов. А если в этом коде заменить стек на очередь, получится обход в ширину — подробности в статье про DFS и BFS.
Вычисление выражений
Компиляторы и калькуляторы считают выражения через стек. Удобнее всего это видно на обратной польской записи, где оператор стоит после операндов: 2 1 + 3 * означает (2 + 1) * 3.
def eval_rpn(tokens): ops = { '+': lambda a, b: a + b, '-': lambda a, b: a - b, '*': lambda a, b: a * b, '/': lambda a, b: int(a / b), } stack = [] for token in tokens: if token in ops: b = stack.pop() a = stack.pop() stack.append(ops[token](a, b)) else: stack.append(int(token)) return stack.pop() print(eval_rpn(['2', '1', '+', '3', '*'])) # 9 print(eval_rpn(['7', '2', '-'])) # 5
Число — в стек, оператор — снять два числа, посчитать, положить результат. Порядок снятия важен: первым снимается правый операнд, иначе 7 2 - даст −5. Разбор задачи — в статье про обратную польскую запись.
Типичные ошибки
popилиpeekна пустом стеке.[].pop()бросаетIndexError: pop from empty list,[][-1]— тожеIndexError. Перед обращением к вершине проверяйтеif stack.- Вершина в начале списка.
insert(0, x)иpop(0)формально дают стек, но каждая операция стоит . - Забыли проверить стек в конце. В задачах на скобки непустой стек после прохода означает, что что-то не закрыто.
- Перепутали порядок операндов. При двух
popподряд первым выходит то, что положили последним. Для вычитания и деления это критично. - Глубокая рекурсия вместо явного стека. На списке из 100 000 элементов или вырожденном дереве рекурсивное решение на Python упадёт с
RecursionError. - Стек там, где нужна очередь. Если элементы должны обрабатываться в порядке поступления, нужен FIFO, а не LIFO.
Стек на собеседованиях
Написать стек с нуля просят редко и в основном джунов. Гораздо чаще стек — инструмент внутри задачи, и главное — вовремя его узнать. Сигналы:
- в условии есть вложенность: скобки, теги, вложенные вызовы, пути вида
a/b/../c; - нужно «вернуться к предыдущему» или отменить последнее действие;
- для каждого элемента ищут ближайший больший или меньший слева или справа;
- рекурсивное решение надо сделать итеративным.
Что стоит разобрать после базовых операций:
- Стек с минимумом за O(1) — как добавить к стеку операцию, которой в нём нет, с помощью второго стека.
- Монотонный стек — техника для задач про ближайший больший элемент, температуры и гистограммы.
- Очередь на двух стеках — как из двух LIFO собрать FIFO и почему это всё ещё амортизированно.
Отвечая на вопрос «что такое стек», назовите принцип LIFO, операции и их сложность, скажите, на чём стек реализуют, и приведите пару применений — стек вызовов и скобки подойдут. Этого достаточно, чтобы перейти к задаче.
Стек и очередь: в чём разница
Очередь — зеркальная структура: элементы добавляют в один конец, а забирают из другого. Принцип — FIFO, первым пришёл, первым ушёл.
| Стек | Очередь | |
|---|---|---|
| Принцип | LIFO | FIFO |
| Кто выходит | Тот, кто пришёл последним | Тот, кто пришёл первым |
| В Python | list | collections.deque |
| Обход графа | В глубину (DFS) | В ширину (BFS) |
| Типичная задача | Скобки, undo, вложенность | Задачи по порядку, кратчайший путь |
Короткое сравнение обеих структур с реализациями на JavaScript и Python — в статье «Стек и очередь», а про очередь отдельно — в материале про структуру данных очередь.
Частые вопросы
Стек и стек вызовов — это одно и то же?
Стек вызовов — конкретный стек, который ведёт среда выполнения, чтобы помнить цепочку вызовов функций. Стек как структура данных — общая идея, и стек вызовов — один из её примеров.
Чем стек отличается от массива?
Массив даёт доступ к любому элементу по индексу. Стек — только к последнему добавленному. Стек часто хранят в массиве, но наружу отдают лишь push и pop.
Что такое «стек и куча»?
Это уже про память программы. В области стека лежат кадры вызовов функций, она освобождается автоматически при выходе из функции. Куча — область для объектов, которые живут дольше одного вызова. Называется область стеком потому, что работает по тому же принципу LIFO.
А «стек технологий»?
К структуре данных отношения не имеет. Так называют набор технологий проекта: язык, фреймворк, база данных.
Итог
Стек — структура с одним правилом: работать можно только с последним добавленным элементом. Из этого правила получаются все операции за и естественное решение для всего, что связано с вложенностью и возвратом назад. В Python для стека хватает списка: append, pop и stack[-1].
Лучший способ закрепить — решить задачи: начните со скобок, затем обратная польская запись, а после — температуры, где понадобится монотонный стек.