Стек и очередь
Модуль 5.


Введение
Вы уже знакомы с базовыми структурами данных: массивы, строки, связные списки, HashMap и HashSet. Все они отлично подходят для хранения и быстрого доступа к данным. Но что если нам нужен особый порядок доступа к элементам?
Пришло время познакомиться с двумя линейными структурами, которые определяют порядок доступа к элементам:

  • Стек — LIFO (Last In, First Out)
  • Очередь — FIFO (First In, First Out)
Эти структуры кажутся простыми, но критически важны для:
  • Управления историей (отмена действий, история браузера)
  • Управления памятью (вызовы функций)
  • Обработки задач в порядке поступления
  • Поиска в глубину и ширину (DFS/BFS) — критически важные алгоритмы для обхода деревьев и графов.
Мы рассмотрим базовые операции и ключевые паттерны использования стека и очереди.
Пример задачи: история браузера
Представьте, что вы используете веб-браузер и:
  1. Открываете сайт google.com
  2. Переходите на youtube.com
  3. Переходите на leetcode.com
  4. Нажимаете кнопку «Назад»
  5. Опять нажимаете кнопку «Назад»
  6. Нажимаете кнопку «Вперёд»
Как браузер хранит эту историю? Как он знает, куда вернуться? Ответ — стек.
Что такое стек
Стек — линейная структура данных, которая следует принципу LIFO (Last In, First Out) — последний зашёл, первым вышел.
Ключевая идея: вы можете добавлять и удалять элементы только с одного конца — вершины стека (top).

Где используется:
  • Проверка вложенности — сбалансированные скобки, XML/JSON валидация
  • Отмена действий — undo/redo в редакторах, история браузера
  • Обратная польская запись — калькуляторы, вычисление выражений
  • Поиск в глубину (DFS) — обход деревьев и графов
  • Call Stack — управление вызовами функций в программах
  • Backtracking — поиск с возвратом (генерация перестановок, sudoku)
Операции со стеком:
  • Добавление элемента: push
  • Извлечение элемента: pop
  • Просмотр вершины без удаления: peek
Для лучшего понимания можно представить себе стопку тарелок. Обычно мы кладем новую тарелку наверх и ее же достаем первой в случае необходимости. Это и есть принцип «последний зашёл, первым вышел».
Иллюстрация 1: Стек как стопка тарелок
        Топ (top)
           ↑
        ┌───┐
        │ 5 │ ← добавляем/удаляем только отсюда
        ├───┤
        │ 4 │
        ├───┤
        │ 3 │
        ├───┤
        │ 2 │
        ├───┤
        │ 1 │
        └───┘
       Дно (bottom)

Операции:
push(6): [1, 2, 3, 4, 5, 6]
peek():   возвращает 6 (не удаляет)
pop():    удаляет 6, возвращает 6
isEmpty(): false
Иллюстрация 2: История браузера как стек
История посещений (стек):

Шаг 1: google.com
Стек: [google.com]

Шаг 2: youtube.com
Стек: [google.com, youtube.com]

Шаг 3: leetcode.com
Стек: [google.com, youtube.com, leetcode.com]
                                    ↑
                            последний элемент (top)

Шаг 4: кнопка "Назад"
Удаляем leetcode.com, возвращаем youtube.com
Стек: [google.com, youtube.com]

Шаг 5: кнопка "Назад"
Удаляем youtube.com, возвращаем google.com
Стек: [google.com]

Шаг 6: кнопка "Вперёд"
Добавляем youtube.com (из отдельного стека "вперёд")
Стек: [google.com, youtube.com]
Представления стека в коде
В Python, Java и Go стек не является встроенной структурой данных, то есть реализация этой структуры — задача разработчика.
Стек можно реализовать с помощью массива или связного списка.
Реализация с помощью массива:
  • Массив хранит элементы
  • Переменная top указывает на последний элемент
  • При push — увеличиваем top и добавляем элемент
  • При pop — возвращаем элемент по top и уменьшаем top
