Очередь
TL;DR
Очередь (queue) — линейная структура данных с порядком доступа FIFO (first in, first out): элементы добавляются только в хвост, а удаляются только из головы. Основные операции enqueue (поставить в хвост), dequeue (забрать из головы), front/peek (посмотреть голову) и empty выполняются за [math]\displaystyle{ O(1) }[/math]. Наивная реализация на массиве даёт dequeue за [math]\displaystyle{ O(n) }[/math] из-за сдвига элементов, поэтому на практике применяют кольцевой буфер (индексы заворачиваются по модулю ёмкости), связный список или два стека (амортизированно [math]\displaystyle{ O(1) }[/math]). Очередь — рабочий инструмент BFS, планирования процессов, буферов ввода-вывода и очередей сообщений. Её ограничение: доступ только к двум концам, к середине обратиться нельзя.
| Свойство | Значение |
|---|---|
| Класс | Линейная структура данных; абстрактный тип «первым пришёл — первым вышел» |
| Порядок доступа | FIFO (first in, first out) |
| Операции | enqueue, dequeue, front/peek, empty, size
|
| Сложность | все операции [math]\displaystyle{ O(1) }[/math] (наивный массив: dequeue — [math]\displaystyle{ O(n) }[/math]; два стека — амортизированно [math]\displaystyle{ O(1) }[/math])
|
| Память | [math]\displaystyle{ O(n) }[/math] (кольцевой буфер — ровно [math]\displaystyle{ O(m) }[/math] для фиксированной ёмкости [math]\displaystyle{ m }[/math]) |
| Реализации | кольцевой буфер (динамический массив), связный список, два стека, std::queue, std::deque
|
| Доступ | только к голове и хвосту (нет произвольного доступа) |
| Упорядоченность | по времени поступления; стабильность FIFO |
| Родственники | стек (LIFO), deque (оба конца), очередь с приоритетом (по ключу) |
| Где встречается | BFS, планировщики ОС, буферы I/O, очереди сообщений, producer-consumer, спулер печати |
Определения
Очередь — коллекция элементов, в которой добавление происходит с одного конца, называемого хвостом (tail, back, rear), а удаление — с другого конца, называемого головой (head, front). Элемент, добавленный раньше, извлекается раньше (FIFO).
Операции:
enqueue(x)/push(x)— поставить [math]\displaystyle{ x }[/math] в хвост;dequeue()/pop()— забрать и вернуть элемент из головы;front()/peek()— посмотреть голову, не удаляя;empty()/size()— пуста ли очередь и сколько в ней элементов.
Инвариант. Элементы упорядочены по времени добавления. Удаляется всегда самый ранний добавленный элемент. Очередь либо пуста, либо имеет ровно одну голову и один хвост.
Кольцевой буфер (circular buffer, ring buffer) — очередь фиксированной ёмкости [math]\displaystyle{ m }[/math], хранимая в массиве buf[0..m−1]. Позиция головы задаётся индексом head, хвоста — парой count (число элементов) и формулой tail = (head + count) mod m. Когда индекс доходит до [math]\displaystyle{ m-1 }[/math], следующий шаг переводит его в [math]\displaystyle{ 0 }[/math] — «по кругу».
Ограниченная очередь (bounded queue) — очередь с фиксированной ёмкостью; при заполнении enqueue либо отклоняет элемент, либо блокирует поток-производитель. Неограниченная очередь (unbounded) растёт динамически.
Deque (double-ended queue) — обобщение: добавление и удаление разрешены с обоих концов (push_front, push_back, pop_front, pop_back), все за [math]\displaystyle{ O(1) }[/math]. Стек и очередь — частные случаи deque.
Блокирующая очередь (blocking queue) — очередь с синхронизацией: dequeue на пустой очереди усыпляет поток, enqueue в полную — блокирует; другой поток будит ждущего. Основа схемы производитель-потребитель (producer-consumer).
Обозначения: [math]\displaystyle{ n }[/math] — текущее число элементов; [math]\displaystyle{ m }[/math] — ёмкость кольцевого буфера; [math]\displaystyle{ \log }[/math] — по двоичному основанию (в этой статье некому сокращать).
Мотивация и интуиция
Главное требование — честный порядок поступления: тот, кто пришёл раньше, должен быть обслужен раньше. Так работают очереди в банке, буферы приёма пакетов и планировщики задач. Если бы новые элементы обслуживались первыми (как в стеке), старые «голодали» бы неограниченно.
Наивная реализация на массиве хранит элементы подряд и при dequeue сдвигает все влево:
dequeue: вернуть A[0]; сдвинуть A[1..n−1] на позицию влево; n ← n − 1
Сдвиг стоит [math]\displaystyle{ O(n) }[/math]; на [math]\displaystyle{ n }[/math] операциях dequeue суммарно [math]\displaystyle{ O(n^2) }[/math]. Для потока из миллиона сообщений это неприемлемо. Две идеи устраняют сдвиг:
- Кольцевой буфер — держать индексы головы и хвоста и двигать их по модулю ёмкости. Освободившееся место в начале массива используется снова, сдвигать элементы не нужно.
- Связный список — хранить голову и хвост как указатели:
dequeueотсоединяет головной узел,enqueueпривязывает новый к хвосту, обе операции — [math]\displaystyle{ O(1) }[/math].
Обеспечивая [math]\displaystyle{ O(1) }[/math] на операцию, очередь становится строительным блоком для BFS (обход слоями), буферов фиксированного размера и конвейеров обработки.
Ключевая идея в одном абзаце: очередь — это отрезок последовательности, из которого читают слева, а дописывают справа; кольцевой буфер делает этот отрезок замкнутым в кольцо, чтобы не тратить память и время на сдвиг (см. рис. 1).
Устройство
Очередь как абстрактный тип данных хранит последовательность и две позиции — голову и хвост. Внешне это «труба»: с одного конца втекает, с другого вытекает, порядок сохраняется (см. рис. 1).
В массивной реализации различают два подхода:
- Линейный массив со сдвигом. Хвост — конец массива, голова — начало. Просто, но
dequeueтребует сдвига за [math]\displaystyle{ O(n) }[/math]. - Кольцевой буфер. Массив фиксированной ёмкости [math]\displaystyle{ m }[/math];
headиcountзадают положение головы и число занятых ячеек. Хвост вычисляется как(head + count) mod m, а занятые ячейки могут «разрываться» через границу массива — часть в конце, часть в начале (см. рис. 2).
count отличает «полна» от «пуста», когда head = tail.Связный список хранит элементы в узлах {key, next}, а очередь — пару указателей head (первый узел) и tail (последний). В отличие от кольцевого буфера, список не имеет фиксированной ёмкости и не требует копирования при росте, но платит за узел накладными расходами и хуже ложится на кэш (разрозненные адреса).
Операции и алгоритмы
Операция: Enqueue (в кольцевом буфере)
Идея. Положить элемент в первую свободную ячейку после хвоста, сдвинув указатель хвоста по кругу.
Пошаговое описание:
- Если очередь полна (
count = m) — сообщить об ошибке (или отклонить/заблокировать). - Вычислить позицию хвоста:
tail ← (head + count) mod m. - Записать
buf[tail] ← x. - Увеличить
countна 1.
Инвариант. count элементов лежат в ячейках head, (head+1) mod m, …, (head+count−1) mod m. Все прочие ячейки свободны; 0 ≤ count ≤ m.
Операция Enqueue(Q, x)
Вход: Q — кольцевой буфер с массивом buf[0..m−1], индексами head, count; x — элемент
Выход: элемент добавлен в хвост; false, если очередь полна
Инвариант: элементы занимают ячейки (head + i) mod m для i = 0..count−1
Сложность: O(1) времени, O(1) памяти
1 if count = m
2 return false # нет места
3 tail ← (head + count) mod m
4 buf[tail] ← x
5 count ← count + 1
6 return true
Разбор. Пусть [math]\displaystyle{ m = 3 }[/math], head = 0, count = 2, buf = [A, B, _]. Тогда tail = (0+2) mod 3 = 2, после enqueue(C) имеем buf = [A, B, C], count = 3 — очередь полна.
Сложность. [math]\displaystyle{ O(1) }[/math]: не более одной записи и одной операции сравнения.
Крайние случаи. Полная очередь — count = m; добавление отклоняется. Если [math]\displaystyle{ m = 0 }[/math] (ёмкость нулевая), очередь всегда полна, но формула mod 0 некорректна — ёмкость должна быть [math]\displaystyle{ \ge 1 }[/math]. Для неограниченной очереди при count = m массив удваивают и переносят элементы в порядке очереди (амортизированно [math]\displaystyle{ O(1) }[/math]).
См. рис. 1 и рис. 2.
Операция: Dequeue (в кольцевом буфере)
Идея. Вернуть головной элемент и сдвинуть голову на одну ячейку вправо по кругу; освободившаяся ячейка будет переиспользована будущими enqueue.
Пошаговое описание:
- Если очередь пуста (
count = 0) — сообщить об ошибке (или отклонить/заблокировать). - Запомнить
x ← buf[head]. - Сдвинуть голову по кругу:
head ← (head + 1) mod m. - Уменьшить
countна 1. - Вернуть
x.
Инвариант. Тот же; после операции «голова» — следующий по времени элемент; число элементов уменьшилось ровно на 1.
Операция Dequeue(Q)
Вход: Q — кольцевой буфер (buf, head, count, m)
Выход: элемент из головы; false, если очередь пуста
Инвариант: элементы занимают count ячеек, начиная с head
Сложность: O(1) времени, O(1) памяти
1 if count = 0
2 return false # очередь пуста
3 x ← buf[head]
4 head ← (head + 1) mod m
5 count ← count − 1
6 return x
Операция Front(Q)
1 if count = 0
2 error "очередь пуста"
3 return buf[head] # без удаления
Разбор. При buf = [A, B, C], head = 0, count = 3 после dequeue вернётся A, head станет 1, count — 2. Ещё один dequeue вернёт B; при enqueue(D) хвост пойдёт на позицию (1+2) mod 3 = 0 — массив замкнётся в кольцо.
Крайние случаи. Пустая очередь — count = 0. Обращение к front/dequeue на пустой очереди — типичная ошибка (underflow). Загруженность (load factor) близка к 1 — очередь работает, но любая вставка отклоняется; обычно держат буфер с запасом или растят его.
См. рис. 2.
Операция: Enqueue и Dequeue на двух стеках
Идея. Держать два стека: in — для входящих, out — для исходящих. Элемент кладут в in; когда нужно извлечь, а out пуст, все элементы перекладывают из in в out — порядок разворачивается и снова становится FIFO (см. рис. 3).
Пошаговое описание dequeue:
- Если
outпуст, перекладывать элементы изinвout, покаinне опустеет (каждый элемент снимается с вершиныinи кладётся на вершинуout). - Снять верхушку
out— это самый ранний пришедший элемент. - Если оба стека пусты — очередь пуста.
Инвариант. Все элементы лежат в in и out; в out они расположены так, что вершина — самый ранний из «выталкиваемых», а в in — в порядке добавления.
Операция TwoStack-Dequeue
Вход: стеки in, out
Выход: элемент из головы; false, если оба пусты
Инвариант: последовательность = (out сверху вниз реверс) ++ (in снизу вверх)
Сложность: амортизированно O(1); худший случай одного dequeue — O(n)
1 if empty(out)
2 while not empty(in) # перевернуть in в out
3 push(out, pop(in))
4 if empty(out)
5 return false # очередь пуста
6 return pop(out)
Операция TwoStack-Enqueue(x)
1 push(in, x)
Разбор. enqueue(1), enqueue(2), enqueue(3) → in = [1, 2, 3] (снизу вверх). При dequeue переносим: out = [3, 2, 1] сверху вниз, снимаем 1. Затем enqueue(4) кладёт 4 в in. Следующие dequeue снимают 2, 3, не трогая in, пока out не опустеет; тогда 4 переедет и будет извлечён. Порядок — 1, 2, 3, 4, как и требует FIFO.
Сложность. Каждый элемент переносится из in в out не более одного раза за всю жизнь, поэтому суммарно [math]\displaystyle{ 2n }[/math] операций push/pop на [math]\displaystyle{ n }[/math] элементов — амортизированно [math]\displaystyle{ O(1) }[/math] на операцию. Отдельный вызов dequeue в момент опустошения out стоит [math]\displaystyle{ O(n) }[/math] (худший случай).
Крайние случаи. Первый dequeue всегда дорог. Пустая очередь — оба стека пусты.
См. рис. 3.
in → out разворачивает порядок: стек дважды даёт FIFO.Пример применения: обход в ширину (BFS)
Идея. Очередь хранит «фронт волны»: сначала все вершины на расстоянии 0, затем 1, затем 2 и так далее. Извлекая вершину из головы и добавляя её непосещённых соседей в хвост, алгоритм послойно обходит граф (см. рис. 4).
Пошаговое описание:
- Пометить старт
sпосещённым,dist[s] ← 0,enqueue(s). - Пока очередь не пуста:
u ← dequeue(). - Для каждого соседа
vвершиныu: еслиvещё не посещён, пометить,dist[v] ← dist[u]+1,enqueue(v).
Инвариант. Вершины извлекаются в неубывающем порядке dist. Каждая вершина попадает в очередь ровно один раз — в момент, когда впервые обнаружена.
Алгоритм BFS(G, s)
Вход: G = (V, E) — граф; s ∈ V — стартовая вершина
Выход: dist[v] — число рёбер на кратчайшем пути s → v (−1, если недостижима)
Инвариант: очередь хранит границу фронта; порядок извлечения не убывает по dist
Сложность: O(V + E) времени, O(V) памяти
1 for each v ∈ V
2 dist[v] ← −1
3 dist[s] ← 0
4 Q ← пустая очередь
5 enqueue(Q, s)
6 while not empty(Q)
7 u ← dequeue(Q)
8 for each v ∈ Adj[u]
9 if dist[v] = −1
10 dist[v] ← dist[u] + 1
11 enqueue(Q, v)
12 return dist
Разбор. Граф с рёбрами [math]\displaystyle{ (0,1), (0,2), (1,3), (2,3) }[/math]; старт 0. Очередь: [0] → извлекаем 0, добавляем 1 и 2 → [1,2] → извлекаем 1, добавляем 3 → [2,3] → извлекаем 2, 3 уже в очереди → [3] → извлекаем 3. Расстояния: 0→0, 1→1, 2→1, 3→2.
Сложность. Каждая вершина и каждое ребро обрабатываются один раз: [math]\displaystyle{ O(V + E) }[/math] времени, [math]\displaystyle{ O(V) }[/math] памяти под очередь и массив расстояний.
Крайние случаи. Несвязный граф — недостижимые вершины остаются −1. Ориентированное ребро не создаёт обратного. Замена очереди на стек превращает алгоритм в DFS.
См. рис. 4; сам обход подробнее разбирается в статье Графы (план).
[0] → [1,2] → [2,3] → [3] → [].Сводная таблица сложности
| Операция | Кольцевой буфер | Связный список | Два стека | Наивный массив |
|---|---|---|---|---|
enqueue |
[math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(1) }[/math] (амортизированно при росте) |
dequeue |
[math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(1) }[/math] | амортизированно [math]\displaystyle{ O(1) }[/math] (худший [math]\displaystyle{ O(n) }[/math]) | [math]\displaystyle{ O(n) }[/math] |
front / peek |
[math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(1) }[/math] |
empty / size |
[math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(1) }[/math] | [math]\displaystyle{ O(1) }[/math] |
| Память | [math]\displaystyle{ O(m) }[/math] (ровно ёмкость) | [math]\displaystyle{ O(n) }[/math] + указатели | [math]\displaystyle{ O(n) }[/math] | [math]\displaystyle{ O(n) }[/math] |
| Устойчивость к скачкам | ограничена ёмкостью | растёт динамически | растёт динамически | растёт динамически |
Оговорки. Худший случай относится к отдельному вызову dequeue на двух стеках; амортизированно по последовательности операций он [math]\displaystyle{ O(1) }[/math]. Рандомизация не нужна — все оценки детерминированы. Кольцевой буфер при фиксированной ёмкости не расширяется: переполнение — вопрос политики (отклонить, перезаписать старое, заблокировать). См. рис. 5.
dequeue.Трассировка примера
Возьмём кольцевой буфер ёмкости [math]\displaystyle{ m = 3 }[/math], начальные head = 0, count = 0.
| Шаг | Действие | buf[0..2] |
head |
count |
Комментарий |
|---|---|---|---|---|---|
| 1 | enqueue(A) |
A _ _ |
0 | 1 | tail = 0 |
| 2 | enqueue(B) |
A B _ |
0 | 2 | tail = 1 |
| 3 | enqueue(C) |
A B C |
0 | 3 | tail = 2, очередь полна |
| 4 | enqueue(D) |
A B C |
0 | 3 | отказ: count = m
|
| 5 | dequeue() → A |
A B C |
1 | 2 | сдвиг головы |
| 6 | enqueue(D) |
D B C |
1 | 3 | tail = (1+2) mod 3 = 0, заворот |
| 7 | dequeue() → B |
D B C |
2 | 2 | голова = 2 |
| 8 | dequeue() → C |
D C C |
0 | 1 | голова = (2+1) mod 3 = 0 |
| 9 | dequeue() → D |
D C C |
1 | 0 | очередь пуста |
Обратите внимание на шаг 6: хвост «перескочил» с позиции 2 на позицию 0, хотя в массиве физически остались старые байты. Значимы только count ячеек, начиная с head; остальное — мусор, который будет перезаписан.
Корректность и оценка сложности
Корректность кольцевого буфера
Докажем инвариант индукцией по числу операций.
Инвариант. После любой последовательности операций при count = k элементы очереди лежат ровно в ячейках (head + i) mod m для i = 0..k−1, в порядке поступления.
База. Пустое состояние: count = 0, инвариант выполняется тривиально.
Переход enqueue. По индукции старые элементы занимают k ячеек от head. Новый элемент пишется в (head + k) mod m — первая свободная ячейка; count становится k+1. Порядок сохранён: новый элемент в конце. Инвариант выполняется.
Переход dequeue. Головной элемент — (head + 0) mod m, то есть самый ранний. После его удаления head ← (head+1) mod m, count ← k−1; оставшиеся k−1 элементов лежат в (head'+i) mod m. Инвариант выполняется.
Отсюда front() возвращает самый ранний элемент, а dequeue() удаляет именно его, — это и есть FIFO-порядок. При count = 0 очередь пуста, при count = m — полна; состояния различимы, несмотря на возможное head = tail.
Амортизированный анализ двух стеков
Пусть над очередью выполнено [math]\displaystyle{ n }[/math] операций enqueue, а извлечено [math]\displaystyle{ m \le n }[/math] элементов. Каждый элемент кладётся в in ровно один раз и переносится в out не более одного раза; значит, число операций push/pop не превосходит [math]\displaystyle{ 3n }[/math] (один push в in, один pop из in, один push в out на элемент, плюс pop из out на каждый извлечённый). Отсюда суммарная стоимость — [math]\displaystyle{ O(n) }[/math], то есть амортизированно [math]\displaystyle{ O(1) }[/math] на операцию. Это оценка по методу предоплаты: каждый enqueue «платит» вперёд за свой будущий перенос.
Сложность BFS
Каждая вершина входит в очередь не более одного раза (условие dist[v] = −1), поэтому тела цикла while выполняются не более [math]\displaystyle{ V }[/math] раз, а внутренний цикл — суммарно по степеням вершин, то есть [math]\displaystyle{ \sum_v \deg(v) = 2E }[/math] для неориентированного графа (или [math]\displaystyle{ E }[/math] для ориентированного). Итого [math]\displaystyle{ O(V + E) }[/math].
Сравнение с альтернативами
| Структура | Порядок извлечения | Извлечение | Доступ к середине | Когда выбирать |
|---|---|---|---|---|
| Очередь (FIFO) | по времени поступления | [math]\displaystyle{ O(1) }[/math] | нет | честный порядок: BFS, планирование, буферы |
| Стек (LIFO) | последним пришёл — первым вышел | [math]\displaystyle{ O(1) }[/math] | нет | рекурсия, откат, DFS |
| Deque | с любого конца | [math]\displaystyle{ O(1) }[/math] | нет | окно, скользящий максимум, оба конца |
| Двоичная куча | по ключу (min/max) | [math]\displaystyle{ O(\log n) }[/math] | нет | приоритетная очередь, Дейкстра |
| Отсортированный массив | по ключу | [math]\displaystyle{ O(1) }[/math] (первый), [math]\displaystyle{ O(n) }[/math] (вставка) | [math]\displaystyle{ O(\log n) }[/math] | статический набор, редкие вставки |
| Кольцевой буфер (фикс. ёмкость) | FIFO | [math]\displaystyle{ O(1) }[/math] | нет | жёсткое ограничение памяти, потоки данных |
Вердикт: если порядок обслуживания — «кто раньше пришёл», берите очередь. Если важен ключ (приоритет) — Очередь с приоритетом, а не FIFO. Если нужен доступ с обоих концов — deque.
Где применяется
- Обход в ширину (BFS). Кратчайшие пути в невзвешенном графе, «волны» на сетке, компоненты связности — очередь задаёт порядок обхода слоями (
std::queue,collections.deque). Почему очередь: расстояния обрабатываются в неубывающем порядке, что и даёт [math]\displaystyle{ O(V+E) }[/math] (см. CLRS, гл. 22) [1][2].
- Планирование процессов в ОС. Планировщик держит очередь готовых задач и выдаёт процессор по очереди (round-robin), а многоуровневые очереди (MLFQ) добавляют приоритеты. Без FIFO часть процессов голодала бы; квантование времени делает планирование справедливым [3].
- Буферы ввода-вывода. Кольцевой буфер сглаживает разницу скоростей приёмника и устройства: данные из сети, с диска или клавиатуры накапливаются и обрабатываются по мере готовности потребителя. При переполнении буфер отбрасывает данные (сеть) или применяет обратное давление (backpressure) [4].
- Очереди сообщений и брокеры. RabbitMQ, Apache Kafka, ActiveMQ, AMQP-очереди хранят сообщения в порядке поступления, развязывая отправителя и получателя по времени и позволяя повторную доставку. FIFO-семантика — база для гарантий порядка и отказоустойчивости [5].
- Схема производитель-потребитель. Пул рабочих потоков забирает задачи из блокирующей очереди:
enqueueбудит ждущего потребителя,dequeueна пустой очереди усыпляет поток. Так устроены пулы потоков, event loop,java.util.concurrent.BlockingQueue[6].
- Спулер печати и пакетная обработка. Задания печати выполняются в порядке отправки; аналогично работают очереди заданий в CI, фоновой обработке писем и image-пайплайнах.
Обзор четырёх типовых областей — на рис. 6.
Историческая справка
Понятие очереди выросло из теории массового обслуживания: А. К. Эрланг (A. K. Erlang), исследуя телефонные станции в 1900–1910-х, ввёл модели потоков вызовов и дисциплину обслуживания «первым пришёл — первым обслужен» (FIFO/FCFS) ⚠️ требует проверки точных годов. Модель M/M/1 и формула Эрланга — из этой области.
В информатике очередь систематически описана в классических работах: Д. Э. Кнут разбирает стек, очередь и deque в The Art of Computer Programming, т. 1, §2.2.1 [7]. Э. Дейкстра применил стек и очередь в описании трансляции ALGOL 60 (1960–1962) [8]. Абстрактный тип данных «очередь» оформился в 1970-е вместе с теорией типов данных (работа Б. Лискова и А. Шоу, 1970-е) ⚠️ требует проверки точной формулировки.
Кольцевой буфер как структуру для буферов данных популяризировали в системном программировании; блокирующие очереди и мониторы вошли в практику параллельного программирования в 1970-е (Хоар, мониторы, 1974) [9].
Типичные ошибки и подводные камни
- Неоднозначность «полна/пуста». Если хранить только
headиtail, состоянияhead = tailне различимы (пусто или полна). Лечится отдельным счётчикомcountлибо одним пустым слотом (ёмкость буфера — на 1 меньше). underflow/overflow.dequeueна пустой очереди иenqueueв полную — типовые ошибки; защищайтесь проверками или исключениями (std::queue::popна пустой — UB).- Off-by-one в кольце. Забыть
mod mдля хвоста приenqueueили для головы приdequeueприводит к выходу за границу массива или к «залипанию». - Неверный размер кольцевого буфера. Ёмкость [math]\displaystyle{ 0 }[/math] даёт
mod 0; ёмкость должна быть [math]\displaystyle{ \ge 1 }[/math]. - Гонки в параллельной очереди. Несинхронизированный
head/tailмежду потоками ломает инвариант; используйте блокировку, мьютекс с условиями или lock-free-схемы (с обязательным анализом ABA-проблемы). - Ложное совместное использование (false sharing).
headиtailв одной кэш-линии дают лишние инвалидации; помогает выравнивание по 64 байта. - Утечка памяти в очереди на списке. Если
dequeueне освобождает узлы или в deque «мертвые» блоки не отдаются, память растёт неограниченно. - Путаница очереди и deque. Deque поддерживает оба конца; использовать его «как очередь» можно, но интерфейс шире и требует большей аккуратности.
- Переполнение счётчика. В неограниченной очереди на GCC-подобной арифметике бесконечный
forпоsize_tдо нуля — классика; следите за типом счётчика.
Задачи для практики
- Простая очередь. Реализуйте очередь на кольцевом буфере фиксированной ёмкости с операциями
enqueue,dequeue,front,empty,full. Ограничения: все операции [math]\displaystyle{ O(1) }[/math]. Подсказка: хранитеheadиcount, хвост вычисляйте по модулю. Сложность — [math]\displaystyle{ O(1) }[/math].
- Заворот индексов. Подайте последовательность операций, при которой хвост заворачивается через границу массива дважды, и вручную выпишите состояния
head,count, массива. Подсказка: возьмите [math]\displaystyle{ m = 4 }[/math] и чередуйтеenqueue/dequeue.
- Очередь на двух стеках. Реализуйте очередь только через две операции стека и докажите амортизированную оценку [math]\displaystyle{ O(1) }[/math]. Ограничение: нельзя обращаться к элементам по индексу.
- BFS. По невзвешенному графу найдите кратчайшее расстояние от
sдо всех вершин за [math]\displaystyle{ O(V+E) }[/math]. Подсказка: очередь и массивdist, инициализированный−1.
- Слои BFS. Выведите для BFS вершины, сгруппированные по уровню (номеру слоя). Подсказка: обрабатывайте очередь «послойно»: запоминайте длину очереди перед слоем.
- Скользящий максимум. Для массива и окна ширины [math]\displaystyle{ k }[/math] найдите максимум в каждом окне за [math]\displaystyle{ O(n) }[/math]. Подсказка: deque из индексов, поддерживающий убывающий порядок значений.
- Кольцевой буфер с перезаписью. Измените буфер так, чтобы при переполнении новый элемент вытеснял самый старый (используется в телеметрии и логах). Как изменится
dequeue?
- Блокирующая очередь. Реализуйте очередь с
enqueue/dequeue, блокирующими поток при полном/пустом буфере (мьютекс + два условных переменных). Докажите отсутствие взаимной блокировки и проверьте гонки под нагрузкой.
Связанные темы
- Стек — противоположный порядок (LIFO); очередь и стек — два крайних случая deque.
- Очередь на шести стеках — очередь с [math]\displaystyle{ O(1) }[/math] в худшем случае и персистентная очередь.
- Персистентная очередь — хранение всех версий очереди, очереди Окасаки.
- Очередь с приоритетом — извлечение по ключу, а не по времени поступления.
- Двоичная куча — типичная реализация приоритетной очереди.
- Графы — BFS, слои, кратчайшие пути без весов.
- Асимптотическая сложность — обозначения [math]\displaystyle{ O }[/math], [math]\displaystyle{ \Theta }[/math], [math]\displaystyle{ o }[/math].
- Префиксные суммы — подготовка для задач со скользящим окном.
Источники
- Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 10 «Elementary Data Structures» (очередь, стек, deque); гл. 22 «Elementary Graph Algorithms» (BFS).
- Knuth D. E. The Art of Computer Programming. Vol. 1: Fundamental Algorithms. — Addison-Wesley, 3rd ed., 1997. — §2.2.1 «Stacks, Queues, and Deques».
- Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — §1.3 (очереди, приоритетные очереди), §4.1 (BFS).
- Silberschatz A., Galvin P. B., Gagne G. Operating System Concepts. — Wiley, 10th ed., 2018. — главы о планировании процессов и буферизации ввода-вывода.
- Hohpe G., Woolf B. Enterprise Integration Patterns. — Addison-Wesley, 2003. — паттерны обмена сообщениями и очереди.
- Gropp W., Lusk E., Skjellum A. Using MPI. — MIT Press, 2nd ed., 1999. — буферизация и блокирующие/неблокирующие операции.
- Wikipedia: Queue (abstract data type). URL: https://en.wikipedia.org/wiki/Queue_(abstract_data_type).
- Wikipedia: Circular buffer. URL: https://en.wikipedia.org/wiki/Circular_buffer.
- Hoare C. A. R. Monitors: An Operating System Structuring Concept // CACM, 1974.
- MITRE/C++ reference:
std::queue— https://en.cppreference.com/w/cpp/container/queue.