Что такое очередь?

Очередь (Queue)

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

Основные операции очереди

// Базовая реализация очереди
class Queue {
  constructor() {
    this.items = [];
  }

  // Добавить элемент в конец очереди
  enqueue(element) {
    this.items.push(element);
  }

  // Удалить и вернуть первый элемент
  dequeue() {
    return this.items.shift();
  }

  // Посмотреть первый элемент (без удаления)
  peek() {
    return this.items[0];
  }

  // Проверить пуста ли очередь
  isEmpty() {
    return this.items.length === 0;
  }

  // Получить размер очереди
  size() {
    return this.items.length;
  }

  // Очистить очередь
  clear() {
    this.items = [];
  }

  // Вывести все элементы
  print() {
    console.log(this.items.toString());
  }
}

// Использование
const queue = new Queue();
queue.enqueue('Задача 1');
queue.enqueue('Задача 2');
queue.enqueue('Задача 3');

console.log(queue.dequeue()); // 'Задача 1'
console.log(queue.peek()); // 'Задача 2'
queue.print(); // 'Задача 2', 'Задача 3'

Визуализация FIFO

                FRONT (деякюеирование)
                        ↓
            ┌───┬───┬───┬───┐
Очередь:   │ 1 │ 2 │ 3 │ 4 │
            └───┴───┴───┴───┘
                              ↑
                        BACK (энкюеирование)

Добавляем 5: ┌───┬───┬───┬───┬───┐
             │ 1 │ 2 │ 3 │ 4 │ 5 │
             └───┴───┴───┴───┴───┘

Удаляем:     ┌───┬───┬───┬───┐
             │ 2 │ 3 │ 4 │ 5 │
             └───┴───┴───┴───┘

Пример 1: Обработка задач из очереди

// Очередь задач для выполнения
class TaskQueue {
  constructor() {
    this.tasks = [];
    this.isProcessing = false;
  }

  addTask(task) {
    this.tasks.push(task);
    this.processQueue();
  }

  async processQueue() {
    if (this.isProcessing || this.tasks.length === 0) {
      return;
    }

    this.isProcessing = true;

    while (this.tasks.length > 0) {
      const task = this.tasks.shift(); // Первая задача из очереди
      console.log(`Выполняю: ${task.name}`);
      await new Promise(resolve => setTimeout(resolve, task.duration));
      console.log(`Завершил: ${task.name}`);
    }

    this.isProcessing = false;
  }
}

// Использование
const taskQueue = new TaskQueue();
taskQueue.addTask({ name: 'Загрузка данных', duration: 1000 });
taskQueue.addTask({ name: 'Обработка', duration: 500 });
taskQueue.addTask({ name: 'Сохранение', duration: 800 });

// Вывод:
// Выполняю: Загрузка данных
// Завершил: Загрузка данных
// Выполняю: Обработка
// Завершил: Обработка
// Выполняю: Сохранение
// Завершил: Сохранение

Пример 2: Event Loop как очередь

В браузере Event Loop использует очереди:

// Макротаски в очереди
setTimeout(() => console.log('Таск 1'), 0);
setTimeout(() => console.log('Таск 2'), 0);
setTimeout(() => console.log('Таск 3'), 0);

// Выполняются в порядке очереди (FIFO)
// Вывод:
// Таск 1
// Таск 2
// Таск 3

// То же самое с микротасками (другая очередь)
Promise.resolve()
  .then(() => console.log('Микротаск 1'))
  .then(() => console.log('Микротаск 2'))
  .then(() => console.log('Микротаск 3'));

// Вывод:
// Микротаск 1
// Микротаск 2
// Микротаск 3

Пример 3: Очередь печати документов

class PrintQueue {
  constructor(maxConcurrent = 1) {
    this.queue = [];
    this.processing = 0;
    this.maxConcurrent = maxConcurrent;
  }

  async addDocument(document) {
    this.queue.push(document);
    this.processPrinting();
  }

  async processPrinting() {
    while (this.queue.length > 0 && this.processing < this.maxConcurrent) {
      this.processing++;
      const document = this.queue.shift(); // FIFO

      await this.print(document);

      this.processing--;
    }
  }

