Структура данных стек: принцип LIFO, операции и реализация на Python

Что такое стек в программировании: принцип LIFO, операции push и pop, реализация на Python через list, deque и связный список. Стек вызовов, скобки, undo и обход в глубину.

14 мин чтенияструктуры данных · стек · python

Коротко

ВопросОтвет
Что этоСтруктура данных, где добавлять и забирать элементы можно только с одного конца
ПринципLIFO, Last In — First Out: последним пришёл, первым ушёл
Операцииpush (положить), pop (снять), peek (посмотреть верхний), проверка на пустоту
СложностьВсе операции за O(1)O(1), память O(n)O(n)
Стек в 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)Кладёт элемент на вершинуO(1)O(1)stack.append(x)
pop()Снимает верхний элемент и возвращает егоO(1)O(1)stack.pop()
peek()Возвращает верхний элемент, не снимаяO(1)O(1)stack[-1]
is_empty()Проверяет, пуст ли стекO(1)O(1)not stack
size()Количество элементовO(1)O(1)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) сдвигают все элементы на одну позицию — это O(n)O(n) на каждую операцию.

Разница не теоретическая. Положим в стек 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 стоит O(n)O(n). Но память берётся с запасом, поэтому случается это редко:

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 — а не на каждом шаге (в других версиях числа могут отличаться). Если размазать стоимость редких копирований по всем вставкам, выйдет константа на операцию. Это называется амортизированной сложностью O(1)O(1): отдельный append может оказаться медленным, но серия из nn вставок всегда укладывается в O(n)O(n).

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 работают за честное O(1)O(1) без копирований всего массива. Для стека выигрыш перед 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 / popO(1)O(1) амортизированноO(1)O(1) всегда
ПамятьКомпактно, но с запасом на ростОтдельный объект и ссылка на каждый элемент
Скорость на практикеБыстрее: данные лежат рядомМедленнее: узлы разбросаны по памяти

В Python вариант на связном списке почти всегда проигрывает и нужен в основном для того, чтобы показать понимание. Счётчик _size хранится отдельно не случайно: без него len пришлось бы считать обходом за O(n)O(n).

Где применяется стек

Стек вызовов

Главный стек в жизни программиста — тот, который он не создавал. Когда функция вызывает другую функцию, интерпретатор должен запомнить, куда вернуться и какие значения были у локальных переменных. Эта запись называется кадром (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) формально дают стек, но каждая операция стоит O(n)O(n).
  • Забыли проверить стек в конце. В задачах на скобки непустой стек после прохода означает, что что-то не закрыто.
  • Перепутали порядок операндов. При двух pop подряд первым выходит то, что положили последним. Для вычитания и деления это критично.
  • Глубокая рекурсия вместо явного стека. На списке из 100 000 элементов или вырожденном дереве рекурсивное решение на Python упадёт с RecursionError.
  • Стек там, где нужна очередь. Если элементы должны обрабатываться в порядке поступления, нужен FIFO, а не LIFO.

Стек на собеседованиях

Написать стек с нуля просят редко и в основном джунов. Гораздо чаще стек — инструмент внутри задачи, и главное — вовремя его узнать. Сигналы:

  • в условии есть вложенность: скобки, теги, вложенные вызовы, пути вида a/b/../c;
  • нужно «вернуться к предыдущему» или отменить последнее действие;
  • для каждого элемента ищут ближайший больший или меньший слева или справа;
  • рекурсивное решение надо сделать итеративным.

Что стоит разобрать после базовых операций:

Отвечая на вопрос «что такое стек», назовите принцип LIFO, операции и их сложность, скажите, на чём стек реализуют, и приведите пару применений — стек вызовов и скобки подойдут. Этого достаточно, чтобы перейти к задаче.

Стек и очередь: в чём разница

Очередь — зеркальная структура: элементы добавляют в один конец, а забирают из другого. Принцип — FIFO, первым пришёл, первым ушёл.

СтекОчередь
ПринципLIFOFIFO
Кто выходитТот, кто пришёл последнимТот, кто пришёл первым
В Pythonlistcollections.deque
Обход графаВ глубину (DFS)В ширину (BFS)
Типичная задачаСкобки, undo, вложенностьЗадачи по порядку, кратчайший путь

Короткое сравнение обеих структур с реализациями на JavaScript и Python — в статье «Стек и очередь», а про очередь отдельно — в материале про структуру данных очередь.

Частые вопросы

Стек и стек вызовов — это одно и то же?

Стек вызовов — конкретный стек, который ведёт среда выполнения, чтобы помнить цепочку вызовов функций. Стек как структура данных — общая идея, и стек вызовов — один из её примеров.

Чем стек отличается от массива?

Массив даёт доступ к любому элементу по индексу. Стек — только к последнему добавленному. Стек часто хранят в массиве, но наружу отдают лишь push и pop.

Что такое «стек и куча»?

Это уже про память программы. В области стека лежат кадры вызовов функций, она освобождается автоматически при выходе из функции. Куча — область для объектов, которые живут дольше одного вызова. Называется область стеком потому, что работает по тому же принципу LIFO.

А «стек технологий»?

К структуре данных отношения не имеет. Так называют набор технологий проекта: язык, фреймворк, база данных.

Итог

Стек — структура с одним правилом: работать можно только с последним добавленным элементом. Из этого правила получаются все операции за O(1)O(1) и естественное решение для всего, что связано с вложенностью и возвратом назад. В Python для стека хватает списка: append, pop и stack[-1].

Лучший способ закрепить — решить задачи: начните со скобок, затем обратная польская запись, а после — температуры, где понадобится монотонный стек.

Потренироваться в спокойной обстановке

Все задачи

Читать дальше

Все статьи
Алгоритмы и структуры данныхОчередь (queue): структура данных FIFO, операции и реализация на PythonОчередь как структура данных простыми словами: принцип FIFO, операции за O(1), почему list.pop(0) медленный, collections.deque, кольцевая очередь и применение в BFS и планировщиках.Алгоритмы и структуры данныхГраф как структура данных: матрица смежности, список смежности и список рёбер на PythonЧто такое граф в программировании: вершины и рёбра, ориентированный, неориентированный и взвешенный граф. Три представления графа в памяти с кодом на Python и сравнением по памяти и скорости.Алгоритмы и структуры данныхБинарное дерево: что это, виды, листья, полное и сбалансированное деревоБинарное дерево простыми словами: корень, узлы и листья, высота, виды деревьев (строгое, полное, совершенное, сбалансированное, вырожденное) и построение на Python с рабочим кодом.