Все о структуре данных очереди в Javascript
Javascript использует очередь для отслеживания кода для выполнения. Ваш принтер также следует очереди, чтобы отслеживать, какой документ печатать следующим. Больницы используют систему, основанную на очереди приоритетов, чтобы решить, какого пациента идти первым. Дело в том, что очереди есть везде. От вашей любимой кофейни до ЦП компьютера, вашего сервера или сети - очередь - важная структура данных, о которой нужно узнать.
Видеоверсия этой статьи
Этот пост представляет собой улучшенную и более подробную версию статьи из серии Структура данных очереди на Youtube, которую вы можете проверить, предпочитаете ли вы видео.
Что такое очередь?
Структура данных очереди - это набор элементов, реализующий принцип FIFO «первым пришел - первым обслужен». Его основные действия ставятся в очередь для вставки элемента, вывода из очереди для удаления и просмотра (иногда называемого «писк») для просмотра верхнего элемента.
Это линейная структура данных, а также абстрактный тип данных. Это означает, что элементы размещаются линейно один за другим и что это определяется их поведением, а не математической моделью.
Очередь - это список, и то, что делает ее очередью, - это то, как она работает и принцип, который она реализует, а не то, как выглядит список или что он содержит.
Когда использовать очередь?
Очередь можно использовать всякий раз, когда вы хотите обрабатывать, отслеживать или контролировать вещи в соответствии с определенным порядком. Этот порядок обычно является порядком, в котором элементы были вставлены в список, но также существует очередь с приоритетом, в которой элементы организованы в списке на основе их уровня приоритета.
Процессоры и языки, такие как Javascript, используют его по этой причине, чтобы поддерживать порядок выполнения. Например, цикл событий Javascript сохраняет внутреннюю очередь обратного вызова для выполнения. Система, которая отслеживает получателей донорских органов, вероятно, представляет собой очередь с приоритетом, которая анализирует различные детали, чтобы определить приоритет каждого человека в очереди. Другой пример - принтер.
В значительной степени всякий раз, когда у вас есть список всего, что вы хотите адресовать в очень конкретном порядке, будь то порядок, вставка или приоритет, он вызывает структуру данных очереди.
Реализация очереди с массивом
Поскольку Queue - это список, и важно то, как он ведет себя и работает, а не конкретная деталь о списке, мы можем использовать любую другую структуру данных списка для его реализации. Самый простой в использовании список - это массив Javascript.
Для следующей очереди мы отслеживаем «head» (элемент спереди) и «tail» (элемент в конце). Эти два трекера очень важны, и оба они начинаются с нуля. Другой вариант, который у нас есть, - это возможность указать «емкость», максимальный размер, до которого должна вырасти очередь, и это необязательно. Отсутствие емкости означает, что у вас есть динамическая очередь.
class Queue {
#list = [];
#capacity = null;
#tail = 0;
#head = 0;
constructor(capacity) {
this.#capacity = Math.max(Number(capacity), 0) || null;
if(this.#capacity) {
this.#list = Array.from({length: this.#capacity});
}
}
}
Если указано значение «capacity», мы сначала проверяем, что оно больше нуля, и используем его для создания массива списка такого размера. Эта деталь очень важна для понимания природы очереди.
Чтобы узнать больше о структуре данных массива, обратитесь к статье Структура данных массива.
Мы можем использовать эти свойства, чтобы определить несколько геттеров для очереди. Размер определяется разницей между хвостом и головой. Вы поймете, почему мы определяем методы «enqueue» и «dequeue».
get size() {
return this.#tail - this.#head;
}
get isEmpty() {
return this.size === 0;
}
get isFull() {
return this.#capacity && this.#tail === this.#capacity;
}
Очередь пуста, если размер равен нулю, и если очередь является динамической (не имеет определенной емкости), следовательно, она никогда не бывает заполнена. Таким образом, очередь считается заполненной, если есть определенная емкость И хвост соответствует емкости.
Метод «enqueue» очень минимален и должен возвращать размер списка.
enqueue(item) {
if(!this.isFull) {
this.#list[this.#tail] = item;
this.#tail += 1;
}
return this.size;
}
Пока очередь не заполнена, мы будем использовать значение «tail», чтобы вставить элемент в этот индекс массива, а затем увеличивать его, чтобы следующее значение было вставлено в следующий индекс. Как только хвост соответствует емкости, очередь считается заполненной, и новый элемент не может быть вставлен.
Метод «dequeue» тоже в чем-то прост и возвращает удаленный элемент.
dequeue() {
let item = null;
if(!this.isEmpty) {
item = this.#list[this.#head];
delete this.#list[this.#head];
this.#head += 1;
if(this.isEmpty) {
this.#head = 0;
this.#tail = 0;
}
}
return item;
}
Пока очередь не пуста, мы возьмем элемент в голове, чтобы вернуть его, а затем «удалим» элемент в голове. Удаление элемента по индексу массива не изменяет размер массива, а просто удаляет значение по этому индексу. Это положение индекса массива считается «пустым», а пустое значение отличается от «undefined».
Затем мы продолжаем увеличивать заголовок, чтобы он указывал на следующий элемент в массиве. Если действие dequeue приводит к тому, что очередь становится пустой (заголовок совпадает с хвостом), мы сбрасываем их в исходное значение, чтобы можно было вставить новый элемент.
Примечание. Попытка поставить новый элемент в полную очередь (переполнить очередь) ничего не изменит. Перед вставкой нового элемента необходимо очистить полную очередь. Удаление элемента из очереди оставляет пустые места, которые невозможно заполнить, пока очередь заполнена, и поэтому для решения этой проблемы была введена Круговая очередь.
Чтобы заглянуть в верхний (передний) элемент, мы просто возвращаем элемент по указателю заголовка, пока очередь не пуста.
peek() {
if(this.isEmpty) {
return null;
}
return this.#list[this.#head];
}
Как видите, это очень простая концепция для реализации, и вы можете спросить, зачем беспокоиться о создании оболочки класса, если вы можете просто использовать массив непосредственно в качестве очереди, поскольку у него есть такие методы, как «push» и «unshift»? Вы также можете найти эту реализацию «дополнительной», и это может быть в Javascript.
class Queue {
#list = [];
enqueue(item) {
return this.#list.push(item)
}
dequeue() {
return this.#list.unshift()
}
peek() {
return this.#list[0]
}
}
Вышеупомянутое также является действующей динамической очередью и, возможно, всем, что вам нужно. Предыдущая сложная реализация может быть более эффективной, поскольку вы фактически не изменяете массив при каждой операции enqueue и dequeue, вы меняете значения быстрее. Вы можете проверить статью Связанный список, где я углублюсь в это подробнее.
По большей части более простая реализация - это то, что вам нужно, особенно если вас не заботят небольшая разница в скорости и оптимизации, но важно понимать эту структуру данных, как она есть, и изучать алгоритм, лежащий в основе ее реализации.
Исходный код: проверьте этот полный код на Github
Массив против очереди
И массив, и очередь - это коллекции элементов. Массив - это индексированный список, допускающий произвольное чтение и запись, где Queue реализует принцип FIFO. Единственный элемент, к которому вы обращаетесь в очереди, - это первый элемент, просматривая или удаляя его.
Оба они служат разным целям, и то, что вы можете использовать массив для реализации Queue, не делает их тесно связанными. Массив динамически растет, и одни только методы push и pop не знают, как самостоятельно обрабатывать емкость или логику переполнения.
Именно эти ограничения и характеристики в списке делают Queue совершенно другим списком и решают очень специфическую проблему, для которой у Array нет ограничений.
Реализация очереди со связанным списком
Чтобы полностью понять следующую реализацию, я рекомендую вам прочитать Статью о структуре данных связанного списка в этой серии для получения более подробной информации. Использование связанного списка для реализации очереди действительно показывает, что очередь основана только на принципе, который реализует список, а не на природе списка.
Для версии со связным списком список отсутствует. Вместо этого у нас есть указатели на первый и последний элементы для отслеживания первого и последнего элементов, которые являются наиболее важными элементами для очереди. В некоторых реализациях они обычно называются головой и хвостом. Еще одно отличие заключается в частном свойстве size для отслеживания размера списка по мере того, как мы помещаем элементы в очередь «queue» и «dequeue».
class Queue {
#firstItem = null;
#lastItem = null;
#size = 0;
#capacity = null;
constructor(capacity = null) {
this.#capacity = Math.max(Number(capacity), 0) || null;
}
get size() {
return this.#size;
}
get isEmpty() {
return this.size === 0;
}
get isFull() {
return this.#capacity ? this.size === this.#capacity : false;
}
...
В связном списке элементы имеют указатели на предыдущий и следующий элементы, но для этого нам нужен только указатель «следующий». Он известен как односвязный список. Эти указатели соединяют элементы вместе. Для создания элемента списка у нас есть метод «createItem», который возвращает значение и указатель.
#createItem(value) {
return {
next: null,
value
}
}
Для метода постановки в очередь нам нужно внести некоторые изменения. Нам все еще нужно убедиться, что очередь не заполнена, прежде чем мы добавим новый элемент, но нам нужно создать элемент, используя предоставленный элемент, а затем выполнить две проверки.
enqueue(item) {
if(!this.isFull) {
const newItem = this.#createItem(item);
if(this.isEmpty) {
this.#firstItem = newItem;
this.#lastItem = newItem;
} else {
this.#lastItem.next = newItem;
this.#lastItem = newItem;
}
this.#size += 1;
}
return this.size;
}
Если очередь пуста, первый и последний элементы совпадают, новый элемент. Если в списке уже есть элементы, нам нужно указать текущий последний элемент на новый элемент, а затем установить новый элемент как последний элемент. После мы увеличиваем размер и возвращаем его в конце.
Удаление из очереди намного проще. Сначала нам нужна переменная для хранения удаляемого элемента, и если очередь не пуста, мы используем значение первого элемента для присвоения переменной удаленного элемента и делаем следующий элемент в списке первым элементом.
dequeue() {
let removedItem = null;
if(!this.isEmpty) {
removedItem = this.#firstItem.value;
this.#firstItem = this.#firstItem.next;
this.#size -= 1;
}
return removedItem;
}
Следующий элемент может иметь значение NULL, если в очереди только 1 элемент. Затем мы уменьшаем размер и возвращаем удаленный элемент.
Взгляд тоже прост. Все, что он делает, это возвращает значение первого элемента.
peek() {
return this.#firstItem.value;
}
Связанный список действительно эффективен, потому что он связывает данные, которые могут находиться где угодно в памяти, со ссылками на указатели. Он также обеспечивает сверхбыстрые операции вставки и удаления, не оставляя лишнего места в памяти. Я считаю, что очередь лучше, если реализована со связанным списком, поскольку она уже наследует все замечательные качества связанных списков.
Исходный код: проверьте этот полный код на Github
Следующий
Нам все еще нужно улучшить Queue, реализованный с помощью Array, и есть также другие типы очередей, такие как Priority и Circular queues, которые решают очень конкретные проблемы, о которых вы можете узнать в следующей статье .
Канал Youtube: До точки с запятой
Веб-сайт: beforesemicolon.com
