Стеки и очереди 🥞

Каждый раз, когда ты вызываешь функцию внутри функции внутри функции, интерпретатор Python (или любого другого языка) незаметно для тебя выполняет одну и ту же операцию: кладёт на невидимую стопку запись «вернуться сюда, когда закончишь» и переходит вглубь вызова. Когда самая внутренняя функция завершается, интерпретатор снимает верхнюю запись со стопки и возвращается точно туда, откуда пришёл — ни строчкой раньше, ни строчкой позже. Эта стопка называется стеком вызовов (call stack), и она обслуживает вообще всё исполнение любой программы, включая ту нейросеть, которую ты, возможно, сейчас обучаешь. В этом уроке ты разберёшь стек и его зеркального близнеца — очередь — как формальные структуры данных: определишь их операции, оценишь их сложность и научишься видеть их там, где они спрятаны внутри привычных инструментов.

Связь со стеком вызовов — это не просто красивая метафора для урока. Возьми любую нейросеть, обученную через loss.backward() в PyTorch или tf.GradientTape в TensorFlow. Во время прямого прохода (forward pass) фреймворк не просто вычисляет числа — он попутно записывает каждую операцию (умножение матриц, применение функции активации, сложение с bias) в вычислительный граф, сохраняя промежуточные тензоры, нужные для будущего дифференцирования. По сути, это последовательное «наращивание» стопки операций, очень похожее на то, как растёт стек вызовов при рекурсивном спуске. А обратный проход (backward pass), вычисляющий градиенты по правилу дифференцирования сложной функции (chain rule), обязан идти в строго обратном порядке — от последней выполненной операции к первой. Это и есть разворачивание стека: последняя добавленная операция обрабатывается первой, ровно по принципу LIFO — «последний пришёл, первый ушёл». Автоматическое дифференцирование в режиме обратного накопления (reverse-mode), на котором построено всё современное глубокое обучение, — это, если убрать техническую обвязку, работа со стеком операций.

Очередь работает по прямо противоположному принципу — FIFO, «первый пришёл, первый ушёл», — и она не менее вездесуща. Классический алгоритм обхода графа в ширину (BFS), который ты изучишь в этом уроке, целиком построен вокруг очереди: сначала обрабатываются все соседи стартовой вершины, потом все соседи соседей, и так далее, слой за слоем. Именно так библиотеки для работы с графами знаний (knowledge graphs) ищут кратчайшую цепочку связей между двумя сущностями, так рекомендательные системы распространяют сигнал по графу «пользователь — товар», а графовые нейросети (GNN) на первых порах формировали свои слои передачи сообщений (message passing) по аналогичной послойной логике. И даже на более приземлённом уровне: когда DataLoader в PyTorch с num_workers > 0 готовит батчи данных для обучения в фоновых процессах, между воркерами и основным циклом обучения стоит именно очередь — с ограниченной ёмкостью, чтобы не переполнить память, но всегда в порядке поступления.

В этом уроке ты последовательно разберёшь стек — его операции, доказательство их сложности O(1) и три ключевых применения (стек вызовов, отмена действий, проверка скобок); затем очередь — её операции и применения (обработка задач по порядку и обход в ширину); коротко познакомишься с деком — двусторонней очередью, которая объединяет возможности обеих структур; и наконец сравнишь две стратегии реализации — через массив и через связный список, опираясь на то, что ты уже знаешь о них из прошлого урока. Тридцать разобранных задач в конце закрепят материал на трассировках, алгоритмах и мини-проектировании — от проверки скобок до симуляции очереди батчей для тренировки нейросети.

История: как появились стек и очередь

Идея стека как механизма для хранения «точек возврата» появилась даже раньше, чем электронные компьютеры научились сами вызывать подпрограммы. В 1945 году Алан Тьюринг, описывая архитектуру будущей машины ACE (Automatic Computing Engine), предложил операции, которые он назвал BURY («закопать») и UNBURY («откопать»): при входе в подпрограмму адрес возврата «закапывался» в специальную область памяти, а при выходе — «откапывался» обратно. По сути, Тьюринг уже тогда описал ровно тот механизм, который сегодня называется стеком вызовов, просто без самого слова «стек» — этот термин появится позже и придёт из совсем другого языка.

Слово «стек» в его нынешнем компьютерном смысле закрепилось благодаря немецким инженерам Клаусу Замельсону (Klaus Samelson) и Фридриху Бауэру (Friedrich L. Bauer) из Мюнхенского технического университета. В середине 1950-х годов они работали над задачей автоматического перевода алгебраических формул в машинный код — по сути, над тем, что сегодня называется компилятором выражений — и столкнулись с необходимостью запоминать промежуточные операнды и операции в правильном порядке для их последующей обратной «раскрутки». В 1957 году они запатентовали устройство, которое назвали немецким словом Kellerspeicher — буквально «подвальная память» или «погребное хранилище» (Keller — «погреб, подвал»). Аналогия была почти буквальной: в немецких пивных и столовых того времени были специальные пружинные стойки для тарелок — чистую тарелку сверху кладёшь, она проседает под своим весом, а когда берёшь верхнюю тарелку, вся стопка снова поднимается на пружине. Именно эта картинка — стопка тарелок, доступная только сверху, — стала интуитивным образом, который вошёл в учебники по информатике по всему миру, а немецкое «Keller» на английский перевели как «stack» — «стопка, стек».

