Что такое стек

Стек — это абстрактный тип данных (ADT — abstract data type) с тремя операциями:

• push(x) — положить элемент сверху.
• pop() — снять верхний элемент и вернуть.
• peek() (он же top()) — посмотреть верхний элемент без снятия.

Принцип: LIFO — Last In, First Out. Последний положенный — первый снятый. Метафора — стопка тарелок: вы кладёте сверху и берёте сверху.

Стек — это поведение, а не структура. Можно реализовать на массиве, на linked list, на deque — любая структура, поддерживающая O(1) push и O(1) pop с одного и того же конца.

Реализация на Python list

В Python стек обычно делают через обычный list: append это push, pop() это pop. Обе операции O(1) amortized на конце списка (помните, почему — модуль 5).

class Stack:
    def __init__(self):
        self._data = []

    def push(self, x):
        self._data.append(x)

    def pop(self):
        if not self._data:
            raise IndexError("pop from empty stack")
        return self._data.pop()

    def peek(self):
        if not self._data:
            raise IndexError("peek from empty stack")
        return self._data[-1]

    def __len__(self):
        return len(self._data)

    def __bool__(self):
        return bool(self._data)


s = Stack()
s.push(10)
s.push(20)
s.push(30)
print(s.peek())     # 30
print(s.pop())      # 30
print(s.pop())      # 20
print(len(s))       # 1

В большинстве случаев в Python вообще не пишут class Stack — просто используют list напрямую:

stack = []
stack.append(10)
stack.append(20)
top = stack[-1]      # peek
val = stack.pop()    # pop

Это идиоматично и быстро. Класс нужен только если хочется явно ограничить интерфейс (запретить случайный доступ по индексу) или добавить инварианты.

Почему list работает: append и pop с конца — O(1)

Помните устройство list (модуль 4): ob_item — буфер указателей. append добавляет в конец (ob_item[ob_size] = x; ob_size += 1) — O(1) amortized. pop() убирает с конца (ob_size -= 1) — O(1) гарантировано (никаких сдвигов).

То есть конец list — это идеальная вершина стека: обе ключевые операции дешёвые.

Что не подходит — это pop(0) (низ list) для стека: O(n) на сдвиг. Но мы это и не делаем — стек только сверху.

Сравнение со deque

from collections import deque

stack = deque()
stack.append(10)
stack.append(20)
val = stack.pop()      # O(1)

deque тоже даёт O(1) на конец. Но для чисто стека list эффективнее: меньше overhead за счёт более простой структуры. deque лучше, когда нужна двусторонняя очередь — а для одностороннего стека list проще и быстрее.

Применение 1: undo

Текстовый редактор хранит стек операций. Каждая операция — что-то, что можно «откатить»:

undo_stack = []

def edit(text, op):
    # op это (type, position, payload)
    undo_stack.append(op)
    # ... примени op к тексту

def undo():
    if not undo_stack:
        return
    op = undo_stack.pop()
    # ... выполни обратное действие

LIFO здесь идеально: самая свежая операция первая для отмены. Глубина — длина стека. Если нужна история «вперёд» (redo) — добавляется второй стек.

Применение 2: вызовы функций (call stack)

Каждый ваш вызов функции — это фрейм на call stack. CPU держит регистр SP (stack pointer), указывающий на текущий фрейм. Когда функция вызывается — push нового фрейма; когда return — pop. Это аппаратный стек, поддерживаемый процессором.

Рекурсия — это про call stack. Если функция вызывает себя глубже, чем хватит стека (~1 MB по default в Linux), получаем stack overflow. В Python лимит ниже: ~1000 рекурсивных вызовов (sys.getrecursionlimit()), можно увеличить через sys.setrecursionlimit().

Применение 3: parser выражений

При парсинге math-выражения (1 + 2) * (3 - 4) мы используем два стека: один для операндов, один для операторов. Это classic Shunting-yard algorithm (Dijkstra, 1961).

Похоже работает парсер JSON, SQL, любой структурированный язык. Когда вы видите { — push на стек скобок; видите } — pop и проверяем match. Если стек не пуст в конце — несбалансированные скобки.

def is_balanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack


print(is_balanced("(()){}"))            # True
print(is_balanced("(({)})"))            # False — closing ) не парится с (
print(is_balanced("([{}])"))            # True

O(n) по длине строки, O(глубина_вложенности) по памяти.

Применение 4: DFS обход

Depth-first search — самый частый алгоритм обхода графа/дерева. Iterative версия использует стек:

def dfs(start, graph):
    visited = set()
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                stack.append(neighbor)
    return order


graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}
print(dfs('A', graph))   # A, C, D, B  (порядок зависит от того, как мы кладём)

Стек контролирует порядок обхода. Если хотим BFS вместо DFS — заменяем stack на deque-очередь. Об этом — следующий урок и модуль 12-12.

Application 5: backtracking

Если ваше решение требует «пройти по одному пути, если не сработало — откатиться и попробовать другой» — это стек. Примеры: solver судоку, генерация перестановок, поиск пути в лабиринте, парсинг с контекстом.

def permutations(items):
    """Все перестановки items через backtracking стек."""
    n = len(items)
    result = []
    stack = [(items, [])]  # (remaining, current)
    while stack:
        remaining, current = stack.pop()
        if not remaining:
            result.append(current)
            continue
        for i, item in enumerate(remaining):
            new_remaining = remaining[:i] + remaining[i+1:]
            stack.append((new_remaining, current + [item]))
    return result


for p in permutations([1, 2, 3]):
    print(p)

Каждое состояние «куда я сейчас ушёл, что осталось» — фрейм в стеке. Откат = pop. Это базовая техника комбинаторных алгоритмов.

Когда выбрать стек, а когда — нет

Стек подходит когда:

• Нужен LIFO-порядок обработки.
• Решение требует «откатиться к предыдущему шагу» — стек хранит состояния.
• Сопоставление парных элементов (скобки, теги XML).
• DFS обход.
• Iterative version рекурсивного алгоритма (когда CPU stack кончается).

Стек НЕ подходит когда:

• Нужен FIFO — то, что положили раньше, обрабатывается раньше (очереди, BFS, продюсер-консьюмер).
• Нужен random access ко всем элементам.
• Нужны приоритеты (heap, priority queue — модуль 11).

Попробуй сам

Реализуйте Min-Stack — стек с операцией min() за O(1):

class MinStack:
    """Стек с O(1) push, pop, top, min."""

    def __init__(self):
        self._data = []           # обычные значения
        self._min = []            # стек минимумов

    def push(self, x):
        self._data.append(x)
        # обновляем стек минимумов: текущий минимум = min(текущий x, прошлый минимум)
        current_min = x if not self._min else min(x, self._min[-1])
        self._min.append(current_min)

    def pop(self):
        if not self._data:
            raise IndexError("pop from empty stack")
        self._min.pop()
        return self._data.pop()

    def top(self):
        return self._data[-1]

    def min(self):
        return self._min[-1]


ms = MinStack()
ms.push(5)
ms.push(3)
ms.push(7)
ms.push(2)
print(ms.min())   # 2
ms.pop()
print(ms.min())   # 3
ms.pop()
print(ms.min())   # 3

Идея: для каждого нового элемента храним минимум подстека до и включая этот элемент. При pop — снимаем тоже из обоих стеков. Все операции O(1). Это классическая задача с собеседования; решение через два стека — каноничный приём.