Queue (Очередь)
Очередь — структура данных по принципу FIFO (First In, First Out): первый добавленный элемент извлекается первым. Основные операции — enqueue (добавить в конец), dequeue (снять с начала), peek (посмотреть первый).
Наивная реализация на массиве (и её проблема)
class SlowQueue<T> {
private items: T[] = [];
enqueue(item: T): void {
this.items.push(item); // O(1)
}
dequeue(): T | undefined {
return this.items.shift(); // ❌ O(n) — сдвигает все элементы
}
}Array.prototype.shift() в JS работает за O(n), потому что после удаления первого элемента все остальные сдвигаются. Для больших объёмов это медленно.
Эффективная реализация (два указателя)
Храним индекс головы и не сдвигаем массив — dequeue становится O(1).
class Queue<T> {
private items: T[] = [];
private head = 0;
enqueue(item: T): void {
this.items.push(item); // O(1)
}
dequeue(): T | undefined {
if (this.head >= this.items.length) return undefined;
const item = this.items[this.head];
this.head++; // O(1) — просто двигаем указатель
// периодически чистим "хвост", чтобы не течь по памяти
if (this.head > 1000 && this.head * 2 >= this.items.length) {
this.items = this.items.slice(this.head);
this.head = 0;
}
return item;
}
peek(): T | undefined {
return this.items[this.head];
}
get size(): number {
return this.items.length - this.head;
}
isEmpty(): boolean {
return this.size === 0;
}
}Разновидности
| Вид | Описание |
|---|---|
| Deque (двусторонняя очередь) | Вставка/удаление с обоих концов; основа для monotonic deque |
| Circular buffer (кольцевой буфер) | Фиксированный размер, голова и хвост «заворачиваются» по модулю |
| Priority Queue | Извлекается не первый, а наиболее приоритетный элемент (см. [[../15-02-05-heap-priority-queue |
Где применяется очередь
- BFS — обход графа/дерева по уровням
- Планировщики задач, очереди сообщений (message queue)
- Буферизация потоков данных
- Rate limiting (скользящее окно запросов)