У очереди происхождение более прикладное и менее компьютерное. Сам термин FIFO пришёл из бухгалтерского учёта задолго до появления вычислительной техники — по этому принципу списывалась стоимость товаров на складе («первым закупили — первым и продали»). А математическая теория, которая формально описывает поведение очередей, — теория массового обслуживания — родилась ещё в 1909 году, когда датский инженер Агнер Крарруп Эрланг, работавший в Копенгагенской телефонной компании, вывел формулы для расчёта, сколько телефонных линий нужно, чтобы абоненты не ждали соединения слишком долго. Когда в 1950–60-х годах появились первые операционные системы с пакетной обработкой заданий, разработчики позаимствовали и термин, и саму идею: задания на выполнение вставали в очередь и обрабатывались строго в порядке поступления, чтобы ни одно из них не «зависло» в ожидании навсегда — то самое свойство, которое в информатике называют отсутствием голодания (starvation-freedom) и которое как раз гарантирует дисциплина FIFO.

Обе идеи довольно быстро срослись в единый набор инструментов программиста. Уже в 1961 году нидерландский математик Эдсгер Дейкстра предложил алгоритм сортировочной станции (shunting-yard algorithm) для перевода арифметических выражений из привычной инфиксной записи в постфиксную — с помощью одного-единственного стека для операторов. Этот алгоритм, придуманный больше шестидесяти лет назад, до сих пор лежит в основе того, как калькуляторы и компиляторы разбирают математические выражения, — ты разберёшь его облегчённую версию в практической части урока.

Стек: LIFO — последний пришёл, первый ушёл

Интуиция

Возьми стопку книг на столе. Ты можешь свободно положить новую книгу сверху или снять верхнюю — но чтобы добраться до книги в середине стопки, придётся сначала снять всё, что лежит выше. Это и есть суть стека: доступ разрешён только к одному концу структуры, который принято называть вершиной (top). Всё, что было добавлено последним, будет извлечено первым — отсюда и название принципа LIFO, Last In, First Out.

Обрати внимание: стек — это не про хранение данных «вообще», а про строго определённую дисциплину доступа к ним. Внутри стек вполне может быть реализован и как массив, и как связный список (к этому ты вернёшься в отдельном разделе), но снаружи он всегда выглядит одинаково — набором из нескольких операций, каждая из которых имеет смысл только применительно к вершине.

Определение: Стек — это абстрактный тип данных, реализующий принцип LIFO: элементы добавляются и удаляются только с одного конца структуры, называемого вершиной. Базовые операции стека — push(x) (положить элемент x на вершину), pop() (снять и вернуть элемент с вершины), peek() или top() (посмотреть элемент на вершине, не снимая его) и is_empty() (проверить, пуст ли стек). При корректной реализации все четыре операции выполняются за время O(1), потому что каждая из них затрагивает исключительно вершину структуры — независимо от того, сколько элементов лежит под ней.

Почему именно O(1), а не, скажем, O(n)? Потому что ни одна из операций стека не требует «заглядывать» вглубь структуры или сдвигать другие элементы: вершина стека всегда известна заранее (это либо последний элемент динамического массива, либо голова связного списка), и любое изменение происходит ровно в одной точке — без перебора и без сдвига остальных элементов. Это ключевое отличие стека от произвольного доступа по индексу массива, где O(1) достигается за счёт адресной арифметики, но, например, вставка в середину массива уже требует O(n) на сдвиг соседей.

На Python простейший стек — это обычный список: append(x) для push и pop() (без аргумента — по умолчанию снимается последний элемент) для pop.

stack = []
stack.append(1)   # push(1) -> [1]
stack.append(2)   # push(2) -> [1, 2]
stack.append(3)   # push(3) -> [1, 2, 3]

top = stack[-1]    # peek() -> 3, стек не меняется
last = stack.pop()  # pop() -> 3, стек становится [1, 2]
print(stack.pop())  # pop() -> 2, стек становится [1]

Примеры с разбором

Пример 1 (лёгкий). Стек вызовов и рекурсия. Рассмотрим рекурсивную функцию вычисления факториала и явно проследим, как интерпретатор использует стек вызовов.

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

factorial(4)

При вызове factorial(4) интерпретатор не может сразу вернуть результат — сначала нужно узнать factorial(3), а для этого — factorial(2), и так далее. Каждый такой «незавершённый» вызов кладётся на стек вызовов в виде кадра стека (stack frame), хранящего значение параметра n и точку, куда нужно вернуться:

push factorial(4)  -> стек: [f(4)]
push factorial(3)  -> стек: [f(4), f(3)]
push factorial(2)  -> стек: [f(4), f(3), f(2)]
push factorial(1)  -> стек: [f(4), f(3), f(2), f(1)]   # базовый случай, возвращает 1
pop  factorial(1)  -> f(2) получает 1, считает 2*1=2
pop  factorial(2)  -> f(3) получает 2, считает 3*2=6
pop  factorial(3)  -> f(4) получает 6, считает 4*6=24
pop  factorial(4)  -> итоговый результат: 24

Обрати внимание на порядок: f(1) был добавлен последним — и обработан первым при разворачивании. Это ровно LIFO. Именно поэтому у рекурсии есть предел глубины (в Python — по умолчанию около тысячи вложенных вызовов, sys.getrecursionlimit()): стек вызовов — это ограниченный по размеру участок памяти, и слишком глубокая рекурсия без базового случая приводит к ошибке RecursionError — программному аналогу переполнения стека (stack overflow).

Именно этот механизм лежит в основе обратного распространения ошибки в нейросетях. Когда PyTorch выполняет y = w2 @ relu(w1 @ x + b1) + b2, во время прямого прохода он записывает граф операций примерно как последовательность вложенных вызовов: сначала «войти» в умножение w1 @ x, затем в сложение + b1, затем в relu(...), затем в w2 @ (...), затем в + b2. При вызове loss.backward() автоматическое дифференцирование обходит этот граф в порядке, обратном тому, в котором операции выполнялись, — вычисляя локальную производную каждой операции и «умножая» её на градиент, пришедший сверху по цепному правилу. Последняя выполненная операция (сложение + b2) дифференцируется первой, самая первая операция (w1 @ x) — последней. Это структурно тот же самый LIFO-порядок, что и при возврате из рекурсивных вызовов factorial.

