re:re:actable
Урок 043 минуты чтения

Что такое 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 лучше head index.
  • Deque работает с двумя концами.
  • Sliding window иногда использует deque.

Документация

Wikipedia: Queue, Wikipedia: Double-ended queue.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам