Создание очередей с помощью JavaScript

Эта статья была первоначально опубликована на Codecademy.

Введение

В разговорах о структурах данных в мире программирования довольно часто можно услышать термин «очередь». Очередь — это линейная структура данных, которая работает по принципу FIFO (first-in-first-out), т.е. удаление происходит спереди, а добавление — в конце. Подумайте об этом, как о кассе в продуктовом магазине. Клиенты, которые подходят к кассе первыми, обслуживаются в первую очередь. Они могут присоединиться к очереди только из задней части очереди, а после того, как их обслужат, они уходят из передней части очереди.

Линейные структуры данных

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

Очереди следуют этой схеме организации, и мы можем увидеть это, обратившись к нашей аналогии с кассой в продуктовом магазине. Каждый покупатель, который подходит к кассе, представляет собой элемент. Первый покупатель имеет связь с предыдущим покупателем, последний покупатель имеет связь со следующим покупателем, а все остальные покупатели между ними имеют связь с предыдущим и следующим покупателем.

Варианты использования очередей

Существует несколько вариантов использования очередей в программировании и реальном мире. Некоторые из них включают следующее.

Настольный принтер

Когда вы отправляете документы на принтер, они печатаются в том же порядке, в котором были отправлены, и это очень удобно, когда вы пытаетесь напечатать документы в определенном порядке. Принтер следит за тем, чтобы страницы не перепутались.

Обновление очереди музыкального проигрывателя

Иногда, когда мы работаем над задачей, у нас есть свои любимые песни для поддержания темпа. Функция очереди музыкального проигрывателя позволяет прослушивать выбранные песни именно в том порядке, в котором они расположены.

Очереди обслуживания клиентов

Если вы идете в банк, чтобы подать жалобу, вас заставляют ждать в очереди, и следующего человека в очереди не вызовут, пока не будет решен вопрос текущего клиента.

Обмен файлами между двумя процессами

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

Реализация очередей

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

Операции в очередях

Вот некоторые основные операции, которые выполняются в очередях:

  • Enqueue
  • Dequeue
  • Просмотреть
  • разворот очереди

Для реализации вышеперечисленных операций мы используем класс ES6, в котором различные операции являются методами.

Создание очереди с ее операциями

Первым шагом будет инициализация нашего класса с его собственным хранилищем (массив, в котором будут храниться элементы нашей очереди):

class Queue {
  constructor() {
    this.queue = [];
  }
}
Войти в полноэкранный режим Выйти из полноэкранного режима

Блок кода выше представляет собой создание класса с именем Queue. Метод constructor() — это специальный метод класса, который используется для создания экземпляра объекта этого класса. Он может использоваться для инициализации любого объекта, который будет использоваться во всех методах класса. Ключевое слово this служит обычным объектом в этом контексте. Оно может быть использовано для инициализации любого значения.

Далее мы добавляем каждую операцию очереди как метод класса.

Enqueue

Этот термин относится к добавлению нового элемента в очередь. Поскольку мы реализуем нашу очередь с помощью массива, мы можем использовать метод массива .push() для добавления новых элементов в очередь.

class Queue {
  constructor() {
    this.queue = [];
  }

  enqueue(element) {
    this.queue.push(element);
  }
}
Вход в полноэкранный режим Выход из полноэкранного режима

Добавленные строки в нашем блоке кода представляют метод класса Queue. Он обрабатывает одну операцию, которая добавляет новый элемент в объект массива, инициализированный с помощью метода constructor.

Метод .enqueue() принимает один аргумент элемент и затем добавляет его в this.queue с помощью метода массива .push().

Dequeue

Этот термин относится к удалению нового элемента из очереди. Опять же, метод массива .shift() легко справится с этой задачей.

class Queue {
  constructor() {
    this.queue = [];
  }

  enqueue(element) {
    this.queue.push(element);
  }

  dequeue() {
    return this.queue.shift();
  }
}
Вход в полноэкранный режим Выход из полноэкранного режима

Мы добавили новый метод .dequeue(). Этот метод не принимает никаких аргументов, в отличие от предыдущего метода. Он возвращает элемент из передней части очереди, а также удаляет его с помощью метода массива .shift().

Peek

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

class Queue {
  constructor() {
    this.queue = [];
  }

  enqueue(element) {
    this.queue.push(element);
  }

  dequeue() {
    return this.queue.shift();
  }

  peek() {
    return this.queue[0];
  }
}
Вход в полноэкранный режим Выход из полноэкранного режима

Метод .peek() проверяет значение, находящееся в начале очереди, обращаясь к первому индексу очереди.

Изменение очереди на противоположную

Как следует из названия, мы просто пытаемся изменить порядок очереди с заднего на передний. Метод .reverse() выполняется с помощью цикла while и метода массива .pop().

class Queue {
  constructor() {
    this.queue = [];
  }

  enqueue(element) {
    this.queue.push(element);
    return this.queue;
  }

  dequeue() {
    return this.queue.shift();
  }

  peek() {
    return this.queue[0];
  }

  reverse() {
    // Declare an empty array
    const reversed = [];

    // Iterate through the array using a while loop
    while (this.queue.length > 0) {
      reversed.push(this.queue.pop());
    }
    // Set queue using the new array
    this.queue = reversed;
    return this.queue;
  }
}
Вход в полноэкранный режим Выход из полноэкранного режима

Использование

Чтобы увидеть, как работает наш код, мы протестируем каждый метод нашего класса Queue.

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

// Creating a new instance of our class
const result = new Queue();

// Adding elements
result.enqueue(5);
result.enqueue(3);
result.enqueue(4);
result.enqueue(7);
console.log("After adding elements:", result.queue);

// Removing an element
result.dequeue();
console.log("After removing an element:", result.queue);

// Checking the first element in the queue
console.log("After peeking:", result.peek());

// Reversing the queue
console.log("After reversing the queue:", result.reverse());
Войти в полноэкранный режим Выйти из полноэкранного режима

После выполнения нескольких операций над нашей очередью result мы получим следующий вывод в консоли:

After adding elements: [ 5, 3, 4, 7 ]
After removing an element: [ 3, 4, 7 ]
After peeking: 3
After reverse: [ 7, 4, 3 ]
Войти в полноэкранный режим Выход из полноэкранного режима

Заключение

Вот краткий обзор того, что было рассмотрено в этой статье:

  • Мы объяснили концепцию очередей (FIFO) и то, как они применяются в реальном мире.
  • Мы создали класс и выполнили различные операции с очередью (enqueue, dequeue, peek, reverse).

Вот и все, друзья. Мы успешно реализовали очередь и ее основные операции с помощью JavaScript.

Оцените статью
Procodings.ru
Добавить комментарий