Стек, очередь и дек

Три способа складывать и доставать элементы — и почему правильный выбор превращает квадрат в линию.

Стек — структура «последним пришёл — первым вышел» (LIFO); очередь — «первым пришёл — первым вышел» (FIFO); дек — двусторонняя очередь, добавлять и удалять можно с обоих концов.

Зачем это нужно

Это «кирпичики» алгоритмов. Стек лежит в основе разбора выражений, обхода DFS и приёма «ближайший больший элемент». Очередь — это сердце BFS (обход в ширину). Дек используется в скользящем максимуме и в 0-1 BFS. Понимание, какая структура нужна и за сколько работают её операции, часто и есть половина решения задачи. В Python все три реализуются эффективно через список и collections.deque.

Стек: список Python

В Python стек — это обычный список: append кладёт элемент наверх, pop снимает верхний, обе операции — O(1). Классическое применение — проверка правильной скобочной последовательности.

s = "(()(()))"
st = []
ok = True
for ch in s:
    if ch == "(":
        st.append(ch)          # открыли — кладём в стек
    else:
        if not st:             # закрыли, а открытых нет — ошибка
            ok = False; break
        st.pop()               # нашли пару — снимаем
ok = ok and not st             # в конце стек должен быть пуст
print("Скобки правильные:", ok)

Логика: каждая закрывающая скобка должна закрывать последнюю открытую — это в точности дисциплина LIFO. Если в конце стек не пуст, остались незакрытые скобки.

Вывод:

Скобки правильные: True

Очередь и дек: collections.deque

Важный момент: использовать список как очередь нельзя — list.pop(0) работает за O(n), потому что сдвигает все элементы. Для очереди и дека в Python есть collections.deque, где добавление и удаление с обоих концов — O(1).

from collections import deque

dq = deque([1, 2, 3])
dq.appendleft(0)               # 0 1 2 3
dq.append(4)                   # 0 1 2 3 4
print("Дек:", list(dq))
print("popleft:", dq.popleft())  # снять слева -> 0
print("pop:", dq.pop())          # снять справа -> 4
print("Осталось:", list(dq))

Запомни соответствие: очередь = только append + popleft; стек = append + pop; дек = все четыре операции. deque покрывает все три структуры.

Вывод:

Дек: [0, 1, 2, 3, 4]
popleft: 0
pop: 4
Осталось: [1, 2, 3]

Мощный приём: ближайший больший элемент (монотонный стек)

Задача: для каждого элемента массива найти ближайший справа больший. Наивно — O(n^2). Но монотонный стек решает за O(n). Идея: храним в стеке индексы элементов, для которых ответ ещё не найден, поддерживая стек по убыванию значений. Приходит новый элемент — он становится ответом для всех меньших на вершине.

a = [2, 1, 5, 6, 2, 3]
n = len(a)
ans = [-1] * n        # -1, если справа большего нет
st = []               # стек индексов, значения убывают сверху вниз
for i in range(n):
    while st and a[st[-1]] < a[i]:
        ans[st.pop()] = a[i]   # a[i] — ближайший больший для вершины
    st.append(i)
print("Массив:           ", a)
print("Ближайший больший:", ans)

Каждый индекс попадает в стек один раз и удаляется один раз — суммарно O(n), несмотря на вложенный while (та же амортизация, что в скользящем окне). Этот шаблон решает «гистограмму наибольшего прямоугольника», «температуры» и десятки похожих задач.

Вывод:

Массив:            [2, 1, 5, 6, 2, 3]
Ближайший больший: [5, 5, 6, -1, 3, -1]

Сложность операций

Подводные камни

• Не используй список как очередь. list.pop(0) — это O(n); на больших данных получишь TLE. Только deque.popleft().
• Проверяй пустоту перед pop: снятие с пустого стека/дека — это RuntimeError.
• Монотонный стек: внимательно выбирай строгий/нестрогий знак (< или <=) в зависимости от того, как обрабатывать равные элементы.

Итог

• Стек (LIFO) — список Python; очередь (FIFO) и дек — collections.deque, все операции O(1).
• Список как очередь — антипаттерн: pop(0) работает за O(n).
• Монотонный стек находит «ближайший больший/меньший» за O(n) — мощный и частый приём.
• Стек ↔ DFS и скобки, очередь ↔ BFS, дек ↔ скользящий максимум и 0-1 BFS.