Пример 2 (средний). Отмена действий (Undo). Многие редакторы хранят историю действий в виде стека: каждое новое действие кладётся на вершину, а Undo снимает верхнее действие и отменяет именно его — то есть последнее из сделанных.

class TextEditor:
    def __init__(self):
        self.text = ""
        self.history = []  # стек предыдущих состояний текста

    def type(self, chars):
        self.history.append(self.text)  # push текущего состояния перед изменением
        self.text += chars

    def undo(self):
        if self.history:
            self.text = self.history.pop()  # pop последнего сохранённого состояния
        else:
            print("Нечего отменять")

editor = TextEditor()
editor.type("Привет")       # history: [""]
editor.type(", мир")        # history: ["", "Привет"]
editor.type("!!!")          # history: ["", "Привет", "Привет, мир"]
print(editor.text)          # "Привет, мир!!!"

editor.undo()                # снимаем "Привет, мир" -> text = "Привет, мир"
print(editor.text)           # "Привет, мир"
editor.undo()                # снимаем "Привет" -> text = "Привет"
print(editor.text)           # "Привет"

Обрати внимание: undo() всегда откатывает именно последнее действие, а не какое-то произвольное — это прямое следствие LIFO. Если бы вместо стека использовалась очередь, первый Ctrl+Z отменял бы самое первое из когда-либо сделанных действий, что было бы совершенно бесполезно для пользователя. Ровно по этой же схеме устроены git revert последнего коммита, стек истории браузера (кнопка «Назад» ведёт на предыдущую посещённую страницу, а не на первую в сессии) и механизм отмены хода в шахматных движках.

Пример 3 (сложный). Проверка сбалансированности скобок. Классическая задача: дана строка со скобками, нужно определить, правильно ли они расставлены — каждой открывающей соответствует закрывающая того же типа, и порядок закрытия соблюдён.

def is_balanced(expression):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for char in expression:
        if char in "([{":
            stack.append(char)          # push открывающей скобки
        elif char in ")]}":
            if not stack or stack[-1] != pairs[char]:
                return False             # нечего закрывать или неверный тип
            stack.pop()                  # закрыли верхнюю открывающую скобку
    return len(stack) == 0               # все открытые скобки должны быть закрыты

print(is_balanced("{[()()]}"))  # True
print(is_balanced("([)]"))      # False — неверный порядок закрытия
print(is_balanced("(()"))       # False — незакрытая скобка осталась в стеке

Ключевая деталь, которую часто упускают: недостаточно просто считать количество открывающих и закрывающих скобок — строка "([)]" содержит поровну открывающих и закрывающих скобок, но не является правильной, потому что ] пытается закрыть (, а не [. Именно стек (а не простой счётчик) хранит нужную информацию о порядке вложенности, и сравнение на каждом шаге происходит с самой последней ещё не закрытой скобкой — вершиной стека. Этот алгоритм — не учебная абстракция: ровно он используется внутри парсеров JSON и YAML (конфигурационные файлы моделей машинного обучения — от config.yaml для гиперпараметров до архитектурных описаний в форматах наподобие ONNX), внутри синтаксических анализаторов языков программирования и внутри линтеров кода, которые подсвечивают тебе незакрытую скобку ещё до запуска программы.

Почему это важно. Все три примера объединяет одно: стек — это естественная структура данных для любой задачи, где нужно «запомнить, куда вернуться» или «отменить последнее из сделанного». Гарантия O(1) на все операции делает стек эффективным даже при огромной глубине вложенности, а сама дисциплина LIFO избавляет от необходимости вручную отслеживать порядок — достаточно довериться структуре. В контексте машинного обучения это не абстракция для собеседований: именно на этом принципе построен движок автоматического дифференцирования, без которого не существовало бы современного глубокого обучения, — обратный проход обязан идти в порядке, обратном прямому, и стек — единственная структура, которая гарантирует это без дополнительных ухищрений.

Очередь: FIFO — первый пришёл, первый ушёл

Интуиция

Очередь в продуктовом магазине работает по правилу, которое интуитивно понятно каждому: кто встал раньше — того обслужат раньше. Никто не «перепрыгивает» вперёд, и никто не остаётся в конце навсегда, если только не перестаёт продвигаться вся очередь целиком. Это ровно тот принцип, который в информатике называют FIFO — First In, First Out.

В отличие от стека, у очереди задействованы два разных конца структуры: элементы добавляются с одного конца (принято называть его хвостом, rear или back) и удаляются с другого (головы, front). Именно эта двухконечная природа делает наивную реализацию очереди через обычный массив менее очевидной, чем реализация стека, — к этому нюансу ты вернёшься в разделе о реализациях.

Определение: Очередь — это абстрактный тип данных, реализующий принцип FIFO: элементы добавляются в один конец структуры (хвост) и удаляются с другого конца (голова). Базовые операции — enqueue(x) (добавить элемент x в хвост), dequeue() (удалить и вернуть элемент из головы), peek() или front() (посмотреть элемент в голове, не удаляя его) и is_empty() (проверить, пуста ли очередь). При грамотной реализации (двусторонний связный список, кольцевой буфер или структура вроде collections.deque в Python) все четыре операции выполняются за O(1).

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

from collections import deque

queue = deque()
queue.append("заявка №1")   # enqueue -> хвост
queue.append("заявка №2")   # enqueue -> хвост
queue.append("заявка №3")   # enqueue -> хвост

first = queue.popleft()     # dequeue -> из головы, вернёт "заявка №1"
print(first)                 # заявка №1
print(list(queue))           # ['заявка №2', 'заявка №3']

Примеры с разбором

Пример 1 (лёгкий). Обработка задач по порядку. Служба поддержки обрабатывает заявки строго в порядке поступления — это прямое применение FIFO, гарантирующее, что ни один клиент не будет ждать бесконечно долго, пока обслуживают тех, кто пришёл позже.

from collections import deque

support_queue = deque()
support_queue.append("Не работает Wi-Fi")
support_queue.append("Проблема с оплатой")
support_queue.append("Медленный интернет")

while support_queue:
    ticket = support_queue.popleft()
    print(f"Обрабатываем: {ticket}")

# Обрабатываем: Не работает Wi-Fi
# Обрабатываем: Проблема с оплатой
# Обрабатываем: Медленный интернет

Это же свойство «справедливости» (fairness) используется в планировщиках задач операционных систем, в очередях печати и в брокерах сообщений вроде RabbitMQ или Kafka, где по умолчанию сообщения одного раздела обрабатываются в порядке поступления, если явно не задана иная приоритизация.

Пример 2 (средний). Обход графа в ширину (BFS). BFS исследует граф «слоями»: сначала все вершины на расстоянии одного ребра от старта, потом все вершины на расстоянии двух рёбер, и так далее. Такой порядок достигается ровно за счёт очереди: пока обрабатываешь текущую вершину, все её ещё не посещённые соседи ставятся в конец очереди — а значит, будут обработаны только после всех вершин, поставленных раньше.

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
}

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()       # dequeue
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)  # enqueue
    return order

