Что такое queue и deque?
На этой странице
Queue работает по принципу FIFO: first in, first out. Deque позволяет добавлять и удалять элементы с обеих сторон. В алгоритмах очередь нужна для BFS, задач по уровням, simulation и sliding window.
Вопрос
Что такое queue и deque и как реализовать очередь в JavaScript без O(n) на shift?
Queue
Очередь работает как очередь в магазине: кто пришел первым, тот первым и уходит.
enqueue(1), enqueue(2), enqueue(3)
вход -> [3, 2, 1] -> выход
dequeue() вернет 1, потом 2, потом 3Сравните со стеком, где те же три вставки вернут 3, 2, 1.
На массиве без shift:
class Queue<T> {
private items: T[] = []
private head = 0
enqueue(value: T): void {
this.items.push(value)
}
dequeue(): T | undefined {
if (this.head >= this.items.length) return undefined
return this.items[this.head++]
}
get size(): number {
return this.items.length - this.head
}
}Почему не shift?
queue.shift()Для больших массивов может быть O(n), потому что после удаления первого элемента все остальные сдвигаются на одну позицию влево:
[a, b, c, d] shift() -> [b, c, d]
0 1 2 3 0 1 2 индексы всех элементов изменилисьС индексом head мы ничего не сдвигаем, а просто "забываем" элементы левее head. Минус - память под извлеченные элементы освобождается не сразу; для BFS в задачах это не проблема.
Deque
Deque, double-ended queue, поддерживает:
- push back;
- pop back;
- push front;
- pop front.
В JavaScript нет встроенного Deque. Для интервью часто хватает массива с индексами или собственной реализации.
BFS
function bfs(start: string, graph: Map<string, string[]>): string[] {
const result: string[] = []
const visited = new Set([start])
const queue = [start]
let head = 0
while (head < queue.length) {
const node = queue[head++]
result.push(node)
for (const next of graph.get(node) ?? []) {
if (!visited.has(next)) {
visited.add(next)
queue.push(next)
}
}
}
return result
}Что отвечать на собеседовании?
Queue - FIFO-структура, где первым выходит самый старый элемент. Она нужна для BFS, обработки задач по порядку и level-order traversal. В JS для большой очереди лучше не использовать shift, а хранить индекс head. Deque расширяет очередь и позволяет работать с двумя концами.
Что важно помнить: частые ошибки
- Использовать
shift()в BFS на больших данных. - Не отмечать вершину visited при добавлении в очередь.
- Путать stack DFS и queue BFS.
- Не очищать старые элементы при долгой жизни очереди.
- Ожидать встроенный Deque в JS.
Мини-шпаргалка
- Queue = FIFO.
- Stack = LIFO.
- BFS использует queue.
- В JS лучше
headindex. - Deque работает с двумя концами.
- Sliding window иногда использует deque.