Очередь - queue

Очередь в JavaScript, как и стек, можно реализовать с помощью массивов. Очередь работает по принципу FIFO (First In, First Out), что означает, что элементы извлекаются в том порядке, в котором они были добавлены.

Классическая очередь — это абстрактная структура данных, которая предусматривает следующие операции:

Enqueue (поместить в очередь): Добавление элемента в конец очереди. В массивах JavaScript это обычно делается с помощью метода push.

Dequeue (извлечь из очереди): Удаление и возврат первого элемента очереди. Для массивов это обычно делается с помощью метода shift, который извлекает первый элемент массива, но этот метод имеет временную сложность O(n), так как при его вызове все элементы сдвигаются.

Front или Peek: Возврат первого элемента без его удаления. Это просто доступ к элементу в начале массива, который имеет временную сложность O(1).

IsEmpty: Проверка, пуста ли очередь. Это простая проверка на то, пуст ли массив, и выполняется за O(1).

let queue = []; // этот массив будет нашей очередью
queue.push(1);
queue.push(2);
queue.push(3);
console.log(queue.shift());
console.log(queue.shift());
console.log(queue);

Зачем нам вообще нужна очередь?

Очереди используются в различных алгоритмах и структурах данных, а также для управления потоками данных в программировании. Вот несколько примеров:

• Обслуживание клиентов: В системах обслуживания клиентов, таких как кассы в магазине или обслуживание клиентов в банке, используется очередь, чтобы клиенты обслуживались в порядке их прибытия.

• Системы печати: В очереди печати задания на печать обрабатываются в порядке их поступления.

• Управление задачами: В операционных системах очереди используются для управления задачами и процессами.

• Асинхронное программирование: В асинхронных системах очередь задач используется для управления выполнением асинхронных операций.

Использование очереди помогает организовать и управлять данными или задачами в порядке их поступления, что делает её важным инструментом в программировании и алгоритмах.

Пример 1: Печать первых N чисел

Эта функция использует очередь для печати первых N чисел.

function printFirstNNumbers(n) {
  let queue = [];
  for (let i = 1; i <= n; i++) {
    queue.push(i);
  }
  while (queue.length > 0) {
    console.log(queue.shift());
  }
}

Пример 2: Кольцевая очередь

Эта функция реализует кольцевую очередь фиксированного размера.

function CircularQueue(size) {
  this.queue = [];
  this.size = size;
}

CircularQueue.prototype.enqueue = function (element) {
  if (this.queue.length === this.size) {
    this.queue.shift();
  }
  this.queue.push(element);
};

CircularQueue.prototype.dequeue = function () {
  return this.queue.shift();
};

let cq = new CircularQueue(3);
cq.enqueue(1);
cq.enqueue(2);
cq.enqueue(3);
cq.enqueue(4);
console.log(cq);
console.log(cq.dequeue());

Описание решения

Конструктор CircularQueue: принимает размер очереди и инициализирует пустой массив queue и сохраняет размер очереди size.

Метод enqueue: добавляет элемент в очередь. Если очередь заполнена (длина очереди равна размеру), удаляет первый элемент перед добавлением нового.

Метод dequeue: удаляет и возвращает первый элемент из очереди.

Пример использования:

1. Создаем новую кольцевую очередь cq размером 3.
2. Добавляем в очередь элементы 1, 2, 3 и 4. При добавлении четвертого элемента первый элемент удаляется, чтобы сохранить размер очереди равным 3.
3. Печатаем текущее состояние очереди.
4. Удаляем и печатаем первый элемент очереди.

Эти примеры демонстрируют, как использовать очередь для различных задач, включая базовую очередь и кольцевую очередь фиксированного размера.

Совет

Если в данном решении вас смущают слова this, prototype, то они подробно будут обсуждаться в занятии 4.