В предыдущей статье я обсуждал структуру данных стека. Стек является примером структуры данных, в которой последние данные, поступающие в него, являются первыми данными, которые из него выходят. Один пример, который я использовал, — это стопка подносов в кафетерии, где покупатель может взять поднос только сверху, а посудомоечная машина может поставить чистый поднос только сверху. Другими словами, все происходит на вершине стека.
С другой стороны, структура данных очереди похожа на очередь, в которую вы встаете в продуктовом магазине. С линией вы входите в линию сзади и выходите из линии спереди. Таким образом, первые данные в очереди — это первые данные из очереди. В этом основное различие между очередью и стеком.
Как и в стеке, в очереди всего несколько операций. Реализации очередей используют аналогичные имена для этих операций. Добавление новых данных в очередь — это операция push, а удаление данных из очереди — операция pop. Однако, в отличие от стеков, где вы можете просматривать только верхнюю часть стека, с очередью вы можете просматривать как начало очереди, так и конец очереди.
Разобравшись с этим фоном, давайте перейдем к реализации очереди JavaScript.
Проектирование класса очереди
Я уже определил четыре поведения класса Queue: push, pop, front и back. Мне нужен метод, который сообщает мне, сколько элементов находится в очереди — метод size. Мне нужен метод, чтобы проверить, пуста ли очередь — метод empty, и мне нужен метод для удаления всех элементов из очереди (наверняка вы стояли в очереди в продуктовом магазине и закрывали кассу до того, как твоя очередь) - метод clear.
Мне также нужно решить, какую структуру данных использовать для хранения элементов очереди. Для этой реализации я буду использовать массив.
Вот мое определение класса Queue:
class Queue {
constructor() {
this.dataStore = [];
}
push(element) {
this.dataStore.push(element);
}
pop() {
this.dataStore.shift();
}
front() {
return this.dataStore[0];
}
back() {
return this.dataStore[this.dataStore.length-1];
}
empty() {
return this.dataStore.length == 0;
}
size() {
return this.dataStore.length;
}
clear() {
while (this.dataStore.length != 0) {
this.dataStore.pop();
}
}
}
Вот короткая программа для проверки этого определения:
let line = new Queue()
line.push("Mike");
line.push("Cynthia");
putstr("Front of line: ");
print(line.front());
putstr("Back of line: ");
print(line.back());
line.push("Jonathan");
putstr("Number of people in line: ");
print(line.size());
putstr("Back of line is now: ");
print(line.back());
line.pop();
putstr("Front of line: ");
print(line.front());
putstr("Back of line: ");
print(line.back());
print("Closing line.");
line.clear();
if (line.empty()) {
print("Line is now empty.");
}
else {
putstr("Number of people in line: ");
print(line.size());
}
Вывод этой программы:
Front of line: Mike Back of line: Cynthia Number of people in line: 3 Back of line is now: Jonathan Front of line: Cynthia Back of line: Jonathan Closing line. Line is now empty.
Некоторые приложения очереди
Есть несколько полезных применений очередей. Очереди часто используются в исследованиях моделирования, где изучаются потоки клиентов. Например, сколько островков самообслуживания необходимо продуктовому магазину, чтобы не допустить слишком большого количества клиентов в часы пик? Программа моделирования будет использовать структуру данных очереди для представления каждой строки в хранилище.
В качестве первого примера я собираюсь написать небольшую программу, которая реализует программу планирования очереди для отслеживания ежедневных встреч руководителя. Помощник руководителя собирает новые встречи на следующий день и сохраняет их в очереди встреч.
В начале следующего дня осуществляется доступ к очереди назначений и отображается первое назначение. По завершении оно стирается и отображается время следующей встречи. Это продолжается до тех пор, пока очередь не станет пустой.
Я также создал новый класс для хранения времени. Теперь вот программа:
class Time {
constructor(hour, minute) {
this.hour = hour;
this.minute = minute;
}
show() {
return this.hour + ":" + this.minute;
}
}
let appts = new Queue();
for (let i = 1; i <= 6; i++) {
putstr("Enter appointment hour: ");
let hour = parseInt(readline());
putstr("Enter appointment minute: ");
let minute = parseInt(readline());
let theTime = new Time(hour, minute);
appts.push(theTime);
}
print("Appointments for the day: ");
let nextAppt = "n";
while (!appts.empty()) {
putstr("Time: ");
print(appts.front().show());
appts.pop();
}
Результат одного запуска этой программы:
C:\js>js queue.js Enter appointment hour: 8 Enter appointment minute: 15 Enter appointment hour: 9 Enter appointment minute: 20 Enter appointment hour: 10 Enter appointment minute: 25 Enter appointment hour: 11 Enter appointment minute: 25 Enter appointment hour: 12 Enter appointment minute: 30 Enter appointment hour: 1 Enter appointment minute: 15 Appointments for the day: Time: 8:15 Time: 9:20 Time: 10:25 Time: 11:25 Time: 12:30 Time: 1:15
Для второй демонстрации я возьму пример моделирования из книги Структуры данных в C++, написанной Тимоти Баддом. Эта симуляция представляет собой симуляцию кассира банка, которая может помочь банку определить, сколько кассовых линий должно быть открыто одновременно, чтобы свести к минимуму количество времени, в течение которого их клиенты должны ждать помощи.
Программа создает два класса — класс Customer и класс Teller. Класс Customer отслеживает две части данных: время, когда покупатель стоит в очереди, и количество времени, которое он проводит с кассиром. Класс Teller также должен отслеживать две части данных: помогают ли они клиенту и когда они начинают помогать клиенту.
Вот определения для этих двух классов:
class Customer {
constructor(arrival) {
this.arrivalTime = arrival;
this.processTime = 2 + parseInt(Math.random() * (6-1) + 1);
}
done() {
return --this.processTime < 0;
}
arrival() {
return this.arrivalTime;
}
}
class Teller {
constructor() {
this.free = true;
}
isFree() {
if (this.free) { return true };
if (this.customer.done()) {
this.free = true;
return this.free;
}
}
addCustomer(c) {
this.customer = c;
this.free = false;
}
}
Customer объектов выстраиваются в линию, а затем покидают ее. Teller объекты либо свободны, чтобы увидеть нового клиента, либо заняты, помогая клиенту.
Ниже приведена программа, которая использует эти классы для выполнения простой симуляции банковского кассира. Вы можете изменить количество кассиров, чтобы изменить среднее время ожидания, чтобы решить, сколько кассовых линий должно быть в вашем банке.
Вот код:
let tellers = 2;
let minutes = 60;
let totalWait = 0;
let customers = 0;
let line = new Queue();
let teller = new Array(tellers);
for (let i = 0; i < tellers; i++) {
teller[i] = new Teller();
}
for (let time = 0; time < minutes; time++) {
if (parseInt(Math.random() * (10-1) + 1) < 9) {
let newCustomer = new Customer(time);
line.push(newCustomer);
}
for (let i = 0; i < tellers; i++) {
if (teller[i].isFree() && !line.empty()) {
let frontCustomer = line.front();
customers++;
totalWait += (time - frontCustomer.arrival());
teller[i].addCustomer(frontCustomer);
line.pop();
}
}
}
print("Average wait: " + (totalWait / customers));
Вот один запуск программы с количеством кассиров, равным 2:
Average wait: 16.571428571428573
Вот как меняется среднее время ожидания, когда я увеличиваю количество кассиров до 5:
Average wait: 2
Очереди можно использовать и для других приложений, но наиболее популярными являются имитации.
Другим типом очереди является очередь с приоритетом, в которой элементы, хранящиеся в очереди, имеют весовой коэффициент приоритета, а элементы с более высоким приоритетом извлекаются из очереди раньше, чем элементы с более низким приоритетом. Хорошим примером приоритетной очереди является зал ожидания отделения неотложной помощи больницы. Сломанная нога имеет более высокий приоритет, чем лихорадка, и врач скорее обратится к врачу. Я напишу о реализации приоритетных очередей в следующей статье.
Спасибо за прочтение. Пожалуйста, ответьте на эту статью или отправьте мне электронное письмо с вашими комментариями и предложениями.