  async print(document) {
    console.log(`Печатаю: ${document.name}`);
    await new Promise(resolve => setTimeout(resolve, document.pages * 100));
    console.log(`Готово: ${document.name}`);
  }
}

// Использование
const printer = new PrintQueue(1);
printer.addDocument({ name: 'Документ 1', pages: 5 });
printer.addDocument({ name: 'Документ 2', pages: 3 });
printer.addDocument({ name: 'Документ 3', pages: 7 });

Пример 4: Очередь сообщений в чате

class MessageQueue {
  constructor() {
    this.messages = [];
  }

  sendMessage(message) {
    this.messages.push({
      text: message,
      timestamp: new Date(),
      status: 'sent'
    });
    console.log(`Отправлено: ${message}`);
  }

  displayMessages() {
    // Показываем сообщения в порядке поступления
    this.messages.forEach((msg, index) => {
      console.log(`${index + 1}. [${msg.timestamp.toLocaleTimeString()}] ${msg.text}`);
    });
  }

  getOldestMessage() {
    return this.messages[0]; // Первое сообщение (FIFO)
  }
}

// Использование
const chat = new MessageQueue();
chat.sendMessage('Привет!');
chat.sendMessage('Как дела?');
chat.sendMessage('Отлично!');
chat.displayMessages();

Пример 5: Приоритетная очередь

Иногда нужна очередь с приоритетами:

class PriorityQueue {
  constructor() {
    this.items = [];
  }

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

    // Найди правильное место для вставки
    let added = false;
    for (let i = 0; i < this.items.length; i++) {
      if (item.priority < this.items[i].priority) {
        this.items.splice(i, 0, item);
        added = true;
        break;
      }
    }

    // Если не вставлено, добавь в конец
    if (!added) {
      this.items.push(item);
    }
  }

  dequeue() {
    return this.items.shift()?.element;
  }
}

// Использование
const pq = new PriorityQueue();
pq.enqueue('Обычная задача', 3);
pq.enqueue('Срочная задача', 1);
pq.enqueue('Менее важная', 4);

console.log(pq.dequeue()); // 'Срочная задача'
console.log(pq.dequeue()); // 'Обычная задача'
console.log(pq.dequeue()); // 'Менее важная'

Пример 6: Кэширование с LRU (Least Recently Used)

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map(); // Используем для сохранения порядка
  }

  get(key) {
    if (!this.cache.has(key)) {
      return -1;
    }

    // Переместить элемент в конец (свежий)
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }

    this.cache.set(key, value);

    // Если превышена емкость, удали самый старый
    if (this.cache.size > this.capacity) {
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
  }
}

// Использование
const cache = new LRUCache(3);
cache.put('a', 1);
cache.put('b', 2);
cache.put('c', 3);
cache.get('a'); // Переместить 'a' в конец
cache.put('d', 4); // Удалит 'b' (самый старый)

Очередь vs Стек

Практическое использование в Frontend

// Очередь запросов к API
class RequestQueue {
  constructor(maxConcurrent = 3) {
    this.queue = [];
    this.active = 0;
    this.maxConcurrent = maxConcurrent;
  }

  async request(url) {
    return new Promise((resolve) => {
      this.queue.push(() => fetch(url).then(resolve));
      this.process();
    });
  }

  async process() {
    while (this.queue.length > 0 && this.active < this.maxConcurrent) {
      this.active++;
      const task = this.queue.shift();
      await task();
      this.active--;
      this.process();
    }
  }
}

// Использование
const rq = new RequestQueue(3);
rq.request('/api/users');
rq.request('/api/posts');
rq.request('/api/comments');

Заключение

Очередь (Queue) — это фундаментальная структура данных, которая используется повсеместно в программировании:

• Event Loop в браузере
• Обработка асинхронных операций
• Системы обработки задач
• Сетевые протоколы
• Кэширование

Понимание очередей критично для написания эффективного асинхронного кода и оптимизации производительности приложений.