print(bfs(graph, "A"))  # ['A', 'B', 'C', 'D', 'E']

Трассировка по шагам: очередь стартует как [A]. Снимаем A, добавляем его соседей B, C → очередь [B, C]. Снимаем B, его сосед D ещё не посещён → очередь [C, D]. Снимаем C, сосед D уже добавлен, ничего не меняется → очередь [D]. Снимаем D, добавляем E → очередь [E]. Снимаем E → очередь пуста, обход завершён. Сложность BFS — O(V + E), где V — число вершин, а E — число рёбер: каждая вершина попадает в очередь и покидает её ровно один раз, а каждое ребро просматривается не более двух раз (по разу с каждого конца).

Именно этот алгоритм используется для поиска кратчайшего пути по числу рёбер между двумя сущностями в графе знаний — скажем, чтобы найти минимальную цепочку связей между «Эйнштейн» и «Нобелевская премия» в графе вроде Wikidata: BFS от стартовой сущности гарантированно найдёт ближайшую по числу шагов вершину раньше, чем любую более далёкую, — свойство, которого не даёт DFS на стеке. Та же послойная логика используется и при обходе иерархических структур данных — от дерева зависимостей пакетов до организационной структуры компании, — а в графовых нейросетях (GNN) классическая передача сообщений (message passing) на каждом «слое» агрегирует информацию именно от непосредственных соседей, что структурно повторяет один шаг BFS.

Пример 3 (сложный). Очередь как буфер между производителем и потребителем. В реальных пайплайнах обучения нейросетей подготовка батча данных (чтение файлов, декодирование изображений, аугментации) обычно медленнее, чем один шаг обучения на GPU. Чтобы GPU не простаивал, данные готовят заранее в фоновых процессах-«воркерах» и складывают в очередь ограниченного размера, из которой основной цикл обучения их забирает.

import queue
import threading

MAX_BUFFER = 3
batch_queue = queue.Queue(maxsize=MAX_BUFFER)  # ограниченная очередь (bounded queue)

def producer(n_batches):
    for i in range(n_batches):
        batch = f"батч #{i}"
        batch_queue.put(batch)   # enqueue; блокируется, если очередь заполнена
        print(f"подготовлен {batch}")
    batch_queue.put(None)         # сигнал об окончании данных

def consumer():
    while True:
        batch = batch_queue.get()  # dequeue; блокируется, если очередь пуста
        if batch is None:
            break
        print(f"  обучаемся на {batch}")

threading.Thread(target=producer, args=(6,)).start()
consumer()

Ограничение maxsize=MAX_BUFFER здесь принципиально: без него воркер-производитель мог бы подготовить данные гораздо быстрее, чем модель успевает их потреблять, и очередь неограниченно растянулась бы в памяти. Ограниченная очередь с блокировкой (bounded blocking queue) — это ровно тот механизм, который скрыт внутри torch.utils.data.DataLoader(num_workers=k): несколько процессов-воркеров параллельно готовят батчи и кладут их в общую очередь, а основной цикл обучения забирает их строго по порядку подготовки, не заботясь о том, какой именно воркер собрал конкретный батч.

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

Дек: очередь с двух сторон

Дек (deque, double-ended queue — «двусторонняя очередь») обобщает и стек, и очередь: он позволяет добавлять и удалять элементы с обоих концов за O(1), а не только с одного или с разных предопределённых концов.

Определение: Дек — абстрактный тип данных, поддерживающий четыре операции за O(1): append(x) и appendleft(x) (добавить элемент справа и слева соответственно), pop() и popleft() (удалить и вернуть элемент справа и слева соответственно). Используя только правый конец, дек ведёт себя как стек; используя добавление справа и удаление слева (или наоборот) — как очередь. Поэтому на практике дек нередко заменяет собой обе структуры сразу.

В Python дек реализован в модуле collections и оптимизирован именно под операции на обоих концах:

from collections import deque

d = deque([2, 3, 4])
d.appendleft(1)   # [1, 2, 3, 4]
d.append(5)        # [1, 2, 3, 4, 5]
d.popleft()         # вернёт 1, останется [2, 3, 4, 5]
d.pop()              # вернёт 5, останется [2, 3, 4]

Пример 1. Скользящее окно максимума. Классическая задача обработки временных рядов: для массива и размера окна k найти максимум в каждом окне из k последовательных элементов. Наивное решение пересчитывает максимум заново на каждом шаге за O(n·k); дек позволяет сделать это за O(n), поддерживая в себе только индексы «потенциально полезных» элементов в убывающем порядке значений.