Иллюстрация 3: Стек на массиве
Массив: [_, _, _, _, _]
         0  1  2  3  4
        ↑
        top = -1 (пустой)

push(1):
Массив: [1, _, _, _, _]
         0  1  2  3  4
         ↑
         top = 0

push(2):
Массив: [1, 2, _, _, _]
         0  1  2  3  4
            ↑
            top = 1

pop():
Возвращаем: 2
Массив: [1, 2, _, _, _]  (значение 2 всё ещё там, но не учитывается)
         0  1  2  3  4
         ↑
         top = 0
# Python
# Создание стека
stack = []

# Добавление (push) — O(1)
stack.append(1)
stack.append(2)
stack.append(3)

# Просмотр вершины (peek) — O(1)
top = stack[-1]  # 3

# Удаление (pop) — O(1)
top = stack.pop()  # 3

# Проверка пустоты — O(1)
len(stack) == 0
// Java
import java.util.*;

// Создание стека
Stack<Integer> stack = new Stack<>();

// Добавление (push) — O(1)
stack.push(1);
stack.push(2);
stack.push(3);

// Просмотр вершины (peek) — O(1)
int top = stack.peek();  // 3

// Удаление (pop) — O(1)
top = stack.pop();  // 3

// Проверка пустоты — O(1)
boolean isEmpty = stack.isEmpty();
// Go
// Создание стека
stack := []int{}

// Добавление (push) — O(1)
stack = append(stack, 1)
stack = append(stack, 2)
stack = append(stack, 3)

// Просмотр вершины (peek) — O(1)
top := stack[len(stack)-1]  // 3

// Удаление (pop) — O(1)
top = stack[len(stack)-1]   // возвращаем последний
stack = stack[:len(stack)-1]  // удаляем последний

// Проверка пустоты — O(1)
isEmpty := len(stack) == 0
Реализация с помощью связного списка:
  • Каждый узел указывает на следующую
  • При push — добавляем узел в начало списка
  • При pop — удаляем первый узел

Обе реализации обеспечивают сложность O(1) для операций извлечения и вставки (push и pop) за счёт константной сложности этих операций в соответствующих структурах.
На Python и Java реализацию через связный список обеспечивает объект типа deque. На Go в стандартной библиотеке нет готового стека на связном списке, но можно использовать container/list (двусвязный список) или slice (массив).
Подробнее о специфике по языкам — в разделе «Специфика по языкам».
Что такое очередь
Очередь — линейная структура данных, которая следует принципу FIFO (First In, First Out) — первым зашёл, первым вышел.

Ключевая идея: вы добавляете элементы с одного конца (rear/back) и удаляете с другого (front/head).

Где используется:
  • Поиск в ширину (BFS) — кратчайший путь в графах, уровневый обход деревьев
  • Обработка задач — очередь печати, планировщик задач ОС
  • Очереди сообщений — Kafka, RabbitMQ, обработка событий
  • Буферизация — stream processing, producer-consumer
  • Кэш LRU — Least Recently Used (с дополнительными структурами)
  • Rate limiting — ограничение частоты запросов
Операции с очередью:
  • Добавление элемента: enqueue
  • Извлечение элемента: dequeue
  • Просмотр вершины без удаления: peek
Для визуализации очереди можно представить себе обычную очередь в магазине. Первый вставший в очередь первым же её покинет (в отличие от стека, когда первым извлекается элемент, добавленный последним).
Иллюстрация 5: Очередь как очередь в магазине
Front (начало)     Rear (конец)
    ↓                   ↓
   [ ]  [ ]  [ ]  [ ]  [ ]
    ↑
  первый

Операции:
enqueue(1): enqueue(2): enqueue(3):
Queue: [1, 2, 3]
        ↑     ↑
        front rear

dequeue():
Удаляет 1, возвращает 1
Queue: [2, 3]
        ↑  ↑
    front  rear

peek():
Возвращает 2 (не удаляет)
Представление очереди в коде
Очередь, как и стек, не представлена в виде встроенной структуры данных, и так же реализуется на базе массива или связного списка.

