В этом руководстве вы узнаете о структуре данных Queue и о том, как реализовать очередь в JavaScript.
Очередь — это упорядоченный список элементов, где элемент вставляется в конец очереди и удаляется из начала очереди.
Queue работает по принципу «первым поступил — первым обслужен» (FIFO), который отличается от стека, работающего по принципу «последним пришел — первым обслужен» (LIFO).
Очередь имеет две основные операции:
- Вставка нового элемента в конец очереди, которая называется enqueue.
- Удаление элемента из начала очереди, которое называется dequeue.
На следующем рисунке показана очередь:
Другой важной операцией очереди является получение элемента в начале, называемое peek. В отличие от операции удаления из очереди, операция просмотра возвращает элемент в начале без изменения очереди.
Название queue происходит от аналогии с очередью клиентов в банке. Клиент, который придет первым, будет обслужен первым, а тот, кто придет позже, будет поставлен в очередь в конце очереди и будет обслужен позже.
Реализация очереди JavaScript с использованием объекта
Ниже показано, как реализовать структуру данных queue с помощью объекта:
class Queue {
constructor() {
this.elements = {};
this.head = 0;
this.tail = 0;
}
enqueue(element) {
this.elements[this.tail] = element;
this.tail++;
}
dequeue() {
const item = this.elements[this.head];
delete this.elements[this.head];
this.head++;
return item;
}
peek() {
return this.elements[this.head];
}
get length() {
return this.tail - this.head;
}
get isEmpty() {
return this.length === 0;
}
}Как это работает:
- Сначала инициализируем в конструкторе объект, в котором хранятся элементы очереди (
elements) и две переменные для отслеживания головы и хвоста:
class Queue {
constructor() {
this.elements = {};
this.head = 0;
this.tail = 0;
}
//...
}- Во-вторых, поставьте элемент в очередь, добавив его в объект elements в конец очереди:
class Queue {
//...
enqueue(element) {
this.elements[this.tail] = element;
this.tail++;
}
//...
}- В-третьих, удалите элемент из начала очереди:
class Queue {
// ...
dequeue() {
const item = this.elements[this.head];
delete this.elements[this.head];
this.head++;
return item;
}
//...
}- В-четвертых, определите метод peek(), который обращается к элементу в начале очереди:
class Queue {
//...
peek() {
return this.elements[this.head];
}
//...
}- В-пятых, получите длину очереди:
class Queue {
//...
get length() {
return this.tail - this.head;
}
//...
}Очередь пуста, когда длина равна нулю.
- Наконец, определите метод isEmpty(), который возвращает true, если очередь пуста:
class Queue {
// ...
get isEmpty() {
return this.tail - this.head;
}
// ...
}Чтобы создать новую очередь из функции-конструктора Queue(), используйте ключевое слово new следующим образом:
let q = new Queue();
Чтобы поставить в очередь числа от 1 до 7, используйте следующий код.
for(let i = 1; i <= 7; i++) {
q.enqueue(i);
}Чтобы получить номер в начале очереди, используйте метод peek().
console.log(q.peek()); // 1
Чтобы получить текущую длину очереди, используйте метод length(), как в следующем примере.
console.log(q.length); // 7
Чтобы удалить элемент в начале очереди, используйте метод dequeue() следующим образом:
// dequeue all elements
while(!q.isEmpty()) {
console.log(q.dequeue());
}Все это вместе:
class Queue {
constructor() {
this.elements = {};
this.head = 0;
this.tail = 0;
}
enqueue(element) {
this.elements[this.tail] = element;
this.tail++;
}
dequeue() {
const item = this.elements[this.head];
delete this.elements[this.head];
this.head++;
return item;
}
peek() {
return this.elements[this.head];
}
get length() {
return this.tail - this.head;
}
get isEmpty() {
return this.length === 0;
}
}
let q = new Queue();
for (let i = 1; i <= 7; i++) {
q.enqueue(i);
}
// get the current item at the front of the queue
console.log(q.peek()); // 1
// get the current length of queue
console.log(q.length); // 7
// dequeue all elements
while (!q.isEmpty) {
console.log(q.dequeue());
}