Подробные примеры с картинками и текстом для реализации очередей на JavaScript.

Рекомендации по теме: руководство по JavaScript

1. Структура данных очереди

• Очередь — это тип структуры данных «первым пришел — первым обслужен» (FIFO). Первый поставленный в очередь элемент (входной) является первым исключенным из очереди (выходной).
• Очередь имеет 2 указателя: заголовок и хвост. Самый старый элемент в очереди находится в начале, а самый новый элемент в очереди — в конце.
• Очередь похожа на очередь в метро. Пассажиры возле двери стоят в начале очереди, а пассажиры, только что вошедшие в очередь, находятся в конце очереди.

С точки зрения высокого уровня очередь — это структура данных, которая позволяет нам обрабатывать каждый элемент данных в том порядке, в котором он хранится в базе данных.

2. Операции с очередью

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

• Операция постановки в очередь <br/>Операция постановки в очередь заключается в вставке элемента в конец очереди, и вставленный элемент становится концом очереди.

Операция постановки в очередь на рисунке выше вставляет элемент 8 в конец, и номер 8 становится концом очереди.

очередь.enqueue(8);

• Операция удаления из очереди <br/> Операция удаления из очереди заключается в извлечении элемента из начала очереди, и следующий элемент в очереди становится головным элементом.

На рисунке выше операция удаления из очереди возвращает и удаляет элемент 7 из очереди. После удаления из очереди элемент 2 становится новым головным элементом.

очередь.dequeue(); // => 7

• операция проверки <br/> Операция проверки считывает начало очереди без изменения очереди.

Элемент 7 — это начало очереди на рисунке выше, и операция проверки возвращает только заголовок (элемент) 7 без изменения очереди.

очередь.peek(); // => 7

• длина очереди Операция длины вычисляет, сколько элементов содержит очередь.

На картинке в очереди 4 элемента: 4, 6, 2 и 7. В результате длина очереди равна 4.

очередь.длина; // => 4

• Временная сложность операций с очередью Для всех операций с очередью (постановка в очередь, удаление из очереди, просмотр и длина) важно то, что все эти операции должны выполняться за фиксированное время O(1).

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

3. Реализация очередей в JavaScript

Давайте посмотрим на возможную реализацию структуры данных очереди с сохранением требования, что все операции должны выполняться за постоянное время O(1).

класс Очередь {
  конструктор() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }

  очередь (пункт) {
    this.items[this.tailIndex] = элемент;
    это.tailIndex++;
  }

  удаление из очереди() {
    const item = this.items[this.headIndex];
    удалить this.items[this.headIndex];
    это.headIndex++;
    возврат товара;
  }

  заглянуть() {
    вернуть this.items[this.headIndex];
  }

  получить длину() {
    вернуть this.tailIndex - this.headIndex;
  }
}

константная очередь = новая очередь();

очередь.enqueue(7);
очередь.enqueue(2);
очередь.enqueue(6);
очередь.enqueue(4);

очередь.dequeue(); // => 7

очередь.peek(); // => 2

очередь.длина; // => 3

const очередь = новая Queue() — это способ создания экземпляра очереди.

Вызовите метод очереди.enqueue(7), чтобы поместить элемент 7 в очередь.

очередь.dequeue() удаляет главный элемент из очереди, а очередь.peek() просто просматривает начало.

Наконец, очередь.длина показывает, сколько элементов осталось в очереди.

Что касается реализации: внутри класса Queue простой объект this.items содержит элементы в очереди по числовому индексу. Индекс элемента заголовка отслеживается с помощью this.headIndex, а индекс элемента хвоста — с помощью this.tailIndex.

• Сложность методов очереди

Методы очереди(), dequeue(), peek() и length() класса Queue используют только:

доступ к атрибутам (например, this.items[this.headIndex]),

или выполнять арифметические операции (например, this.headIndex++).

Следовательно, временная сложность этих методов равна постоянному времени O(1).

4. Резюме

Структура данных очереди представляет собой тип «первым пришел — первым вышел» (FIFO): самый ранний элемент, который будет поставлен в очередь, является самым ранним элементом, который будет исключен из очереди.

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

Все операции с очередью должны выполнять O(1) за постоянное время.

Рекомендации по теме: Учебное пособие по изучению JavaScript.

Выше приведено подробное объяснение реализации очередей в JavaScript с примерами и изображениями. Для получения дополнительной информации обратите внимание на другие соответствующие статьи на китайском веб-сайте PHP.