Реализация на массиве:
  • Массив хранит элементы
  • Переменная front указывает на начало очереди
  • Переменная rear указывает на конец очереди
  • При enqueue — добавляем элемент в rear, увеличиваем rear
  • При dequeue — возвращаем элемент по front, увеличиваем front
Иллюстрация 6: Очередь на массиве
Массив: [_, _, _, _, _]
         0  1  2  3  4
         ↑
         front = rear = 0 (пустой)

enqueue(1):
Массив: [1, _, _, _, _]
         0  1  2  3  4
         ↑
         front = rear = 1

enqueue(2):
Массив: [1, 2, _, _, _]
         0  1  2  3  4
         ↑  ↑
     front  rear = 2

enqueue(3):
Массив: [1, 2, 3, _, _]
         0  1  2  3  4
         ↑     ↑
     front     rear = 3

dequeue():
Возвращаем: 1        
Массив: [2, 3, _, _]
         0  1  2  3  4
         ↑  ↑
     front  rear
Проблема: при извлечении элемента из очереди, реализованной на массиве, мы вынуждены удалять первый элемент массива. Сложность этой операции — O(n). Напомним, что в стеке извлекался последний элемент, для массива сложность такой операции константна. Для эффективной работы очереди также необходима константная сложность.

Решение 1: Перемещение указателя Одно из решений — не удалять элемент из массива, а передвигать указатель front вперед.
Иллюстрация 7: Перемещение указателя front
Массив: [1, 2, 3, _, _]
         0  1  2  3  4
            ↑  ↑
        front  rear
Это даст желаемую константную сложность, однако возникает другая проблема: место до front становится недоступным. Это называется пустым пространством (wasted space).

Решение 2: Кольцевой буфер (Circular Buffer) Другое решение — реализация так называемого кольцевого буфера. Когда rear достигает конца массива, он «заворачивается» в начало, и то же самое для front.
Иллюстрация 8: Кольцевой буфер
Массив (размер 5): [1, 2, 3, 4, 5]
                    0  1  2  3  4
                       ↑        ↑
                      front = 1 rear = 4

enqueue(6):
rear "заворачивается" в начало:
Массив: [6, 2, 3, 4, 5]
         0  1  2  3  4
         ↑  ↑
  rear = 0  front = 1

dequeue():
Удаляем 2, front двигается вперёд:
Массив: [6, 2, 3, 4, 5]
         0  1  2  3  4
         ↑     ↑
  rear = 0     front = 2

Условие переполнения:
Если rear + 1 == front → очередь полная

Условие пустоты:
Если front == rear → очередь пустая
Основная проблема такой реализации — размер очереди должен быть заранее ограничен. Но и этой проблемы можно избежать, если реализовать очередь на связном списке.

Реализация на связном списке:
  • Добавляем в конец списка (enqueue)
  • Удаляем из начала списка (dequeue)
  • O(1) для обеих операций
На Python и Java очередь реализовывается как раз с помощью связного списка, для этого используется объект типа deque. На Go в стандартной библиотеке нет готовой очереди на связном списке, зато можно удобно использовать кольцевой буфер.
Подробнее о специфике по языкам — в разделе «Специфика по языкам».
Сложность операций

Операция

Стек (массив)

Стек (список)

Очередь (массив)

Очередь (список)

push/enqueue

O(1)*

O(1)

O(1)*

O(1)

pop/dequeue

O(1)

O(1)

O(1)**

O(1)

peek/front

O(1)

O(1)

O(1)

O(1)

isEmpty

O(1)

O(1)

O(1)

O(1)


* При заполнении массива — O(n) для расширения ** При кольцевом буфере O(1), при сдвиге элементов O(n) (наивная реализация)
Стек vs Очередь

Свойство

Стек (LIFO)

Очередь (FIFO)

Порядок доступа

Последний зашёл, первым вышел

Первый зашёл, первым вышел

Куда добавляем

Вершина (top)

Конец (rear/back)

Откуда удаляем

Вершина (top)

Начало (front/head)

Использование

