Очередь с приоритетом на JavaScript

"Плохие программисты думают о коде.

Хорошие программисты думают о структурах данных и их взаимосвязях"

Линус Торвальдс, создатель Linux

Очередь и стек — основные структуры данных в программировании.

Стек можно сравнить со стопкой подносов в столовой, которые складывают один на другой. Поднос, который попал в стопку последним, возьмут в первую очередь. Стек работает по принципу LIFO "последним пришел — первым ушел" (last in first out). Над стеком можно осуществлять две операции: push (занесение данных) и pop (изъятие данных).

Так устроен стек

Очередь (queue) напоминает обычную очередь. Она работает по принципу FIFO "первым пришел — первым ушел" (first in first out).

Над очередью можно осуществлять две операции: enqueue — добавлять элементы в конец очереди и dequeue — удалять первый элемент очереди.

Так устроена очередь

Чтобы реализовать операцию enqueue, необходимо:

убедиться, что очередь, не переполнена,
добавить элемент в конец очереди
увеличить текущий размер на единицу.

Чтобы реализовать операцию dequeue, необходимо:

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

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

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

Добавляем в очередь методы:
enqueue — метод, который принимает значение v и помещает его в конец очереди.
dequeue — метод, который возвращает первый элемент очереди.

Результат:

class Queue {
constructor() {
    this._data = [];
}
enqueue(v) {
    this._data.push(v);
}
dequeue() {
    return this._data.shift();
}
}

Также добавим в очередь метод isEmpty, который проверяет очередь на пустоту и метод size, который вернёт размер очереди и метод clear, который очистит очередь

isEmpty() {
return this._data.length === 0;
}

size() {
return this._data.length;
}

clear() {
this._data.length = 0;
}

Результат:

class Queue {
constructor() {
    this._data = [];
}
enqueue(v) {
    this._data.push(v);
}
dequeue() {
    return this._data.shift();
}
isEmpty() {
    return this._data.length === 0;
}
size() {
    return this._data.length;
}
clear() {
    this._data.length = 0;
}

}

Очередь с приоритетом (priority queue) отличается от обычной очереди тем, что каждый элемент в ней имеет определенный числовой приоритет. Элемент с наибольшим приоритетом становится в очередь первым. Если приоритеты элементов одинаковые, тогда используется обычная очередь: FIFO "первым пришел — первым ушел" (first in first out).

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

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

Большие очереди реализуются на основе кучи. Малые очереди с небольшим количеством элементом можна реализовать на основе массива.

Очередь с приоритетом создадим на основе обычной очереди, унаследовав её методы:

class PriorityQueue extends Queue {

}

Так как очередь с приоритетом реализуется для элементов, у которых указан приоритет, такими элементами будут объекты. Поэтому добавим проверку - действительно ли на входе у нас элементы с типом данных "объект"

if(typeof(v) !== "object") {
throw newError(`Ожидается объект, а получен ${typeof(v)}`);
}

Ещё одна проверка - есть ли у объекта поле priority:

if(v.priority === undefined) {
throw newError("У объекта отсутствует поле priority");
}
И если только если обе проверки пройдены, передаём управление родительскому конструктору:

super.enqueue(v)

Всё вместе:

enqueue(v) {
if(typeof(v) !== "object") {
throw newError(`Ожидается объект, а получен ${typeof(v)}`);
} else if(v.priority === undefined) {
throw newError("У объекта отсутствует поле priority");
} else {
    super.enqueue(v);
}
}
При извлечении элемента очередь нужно отсортировать. (видео 49:36 - 52:01 - не совсем понятно возвращение this._data.splice(pos, 1)[0]; - зачем здесь [0]. Уже понятно. Так как данные передаются в виде имя + приоритет, возвращается только имя, без приоритета.)

dequeue() {
let priority = this._data[0].priority;
let pos = 0;
this._data.forEach((o, i) => {
    if(o.priority < priority) {
priority = o.priority;
pos = i;
    }
});
return this._data.splice(pos, 1)[0];
}

Кстати, здесь наибольший приоритет имеет наименьшее значение. Чтобы отсортировать наоборот, достаточно изменить условие: if(o.priority > priority)

Ссылки:
Стек, очередь и куча
Структуры данных на JavaScript: Очереди (очередь с приоритетом начинается с 40:00)
10 типов структур данных, которые нужно знать

Поиск по этому блогу

Изучаем JavaScript

Очередь с приоритетом на JavaScript