Очередь
FIFO: кто пришёл раньше — тот обслуживается раньше. enqueue в конец, dequeue из начала.
1class Queue<T> {2 private items: T[] = []3 4 enqueue(x: T): void {5 this.items.push(x) // в конец6 }7 8 dequeue(): T | undefined {9 return this.items.shift() // из начала10 }11 12 get front(): T | undefined {13 return this.items[0]14 }15}Проблема
Гарантировать справедливый порядок обработки: задачи, события, пакеты. Стек даёт «последним пришёл — первым ушёл» — для очередей нужен ровно противоположный принцип.
Что вы видите
Задачи A–E приходят в тиках и встают в конец. Обработка всегда берёт head — слева. Порядок обработки повторяет порядок прихода, что бы ни творилось сзади.
Как это работает
Очередь — enqueue (в конец) и dequeue (из начала), оба O(1) (на связном списке или кольцевом буфере). Очереди — это планировщики, BFS, буферы событий, очереди сообщений.
Пошаговый разбор
- 01
enqueue
Новый — строго в конец.
- 02
dequeue
Уходит head — он ждёт дольше всех.
- 03
front
Кто следующий — без снятия.
- 04
Справедливость
Порядок выхода = порядок входа.
Complexity и ограничения
O(1) на операцию. На массиве shift — O(n): нужен список или кольцо.
Edge cases
- Пустая очередь
dequeue возвращает пусто — не ошибка, а сигнал.
- Всплеск нагрузки
Очередь растёт — нужен лимит или приоритеты.
- Приоритеты
Куча превращает очередь в приоритетную.
Где встречается в реальности
Буферы событий
Event loop и очереди задач в браузере/Node.
Очереди сообщений
RabbitMQ/Kafka — распределённые FIFO-каналы.
Планировщики
Печать, задачи, шедулеры — все стоят в очереди.
Связанные алгоритмы
«Стек — наглый, очередь — справедливая. В чём разница»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.