Undo/Redo, Call Stack

Print queue, BFS, События

Метафора

Стопка тарелок

Очередь в магазине

Специфика по языкам
Python
Стек: Допустимо использовать обычный list (операции append, pop). Также можно использовать класс deque из стандартной библиотеки collections (операции те же). Обе реализации обеспечивают константную сложность вставки и извлечения элементов.

Очередь: Реализовывается с помощью класса deque из стандартной библиотеки collections (операции append, popleft). Сложность обеих операций — O(1).

НЕ используйте list.pop(0) для очереди — это O(n).
# Неправильно для очереди
queue = [1, 2, 3]
front = queue.pop(0)  # O(n) - сдвиг всех элементов

# Правильно для очереди
from collections import deque
queue = deque([1, 2, 3])
front = queue.popleft()  # O(1)

# Использование deque для стека
stack = deque()
stack.append(1)  # O(1)
stack.pop()      # O(1)
Документация класса deque: https://docs.python.org/3/library/collections.html#collections.deque
Java: Stack, LinkedList, ArrayDeque
Стек:
  • Stack<Integer> — старый класс, не рекомендуется к использованию (синхронизирован, медленнее)
  • Deque<Integer> stack = new ArrayDeque<>() — рекомендуемый вариант, реализация через массив
  • Deque<Integer> stack = new LinkedList<>() — альтернатива, реализация через связный список

Очередь:
  • Queue<Integer> queue = new LinkedList<>() — классический вариант
  • Queue<Integer> queue = new ArrayDeque<>() — более эффективный (реализация через массив с кольцевым буфером, O(1) для операций)
  • Deque<Integer> queue = new ArrayDeque<>() — Deque также может использоваться как очередь
// Стек (рекомендуется)
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.pop();

// Очередь (рекомендуется)
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.poll();
Go: slice и ring buffer
Стек: Реализуется через обычный slice (append, срез). Это обеспечивает сложность O(1) для push/pop.

Очередь: Обычный slice дает O(1) для enqueue, O(n) для dequeue. Для O(1) dequeue нужен ring buffer(кольцевой буфер) или связный список. В стандартной библиотеке Go есть container/ring для кольцевого буфера.
// Очередь с ring buffer
import "container/ring"

// Создаём кольцевой буфер размером 5
rb := ring.New(5)

// Добавляем элементы
rb.Value = 1
rb = rb.Next()
rb.Value = 2
rb = rb.Next()

// Удаляем элементы
rb = rb.Prev()
value := rb.Value  // 2

// Пример использования стека в Go
stack := []int{}
stack = append(stack, 1)
stack = append(stack, 2)
top := stack[len(stack)-1]   // 2
stack = stack[:len(stack)-1]  // удаляем последний
Go: slice и ring buffer
Стек: Реализуется через обычный slice (append, срез). Это обеспечивает сложность O(1) для push/pop.

Очередь: Обычный slice дает O(1) для enqueue, O(n) для dequeue. Для O(1) dequeue нужен ring buffer(кольцевой буфер) или связный список. В стандартной библиотеке Go есть container/ring для кольцевого буфера.
В стандартной библиотеке Go нет готового deque (как в Python или Java). Для реализации дека можно использовать:

  • container/ring — кольцевой буфер
  • container/list — двусвязный список
  • Собственную реализацию на основе slice с двумя указателями
Типичные задачи на стек
1. Проверка вложенности
Задача: Проверить, сбалансированы ли скобки в строке.

Условие: Строка сбалансирована, если:
  • Каждая открывающая скобка имеет соответствующую закрывающую
  • Скобки закрыты в правильном порядке
  • Виды скобок: (), [], {}
Алгоритм:
  1. Создаём пустой стек
  2. Проходим по строке:
  • Если открывающая скобка — добавляем в стек
  • Если закрывающая — проверяем, что верх стека — соответствующая открывающая
3. В конце стек должен быть пустым

Пример:
Вход: "({[]})"

