Queue (Очередь)

Queue — линейная структура данных, работающая по принципу FIFO (First In, First Out): первый добавленный элемент извлекается первым. Как очередь в магазине.

Зачем нужно

Очереди управляют порядком обработки задач. Event loop в JavaScript — очередь. Очередь сообщений, очередь печати, BFS (обход графов в ширину), rate limiting — везде очередь.

Где используется

  • Event loop JavaScript (task queue, microtask queue)
  • BFS — обход графов в ширину
  • Очереди сообщений (RabbitMQ, Kafka)
  • Буферизация (потоки данных)
  • Планирование задач (task scheduler)
  • Print queue, download queue

Предпосылки

Принцип FIFO

Enqueue 1: [1]         ← rear (хвост)
Enqueue 2: [1, 2]
Enqueue 3: [1, 2, 3]
Dequeue:   [2, 3] → 1  ← front (голова) — извлекли первый
Dequeue:   [3]    → 2
Peek:      [3]    → 3  ← посмотрели, не извлекая

Операции

Операция Описание Сложность
enqueue(item) Добавить в конец O(1)
dequeue Извлечь из начала O(1)*
peek / front Посмотреть первый O(1)
isEmpty Проверка пустоты O(1)
size Количество элементов O(1)

* O(1) для связного списка, O(n) для наивной реализации на массиве (shift)

Реализация в JavaScript

На основе объекта (O(1) для всех операций)

class Queue {
  #items = {};
  #head = 0;
  #tail = 0;

  enqueue(item) {
    this.#items[this.#tail] = item;
    this.#tail++;
  }

  dequeue {
    if (this.isEmpty) throw new Error('Queue is empty');
    const item = this.#items[this.#head];
    delete this.#items[this.#head];
    this.#head++;
    return item;
  }

  peek {
    if (this.isEmpty) throw new Error('Queue is empty');
    return this.#items[this.#head];
  }

  isEmpty {
    return this.#tail - this.#head === 0;
  }

  size {
    return this.#tail - this.#head;
  }
}

const q = new Queue();
q.enqueue('A');
q.enqueue('B');
q.enqueue('C');
console.log(q.dequeue); // 'A'
console.log(q.peek);    // 'B'
console.log(q.size);    // 2

На основе связного списка

class QueueNode {
  constructor(value) {
    this.value = value;
    this.next() = null;
  }
}

class LinkedQueue {
  #head = null;
  #tail = null;
  #size = 0;

  enqueue(value) {
    const node = new QueueNode(value);
    if (this.#tail) {
      this.#tail.next() = node;
    } else {
      this.#head = node;
    }
    this.#tail = node;
    this.#size++;
  }

  dequeue {
    if (!this.#head) throw new Error('Queue is empty');
    const value = this.#head.value;
    this.#head = this.#head.next();
    if (!this.#head) this.#tail = null;
    this.#size--;
    return value;
  }

  peek {
    if (!this.#head) throw new Error('Queue is empty');
    return this.#head.value;
  }

  isEmpty { return this.#size === 0; }
  size { return this.#size; }
}

Priority Queue (приоритетная очередь)

Элементы извлекаются по приоритету, а не по порядку добавления.

class PriorityQueue {
  #items = ;

  enqueue(value, priority) {
    const element = { value, priority };

    // Найти позицию для вставки (sorted insert)
    let added = false;
    for (let i = 0; i < this.#items.length; i++) {
      if (element.priority < this.#items[i].priority) {
        this.#items.splice(i, 0, element);
        added = true;
        break;
      }
    }

    if (!added) this.#items.push(element);
  }

  dequeue {
    if (this.isEmpty) throw new Error('Queue is empty');
    return this.#items.shift().value;
  }

  peek {
    if (this.isEmpty) throw new Error('Queue is empty');
    return this.#items[0].value;
  }

  isEmpty { return this.#items.length === 0; }
  size { return this.#items.length; }
}

const pq = new PriorityQueue();
pq.enqueue('Низкий', 3);
pq.enqueue('Критичный', 1);
pq.enqueue('Средний', 2);
console.log(pq.dequeue); // 'Критичный' (приоритет 1)
console.log(pq.dequeue); // 'Средний' (приоритет 2)

Практические примеры

BFS — обход графа в ширину

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  const result = ;

  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift(); // dequeue
    result.push(node);

    for (const neighbor of graph[node] || ) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor); // enqueue
      }
    }
  }

  return result;
}

const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: , E: , F: 
};

console.log(bfs(graph, 'A')); // ['A', 'B', 'C', 'D', 'E', 'F']

Планировщик задач

class TaskScheduler {
  #queue = new Queue();
  #running = false;

  add(task) {
    this.#queue.enqueue(task);
    if (!this.#running) this.#run;
  }

  async #run {
    this.#running = true;

    while (!this.#queue.isEmpty) {
      const task = this.#queue.dequeue;
      try {
        await task;
      } catch (err) {
        console.error('Task failed:', err);
      }
    }

    this.#running = false;
  }
}

const scheduler = new TaskScheduler();
scheduler.add(async () => {
  console.log('Задача 1');
  await new Promise(r => setTimeout(r, 100));
});
scheduler.add(async  => console.log('Задача 2'));

JavaScript Event Loop и очереди

┌────────────────────────────────────┐
│           Call Stack               │
│  (стек вызовов — LIFO)            │
└─────────────┬───────────────────���──┘
              │
┌─────────────┴────────���─────────────┐
│         Event Loop                 │
│  Проверяет: стек пуст?            │
│  Да → берёт из очереди            │
└─────────┬────────────┬─────────────┘
          │            │
┌─────────┴───┐  ┌─────┴──────────┐
│ Microtask   │  │ Macrotask      │
│ Queue       │  │ Queue          │
│ (Promise)   │  │ (setTimeout)   │
│ Приоритет!  │  │                │
└─────────────┘  └────────────────┘

console.log('1');

setTimeout( => console.log('2'), 0); // macrotask queue

Promise.resolve.then( => console.log('3')); // microtask queue

console.log('4');

// Вывод: 1, 4, 3, 2
// Microtask queue обрабатывается ПЕРЕД macrotask queue

Частые ошибки

  1. Использовать shift для очереди на массиве. shift — O(n)! Используйте объект или связный список
  2. Путать стек и очередь. Stack — LIFO (стопка), Queue — FIFO (очередь)
  3. Не обрабатывать пустую очередь. dequeue на пустой очереди — ошибка
  4. Игнорировать microtask vs macrotask. Promise callbacks выполняются раньше setTimeout

Практика

  1. Реализуйте Queue на основе двух стеков (push в один, pop из другого)
  2. Реализуйте горячую клавишу последних N действий (circular buffer / ring queue)
  3. Реализуйте BFS для поиска кратчайшего пути в лабиринте

Связанные темы

  • Stack (LIFO — противоположность)
  • Array
  • Linked List (основа для эффективной очереди)
  • Graph (BFS использует очередь)
  • Tree (BFS-обход дерева)

Ресурсы