A Мы пробираемся через больше структур данных, которые мы будем строить на основе того, что мы узнали из предыдущих сообщений в блоге.

В этой статье мы углубимся в Очередь

/ kyo͞o /
омофоны: cue, Kew, kyu, Q, que

И как концептуализировать это в JavaScript.

В этой статье я буду использовать классы JavaScript и ES6 в своих примерах реализации Queue. Внутри класса я буду использовать массив для хранения моих данных, потому что его немного легче объяснить и визуализировать в коде, но вы также можете реализовать это с помощью Связанного списка .. Что и есть Я проиллюстрировал на доске 😅 Если вы не знакомы с связанным списком, не стесняйтесь читать о них мой блог.

Стартовая линия - это серия фильмов, созданная Романом Тернером. Статьи с полезными советами и техническими советами, которые помогут вам начать разработку. Написано буткемпером для буткемперов.

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

Очередь - это абстрактный тип данных с линейной структурой данных ... воу, что?

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

Линейная структура данных означает, что это упорядоченный список элементов. Порядок для очереди - первым пришел - первым ушел (FIFO). Создаваемые нами методы настраиваемого класса будут обеспечивать такое поведение. Это противоположно структуре данных Stack по порядку. Если вы хотите узнать больше о стеках, загляните в мой блог о них.

Каковы практические применения этой структуры данных?

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

Важные термины для очереди

Хвост / Назад: это последний элемент в очереди, куда вы добавляете свой элемент в очередь.

Head / Front: Это первый элемент в очереди, из которого вы удаляете свой элемент из очереди.

Важные методы для очереди

enqueue (): помещает новый элемент или значение в конец очереди.

dequeue (): удаление элемента в начале очереди.

peek (): проверяет значение в начале очереди.

size (): возвращает длину очереди.

isEmpty (): проверяет, пуста ли очередь.

clear (): удаляет все элементы.

Как реализовать очередь в JavaScript

Потрясающий! Теперь мы можем использовать это ... но на чем?

Представляем новый раздел блога о структуре данных.

Приложения для алгоритмов!

Это действительно помогает понять, ПОЧЕМУ скрываются за структурами данных. Пример, который я рассмотрю, можно найти на leetcode.

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

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

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

E Каждый раз, когда мы вызываем метод для добавления в очередь (Enqueue), мы также можем удалить первый элемент из очереди (Dequeue), а затем вычислить среднее значение.

Вы можете реализовать собственный метод класса для Queue, который будет усреднять все значения внутри Queue, чтобы вы могли просто вызвать my_queue.average.

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

В итоге

Основные функции очереди:

  • Это упорядоченный список элементов.
  • Очереди работают в порядке очереди.
  • Чтобы получить доступ к среднему элементу, вам нужно удалить все элементы перед этим элементом.

Распространенные методы для очереди:

  • enqueue, помещая новый элемент или значение в конец очереди.
  • dequeue, удаляя элемент в начале очереди.
  • peek, проверяет значение в начале очереди.
  • size, возвращает длину очереди.
  • isEmpty, проверяет, пуста ли очередь.
  • clear, удаляет все элементы из очереди.

Уфф, ты сделал это.

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

Вопросы и Комментарии приветствуются.