'(' → стек: ['(']
'{' → стек: ['(', '{']
'[' → стек: ['(', '{', '[']
']' → '[' соответствует ']' → стек: ['(', '{']
'}' → '{' соответствует '}' → стек: ['(']
')' → '(' соответствует ')' → стек: []

Выход: true (сбалансированы)
Вход: "({[)}"

'(' → стек: ['(']
'{' → стек: ['(', '{']
'[' → стек: ['(', '{', '[']
')' → '[' НЕ соответствует ')' → false

Выход: false (несбалансированы)
2. Отмена действий (Undo/Redo)
Задача: Реализовать отмену и повтор действий в редакторе.

Алгоритм:
  1. Создаём два стека: undo_stack и redo_stack
  2. При каждом действии — сохраняем состояние в undo_stack
  3. При "Отмена" — перемещаем из undo_stack в redo_stack
  4. При "Повтор" — перемещаем из redo_stack в undo_stack

Пример:
Текст: ""
action("add 'Hello'") → undo_stack: ["Hello"], redo_stack: []
Текст: "Hello"

action("add ' World'") → undo_stack: ["Hello", "Hello World"], redo_stack: []
Текст: "Hello World"

undo() → redo_stack: ["Hello World"], undo_stack: ["Hello"]
Текст: "Hello"

redo() → undo_stack: ["Hello", "Hello World"], redo_stack: []
Текст: "Hello World"
3. Обратная польская запись (калькулятор)
Задача: Вычислить значение выражения в обратной польской записи.

Что такое обратная польская запись (RPN):
  • Форма записи математических выражений, где оператор идёт после операндов
  • Также называется постфиксной записью
  • Не требует скобок для определения порядка операций
  • Названа в честь польского логика Яна Лукасевича
Примеры RPN:
  • 2 1 + вместо (2 + 1) или 2 + 1
  • 2 1 + 3 * вместо (2 + 1) * 3
  • 3 4 + 2 * вместо (3 + 4) * 2
Почему RPN удобна для вычислений:
  • Не нужно хранить скобки
  • Линейный алгоритм с одним стеком
  • Используется в некоторых калькуляторах и компиляторах

Алгоритм:
  1. Создаём пустой стек
  2. Проходим по токенам:
  • Если число — добавляем в стек
  • Если операция — берём два числа из стека, вычисляем, результат добавляем в стек
3. В стеке остаётся результат

Пример:
Вход: ["2", "1", "+", "3", "*"]

"2" → стек: [2]
"1" → стек: [2, 1]
"+" → 2 + 1 = 3 → стек: [3]
"3" → стек: [3, 3]
"*" → 3 * 3 = 9 → стек: [9]

Выход: 9
4. Поиск в глубину (DFS)
Задача: Обойти граф или дерево в глубину, найти путь или проверить достижимость.

Что такое DFS:
  • Обход структуры данных вглубь до упора, затем возврат и ветвление
  • Использует стек для хранения пути и возврата
  • Применяется в деревьях, графах, лабиринтах
Алгоритм:
  1. Создаём стек (или используем рекурсию)
  2. Добавляем стартовую вершину в стек
  3. Пока стек не пуст:
  • Берём вершину из стека
  • Если не посещена — помечаем как посещённую
  • Добавляем всех непосещённых соседей в стек
4. Можно использовать для поиска пути между вершинами

Пример:
Граф:
    1
   / \
  2   3
 / \   \
4   5   6

DFS от 1:

Шаг 1: стек = [1], посещённые = {1}
Шаг 2: стек = [2, 3], посещённые = {1, 2}
Шаг 3: стек = [4, 5, 3], посещённые = {1, 2, 4}
Шаг 4: 4 не имеет соседей, возвращаемся к 5
Шаг 5: стек = [5, 3], посещённые = {1, 2, 4, 5}
... и так далее
Примечание: DFS также часто реализуется через рекурсию (где стек — call stack). Подробнее о графах — в модуле 11−12.
Типичные задачи на очередь
5. Поиск в ширину (BFS)
Задача: Найти кратчайший путь в графе.