from collections import deque

def sliding_window_max(nums, k):
    dq = deque()   # хранит индексы, значения убывают слева направо
    result = []
    for i, num in enumerate(nums):
        while dq and nums[dq[-1]] <= num:
            dq.pop()               # справа удаляем всё, что заведомо меньше текущего
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()            # слева удаляем то, что выпало из окна
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

print(sliding_window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

Такая техника — не редкость в инженерии признаков (feature engineering) для временных рядов: скользящий максимум, минимум или похожие агрегаты по окну часто вычисляются в потоковом режиме, и дек даёт линейную сложность там, где наивный подход был бы квадратичным.

Пример 2. История браузера «Назад / Вперёд». Навигацию по истории посещённых страниц удобно реализовать двумя стеками (или одним деком, если рассматривать текущую позицию как разделитель): один хранит страницы «назад», другой — страницы «вперёд». Переход на новую страницу очищает стек «вперёд» — типичное поведение любого браузера.

class BrowserHistory:
    def __init__(self, homepage):
        self.back_stack = []
        self.forward_stack = []
        self.current = homepage

    def visit(self, url):
        self.back_stack.append(self.current)
        self.current = url
        self.forward_stack.clear()  # новый переход обнуляет историю "вперёд"

    def back(self):
        if self.back_stack:
            self.forward_stack.append(self.current)
            self.current = self.back_stack.pop()
        return self.current

    def forward(self):
        if self.forward_stack:
            self.back_stack.append(self.current)
            self.current = self.forward_stack.pop()
        return self.current

Почему это важно именно в контексте дека: обе операции — «назад» и «вперёд» — требуют доступа к обоим концам истории, и хотя пример реализован двумя стеками, ту же логику можно свернуть в один дек, где текущая позиция — это курсор посередине, а appendleft/popleft и append/pop обслуживают противоположные направления навигации. Дек полезен именно тогда, когда заранее неясно, с какого конца понадобится доступ следующим — а таких задач в реальном коде набирается немало.

Реализация стека и очереди: массив vs связный список

Интуиция

В прошлом уроке ты разобрал ключевой компромисс массивов и связных списков: массив даёт быстрый доступ по индексу, но дорогую вставку в начало; связный список — наоборот. Для стека и очереди этот компромисс проявляется по-своему, потому что ни стек, ни очередь никогда не обращаются к элементам по произвольному индексу — они всегда работают только с определёнными концами структуры. Вопрос, соответственно, не «что быстрее — доступ по индексу или переход по указателю», а «какой конец массива или списка можно менять за O(1), а какой — нет».

Сравнение: Стек работает только с одним концом, и добавление/удаление с конца динамического массива (Python list.append/list.pop) выполняется за O(1) в амортизированном смысле — то есть удвоение внутренней ёмкости массива происходит редко и не портит среднюю оценку. Поэтому для стека массив (динамический) — почти всегда лучший выбор. Для очереди ситуация сложнее: удаление из начала обычного массива требует сдвига всех оставшихся элементов и стоит O(n), поэтому очередь либо реализуют на связном списке с хранимыми указателями на голову и хвост (обе операции — O(1)), либо на кольцевом буфере (circular buffer) поверх массива, либо используют готовую двустороннюю структуру вроде collections.deque, которая внутри устроена как связный список блоков фиксированного размера и даёт O(1) на обоих концах.

Примеры с разбором

Пример 1 (лёгкий). Стек на динамическом массиве. Реализация стека через list — не случайный выбор, а прямое следствие того, как в лекции 252 устроен динамический массив: он хранит запас (capacity) сверх текущего размера, и append/pop с конца почти всегда просто меняют одну ячейку и счётчик размера, без сдвига остальных элементов.

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

    def push(self, x):
        self._data.append(x)         # O(1) амортизированно

    def pop(self):
        if not self._data:
            raise IndexError("pop из пустого стека")
        return self._data.pop()      # O(1)

    def peek(self):
        return self._data[-1]         # O(1)

    def is_empty(self):
        return len(self._data) == 0

Изредка (когда внутренний массив заполняется целиком) append вынужден выделить новый, вдвое больший блок памяти и скопировать в него все элементы — это единичная операция стоимостью O(n). Но, как ты уже видел на примере динамических массивов в прошлом уроке, суммарная стоимость всех таких копирований на протяжении n операций push не превышает O(n) — то есть в среднем на одну операцию приходится O(1). Именно это называется амортизированной сложностью.

Пример 2 (средний). Наивная очередь на массиве против collections.deque. Если реализовать очередь через list, используя pop(0) для извлечения из начала, каждая такая операция потребует сдвинуть все оставшиеся элементы на одну позицию влево — это O(n).

import time
from collections import deque

n = 20_000

# Наивная реализация на списке
naive_queue = list(range(n))
start = time.perf_counter()
while naive_queue:
    naive_queue.pop(0)     # O(n) на каждый вызов -> O(n^2) суммарно
naive_time = time.perf_counter() - start

# Эффективная реализация на deque
efficient_queue = deque(range(n))
start = time.perf_counter()
while efficient_queue:
    efficient_queue.popleft()  # O(1) на каждый вызов -> O(n) суммарно
efficient_time = time.perf_counter() - start

print(naive_time, efficient_time)  # naive_time на порядки больше efficient_time

Разница не теоретическая: при n = 20 000 наивная версия выполняет порядка 4·10⁸ элементарных операций сдвига (n²/2), а deque — порядка 20 000. На практике это разница между долями секунды и десятками секунд — при том, что снаружи обе версии «просто убирают элемент из начала очереди».

Пример 3 (сложный). Очередь на связном списке с указателями на голову и хвост. Чтобы enqueue и dequeue были честными O(1) без амортизации и без магии deque, достаточно хранить не только указатель на голову списка, но и указатель на хвост — тогда добавление в конец не требует обхода всего списка.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedListQueue:
    def __init__(self):
        self.head = None   # голова -> отсюда dequeue
        self.tail = None   # хвост -> сюда enqueue

    def enqueue(self, x):
        node = Node(x)
        if self.tail is None:          # очередь была пуста
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node            # O(1) благодаря хранимому указателю

    def dequeue(self):
        if self.head is None:
            raise IndexError("dequeue из пустой очереди")
        value = self.head.value
        self.head = self.head.next
        if self.head is None:           # очередь опустела
            self.tail = None
        return value                     # O(1)

Без указателя на хвост добавление в конец связного списка потребовало бы каждый раз проходить его целиком в поисках последнего узла — O(n). Именно хранение обоих концов делает связный список полноценной альтернативой массиву для очереди. Плата за это — дополнительная память на каждый узел (указатель next, а в двусвязных версиях ещё и prev) и худшая локальность в кэше процессора: узлы связного списка могут быть разбросаны по памяти как угодно, тогда как элементы массива лежат подряд, и процессор может подгружать их пачками — это одна из причин, почему на практике collections.deque (гибрид: связный список блоков-массивов) и массив-ориентированные реализации обычно быстрее «наивного» связного списка из отдельных узлов, даже при одинаковой асимптотической сложности O(1).

Почему это важно. Выбор между массивом и связным списком для стека и очереди — это конкретное, измеримое инженерное решение, а не вопрос вкуса. Для стека выбор почти всегда очевиден — динамический массив, потому что стек трогает только один конец, который у массива работает быстро. Для очереди наивный массив — ловушка: он даёт быстрый push, но убийственно медленный pop с другого конца, поэтому либо связный список с двумя указателями, либо кольцевой буфер, либо (в подавляющем большинстве реальных программ) готовая структура collections.deque, уже решившая эту проблему за тебя.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1. Дана последовательность операций над пустым стеком: push(1), push(2), push(3), pop(), push(4), pop(). Что вернут два вызова pop() и что останется в стеке в конце?

Задание 2. Дана последовательность операций над пустой очередью: enqueue(A), enqueue(B), dequeue(), enqueue(C), dequeue(). Что вернут два вызова dequeue() и что останется в очереди?

Задание 3. Стек реализован через динамический массив (список Python, append/pop с конца). Какова сложность операций push и pop? Объясни, почему она именно такая.

Задание 4. Почему list.pop(0) в Python (удаление первого элемента обычного списка) стоит O(n), а не O(1)?

Задание 5. Дана строка скобок "(()())". Проверь её сбалансированность с помощью стека, расписав состояние стека после обработки каждого символа.

Задание 6. Чем принципиально отличается порядок обработки элементов в стеке от порядка в очереди? Приведи по одной жизненной аналогии для каждой структуры.

Задание 7. Какая структура данных лежит в основе функции «Назад» (Undo, Ctrl+Z) в текстовом редакторе — стек или очередь? Обоснуй выбор.

Задание 8. Дан код: d = deque([10, 20, 30]); d.appendleft(5); d.pop(); d.append(40). Каково итоговое содержимое дека d (слева направо)?

Задание 9. Объясни, почему вызов рекурсивной функции без корректного базового случая рано или поздно приводит к ошибке RecursionError в Python. Свяжи объяснение с механизмом стека вызовов.

Задание 10. Перечисли четыре базовые операции дека и укажи их сложность.

Средние задания (11–20)

Задание 11. Реализуй проверку сбалансированности скобок для трёх типов — (), [], {}. Протрассируй алгоритм на строке "{[()()]}".

Задание 12. Вычисли значение выражения в постфиксной записи (обратной польской нотации) "3 4 + 2 *" с помощью стека, расписав его состояние на каждом шаге.

Задание 13. Дан граф списком смежности: A: [B, C], B: [A, D], C: [A, D], D: [B, C]. Проведи BFS от вершины A, показав содержимое очереди на каждом шаге.

Задание 14. Реализуй очередь с помощью двух стеков. Опиши алгоритм enqueue/dequeue и оцени амортизированную сложность операций.

Задание 15. Реализуй стек с помощью одной очереди. Опиши алгоритм push, обеспечивающий корректный LIFO-порядок при последующих pop.

Задание 16. Реши задачу «скользящее окно максимума» для массива [4, 2, 7, 1, 5] при размере окна k = 2, используя дек с хранением индексов.

Задание 17. Опиши логику работы «истории браузера» с кнопками «Назад» и «Вперёд» через два стека: что происходит при обычном переходе на новую страницу, при нажатии «Назад» и при нажатии «Вперёд».

Задание 18. Дано дерево: корень 1 с детьми 2 и 3; у 2 дети 4 и 5; у 3 ребёнок 6. Распиши обход дерева по уровням (level-order traversal) через очередь, показав её содержимое на каждом шаге.

Задание 19. Оцени сложность по времени для n операций dequeue, если очередь реализована на списке Python через list.pop(0). Сравни с реализацией на collections.deque.

Задание 20. Опиши задачу «производитель — потребитель» с очередью ограниченной ёмкости (capacity = k): что происходит, когда очередь заполнена, и что происходит, когда она пуста? Какая структура данных используется в torch.utils.data.DataLoader(num_workers=...) для этого паттерна?

Сложные задания (21–30)

Задание 21. Спроектируй стек, поддерживающий операцию get_min() за O(1) в дополнение к push/pop. Опиши структуру с двумя стеками и распиши её работу на последовательности push(5), push(2), push(7), get_min(), pop(), get_min().

Задание 22. Реши задачу «следующий больший элемент» для массива [2, 1, 2, 4, 3] с помощью монотонного стека: для каждого элемента найди ближайший справа элемент, который больше него (или -1, если такого нет).

Задание 23. Опиши реализацию очереди на кольцевом буфере (circular buffer) фиксированного размера через массив: как устроены индексы head и tail, и по какому признаку буфер считается полным, а по какому — пустым.

Задание 24. Для выражения (a * b) + c распиши порядок операций прямого прохода (forward, что «кладётся» на стек вычислительного графа) и обратного прохода (backward, порядок вычисления градиентов). Покажи, что порядок backward строго обратен порядку forward.

Задание 25. Докажи, что амортизированная сложность операции enqueue в очереди, реализованной через удваивающийся кольцевой буфер (при заполнении буфер целиком копируется в новый, вдвое больший), равна O(1).

Задание 26. В графе знаний есть сущности и связи: Эйнштейн — Нобелевская_премия, Эйнштейн — Теория_относительности, Теория_относительности — Физика, Нобелевская_премия — Физика, Физика — Наука. Найди кратчайший по числу рёбер путь от Эйнштейн до Наука с помощью BFS, восстановив путь через словарь предков (parent pointers).

Задание 27. Сравни систему обработки задач с одной FIFO-очередью и систему с несколькими очередями разного приоритета — в контексте планирования задач обучения моделей на кластере GPU. Какие есть компромиссы?

Задание 28. Спроектируй дек ограниченной вместимости (maxlen) для скользящего окна признаков в потоковой обработке временного ряда. Какие операции нужны, и какова их сложность?

Задание 29. Объясни, почему рекурсивная реализация обхода графа в глубину (DFS) эквивалентна использованию явного стека, и перепиши рекурсивный DFS в итеративный вариант с явным стеком. Протрассируй на графе A: [B, C], B: [D], C: [D], D: [], начиная с A.

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []
    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

Задание 30. Спроектируй систему обработки батчей для обучения нейросети: данные читаются асинхронно несколькими воркерами и складываются в очередь ограниченного размера, а тренировочный цикл извлекает батчи из этой очереди. Опиши: почему нужна именно очередь, а не стек; какие проблемы возникают при переполнении и опустошении очереди; как это соотносится с torch.utils.data.DataLoader(num_workers=...).

Частые ошибки

❌ Ошибка: Использовать list.pop(0) или list.insert(0, x) в Python для реализации очереди.

✅ Правильно: Использовать collections.deque с append/popleft.

💡 Почему: Операции с началом обычного списка в Python стоят O(n) из-за сдвига всех оставшихся элементов; на n операций это превращается в O(n²) суммарно, тогда как deque даёт честные O(1) на каждую операцию.

❌ Ошибка: Проверять сбалансированность скобок, просто сравнивая количество открывающих и закрывающих символов, без учёта их порядка и типа.

✅ Правильно: Использовать стек и сравнивать тип закрывающей скобки с вершиной стека при каждом закрытии.

💡 Почему: Строка вроде "([)]" содержит поровну открывающих и закрывающих скобок, но не является правильной — только стек хранит информацию о порядке вложенности, необходимую для корректной проверки.

❌ Ошибка: Вызывать pop()/dequeue() без предварительной проверки на пустоту структуры.

✅ Правильно: Всегда проверять is_empty() (или перехватывать исключение) перед извлечением элемента.

💡 Почему: Попытка снять элемент с пустого стека или очереди приводит к ошибке времени выполнения (IndexError для списка, IndexError для пустого deque) — и в отладке такую ошибку проще предотвратить заранее, чем перехватывать постфактум.

❌ Ошибка: Путать порядок обработки BFS и DFS — например, случайно использовать стек там, где задача требует именно послойного обхода (кратчайший путь по числу рёбер).

✅ Правильно: Для гарантии кратчайшего пути по числу рёбер и послойного обхода использовать очередь (BFS); стек даёт обход «вглубь-первым» (DFS) с совершенно другими гарантиями.

💡 Почему: Замена очереди на стек в реализации обхода графа не вызывает ошибку выполнения — программа просто молча делает не то, что задумано, и находит не кратчайший, а произвольный путь.

❌ Ошибка: Считать, что глубина рекурсии не имеет значения, потому что «современные компьютеры мощные».

✅ Правильно: Учитывать лимит глубины стека вызовов (в Python — порядка тысячи кадров по умолчанию) и при необходимости переписывать глубокую рекурсию в итеративный вариант с явным стеком.

💡 Почему: Стек вызовов ограничен по размеру независимо от мощности процессора; на входных данных с большой глубиной вложенности (например, при обходе очень длинной цепочки узлов дерева или связного списка) рекурсивное решение может упасть с RecursionError там, где итеративное с явным стеком отработает без проблем.

❌ Ошибка: Реализовывать очередь на связном списке, храня указатель только на голову, а не на хвост.

✅ Правильно: Хранить оба указателя — на голову и на хвост — чтобы enqueue не требовал обхода всего списка.

💡 Почему: Без указателя на хвост добавление нового элемента в конец связного списка потребовало бы каждый раз проходить его целиком в поисках последнего узла, превращая enqueue из O(1) в O(n).

Главное запомнить

✅ Стек (LIFO) — последний пришёл, первый ушёл; операции push, pop, peek, is_empty работают за O(1), потому что затрагивают только вершину

✅ Очередь (FIFO) — первый пришёл, первый ушёл; операции enqueue, dequeue, peek, is_empty работают за O(1) при правильной реализации (связный список с указателем на хвост, кольцевой буфер или collections.deque)

✅ Стек вызовов (call stack) — это буквально стек в смысле структуры данных: каждый вызов функции — push, каждый возврат — pop

✅ Обратное распространение ошибки (backpropagation) в нейросетях устроено по тому же LIFO-принципу: обратный проход обрабатывает операции строго в порядке, обратном прямому проходу

✅ Проверка сбалансированности скобок, отмена действий (Undo) и разбор арифметических выражений — классические применения стека

✅ Обход графа в ширину (BFS) построен на очереди и гарантирует нахождение кратчайшего пути по числу рёбер за счёт послойной обработки вершин

✅ Дек объединяет стек и очередь, поддерживая добавление и удаление с обоих концов за O(1); полезен для скользящих окон и двусторонней навигации

✅ Для стека почти всегда лучший выбор реализации — динамический массив (амортизированное O(1) на одном конце); для очереди наивный массив — ловушка (O(n) на dequeue), нужен связный список с двумя указателями, кольцевой буфер или deque

✅ list.pop(0) в Python — частая ошибка новичков при реализации очереди; правильный инструмент — collections.deque

✅ Ограниченные (bounded) очереди — стандартный механизм синхронизации между «быстрым» и «медленным» процессами, включая очередь батчей данных между воркерами DataLoader и циклом обучения модели

Связь с темами курса

🔙 Откуда пришли: Из урока 252 — массивы и связные списки как два способа хранить последовательность данных, и их компромисс между быстрым доступом по индексу и быстрой вставкой/удалением; стек и очередь — это тот же самый спор о реализации, но применённый к строго ограниченному набору операций на концах структуры.

🔜 Куда идём:

• Связные списки (урок 254) — более глубокий разбор структуры, которая часто служит фундаментом для эффективной реализации очереди
• Хэш-таблицы (урок 255) — ещё одна абстракция поверх массива, но с принципиально иной дисциплиной доступа
• Графы и их обходы (последующие уроки блока) — прямое развитие темы BFS, начатой в этом уроке, вместе с DFS на стеке

🎯 В машинном обучении: Обратное распространение ошибки (backpropagation) в фреймворках вроде PyTorch и TensorFlow структурно устроено как разворачивание стека операций вычислительного графа — реализовано через сохранённый на прямом проходе «тейп» операций, который обратный проход обрабатывает в порядке LIFO. Обход графа в ширину лежит в основе поиска кратчайших путей в графах знаний и послойной передачи сообщений (message passing) в графовых нейросетях (GNN). Ограниченные очереди — стандартный механизм в torch.utils.data.DataLoader для асинхронной подготовки батчей несколькими воркерами без простоя GPU и без неограниченного роста потребления памяти.

Интересные факты

📌 Алан Тьюринг описал механизм, эквивалентный стеку, ещё в 1945 году в отчёте о машине ACE — операции он назвал BURY («закопать») и UNBURY («откопать») для сохранения и восстановления адреса возврата из подпрограммы, за десять с лишним лет до того, как за этой структурой закрепилось привычное сегодня слово «стек».

📌 Само слово «стек» пришло из немецкого Kellerspeicher («погребное хранилище») — термина, который в 1957 году предложили инженеры Клаус Замельсон и Фридрих Бауэр из Мюнхена, вдохновившись пружинными стойками для тарелок в столовых: положил тарелку сверху — стопка просела, взял верхнюю — стопка снова поднялась. Эта же аналогия стопки тарелок используется в учебниках по всему миру и сегодня.

📌 Термин «stack overflow» (переполнение стека) — ошибка, возникающая при превышении лимита глубины стека вызовов, — дал название крупнейшему в мире сайту вопросов и ответов для программистов, Stack Overflow, основанному в 2008 году.

📌 Математическая теория очередей — теория массового обслуживания — на самом деле старше электронных компьютеров почти на полвека: её заложил в 1909 году датский инженер Агнер Эрланг, рассчитывая, сколько телефонных линий нужно Копенгагенской телефонной станции, чтобы абоненты не ждали соединения слишком долго. Единица измерения телефонной нагрузки «эрланг» названа в его честь и используется до сих пор в телекоммуникациях.

Лайфхаки

💡 Если задача формулируется как «нужно обработать самый последний / самый свежий элемент в первую очередь» — почти наверняка нужен стек. Если формулировка «нужно обработать в порядке поступления, никого не обделив» — почти наверняка нужна очередь. Эта простая проверка экономит время при выборе структуры на собеседовании и в реальном коде.

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

💡 Заметив в задаче словосочетания «следующий больший элемент», «предыдущий меньший», «скользящее окно максимума/минимума» — это почти всегда сигнал к паттерну «монотонный стек» или «монотонный дек», который решает такие задачи за O(n) вместо наивных O(n²).

💡 Если рекурсивная функция падает с RecursionError на реальных данных (например, при обходе очень длинного связного списка или глубокого дерева), первое, что стоит попробовать, — переписать её в итеративный вариант с явным стеком (обычным списком): логика остаётся той же самой, просто push/pop делаются руками, а не через вызовы функций.

💡 collections.deque(maxlen=k) — готовое решение для скользящего окна фиксированного размера: при добавлении нового элемента после заполнения окна самый старый автоматически вытесняется с противоположного конца, без ручного контроля размера.

💡 Перед тем как писать реализацию очереди на массиве с нуля, задай себе вопрос: действительно ли нужен именно массив (например, ради компактности в памяти и контроля над структурой), или подойдёт готовая структура языка — в подавляющем большинстве практических задач второй вариант и быстрее в разработке, и корректнее с первого раза.

Стек и очередь — самые компактные из всех структур данных курса: у каждой всего по паре-тройке операций, и каждая работает за строго постоянное время. Но именно эта простота делает их вездесущими: без стека не существовало бы ни рекурсии, ни обратного распространения ошибки, на котором держится обучение любой современной нейросети; без очереди не было бы ни справедливого планирования задач, ни обхода в ширину, на котором строится поиск кратчайших связей в графах знаний. Дальше в курсе эти две структуры будут появляться снова и снова — иногда явно, как в алгоритмах обхода графов, а иногда незаметно, спрятанные внутри чужого кода, который ты теперь умеешь узнавать. Следующий урок — связные списки — разберёт подробнее ту структуру, на которой чаще всего строятся эффективные реализации и стека, и очереди.