Алгоритм:
  1. Создаём пустую очередь
  2. Добавляем стартовую вершину в очередь
  3. Пока очередь не пуста:
  • Берём вершину из очереди
  • Добавляем всех соседей в очередь (если не были посещены)
4. Когда достигаем целевой вершины — путь найден

Пример:
Граф:
    1
   / \
  2   3
 / \   \
4   5   6

BFS от 1 до 6:

Шаг 1: очередь = [1]
Шаг 2: очередь = [2, 3]  (соседи 1)
Шаг 3: очередь = [3, 4, 5]  (соседи 2)
Шаг 4: очередь = [4, 5, 6]  (соседи 3)
Шаг 5: нашли 6! Путь: 1 → 3 → 6
Примечание: подробнее о графах мы поговорим в модуле 11.
6. Обработка задач в порядке поступления
Задача: Обработать задачи в порядке их поступления.

Алгоритм:
  1. Создаём пустую очередь
  2. При поступлении задачи — добавляем в очередь
  3. При освобождении работника — берём задачу из очереди
  4. Обрабатываем задачу

Пример:
Время 0: поступает задача A
Время 1: поступает задача B
Время 2: поступает задача C
Время 3: работник свободен

Очередь: [A, B, C]

Шаг 1: работник берёт A → очередь: [B, C]
Шаг 2: работник завершает A, берёт B → очередь: [C]
Шаг 3: работник завершает B, берёт C → очередь: []
Примеры в реальных системах
Стек

1. Программирование:
  • Call Stack — отслеживание вызовов функций
  • Undo/Redo в текстовых редакторах (VS Code, Sublime Text)
  • История браузера (Chrome, Firefox)
2. Алгоритмы:
  • Проверка сбалансированных скобок (парсинг кода)
  • Обратная польская запись (калькуляторы)
  • Backtracking (поиск с возвратом)
  • DFS (поиск в глубину в графах)
3. Компиляторы:
  • Парсинг выражений
  • Проверка синтаксиса
  • Генерация AST (абстрактное синтаксическое дерево)
4. Инструменты:
  • Git (undo/redo коммитов)
  • Photoshop (история слоёв)

Очередь

1. Системное программирование:
  • Print queue — очередь печати в ОС
  • Task queue — планировщик задач
  • Message queue — очереди сообщений (Kafka, RabbitMQ, AWS SQS)
2. Алгоритмы:
  • BFS (поиск в ширину) — поиск кратчайшего пути
  • Уровневый обход деревьев
  • Кэш LRU (Least Recently Used)
3. Веб-серверы:
  • Обработка HTTP-запросов
  • Пул соединений к базе данных
  • Очереди задач (Celery, Sidekiq)
4. Микросервисы:
  • Асинхронная обработка событий
  • Rate limiting
  • Circuit breaker

Конкретные примеры

PostgreSQL:
  • Очереди WAL (Write Ahead Log) для журналирования транзакций
  • Process queue для асинхронных задач
Kafka:
  • Message queue — распределённая очередь сообщений
  • Producer/consumer pattern — очередь для обработки данных
Redis:
  • List как очередь (LPUSH, RPOP)
  • Pub/Sub — очередь сообщений
AWS:
  • SQS (Simple Queue Service) — управляемая очередь сообщений
  • Lambda — очередь для обработки событий
Prometheus:
  • Scrape queue — очередь для сбора метрик
Заключение
В этом модуле мы разобрали стек и очередь — линейные структуры данных, которые определяют порядок доступа к элементам.

Мы узнали:

1. Стек (LIFO) — последний зашёл, первым вышел
Call Stack, Undo/Redo, Проверка скобок
О(1) для push/pop/peek

2. Очередь (FIFO) — первый зашёл, первым вышел
Print queue, BFS, Системы событий
О(1) для enqueue/dequeue/peek (при кольцевом буфере)

3. Реализация — массив vs связный список

4. Специфика по языкам — Python (deque), Java (ArrayDeque), Go (ring buffer)

5. Паттерны — проверка скобок, undo/redo, обратная польская запись, BFS, обработка задач

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