Вступление
В этой статье мы узнаем, как реализовать очередь с использованием массива в Javascript! Базовая реализация структуры данных очереди будет выполняться с помощью следующих методов:
- enqueue () - добавляет элемент в очередь.
- dequeue () - удаляет и возвращает первый элемент, введенный в очередь.
- isEmpty () - возвращает истину или ложь в зависимости от того, пуста ли очередь или нет.
- front () - возвращает передний элемент очереди.
- print () - возвращает все элементы очереди.
Примечание. В моей предыдущей статье я обсуждал, что такое структура данных очереди. "Щелкните здесь, чтобы прочитать эту статью.
Итак, начнем!
Простой способ
Вы можете довольно легко реализовать очередь в Javascript. Для начала создадим массив.
var queue = [];
Затем давайте вставим некоторые значения с помощью метода push ().
var queue = []; queue.push(1); queue.push(2);
Вот так! У нас есть готовая базовая очередь, и мы завершили операцию постановки в очередь. Точно так же вы можете выполнить операцию удаления из очереди.
queue.shift(); //dequeue operation
Чтобы проверить, пуста ли очередь, вы можете проверить, пуста ли длина массива.
if(queue.length > 0){
console.log("The Queue is not empty")
} else {
console.log("The Queue is empty")
}
Вы даже можете распечатать передний элемент и распечатать все элементы.
console.log(queue[0]); //prints the front element console.log(queue); //prints all the elements
Вышеупомянутый простой подход к очередям. Вы можете использовать это, но лучший подход будет основан на классах.
Классовый подход
Класс узла
class Node {
constructor(data) {
this.data = data;
}
}
Класс Node будет использоваться для создания узлов, которые затем можно поставить в очередь или исключить в очередь. Узел - это элементарный класс с конструктором, который инициализирует объект и назначает данные. Это простая реализация, и вы можете добавить некоторые настройки в соответствии со своими требованиями.
Класс Queue
Теперь давайте создадим основной класс Queue. Этот класс будет иметь следующие методы, относящиеся к структуре данных Queue: enqueue (), dequeue (), isEmpty (), front (), print ().
class Queue {
constructor() {
this.elements = [];
}
enqueue(node) {
this.elements.push(node);
}
dequeue() {
if(this.elements.length > 0) {
return this.elements.shift();
} else {
return 'Underflow situation';
}
}
isEmpty() {
return this.elements.length == 0;
}
front() {
if(this.elements.length > 0) {
return this.elements[0];
} else {
return "The Queue is empty!";
}
}
print() {
return this.elements;
}
}
Теперь давайте разберемся с каждой частью класса Queue.
constructor() {
this.elements = [];
}
Класс снова состоит из конструктора, который инициализирует объект. Он также создает пустой массив, который используется для создания очереди.
enqueue(node) {
this.elements.push(node);
}
Метод постановки в очередь (не статический метод) ставит узел в очередь (добавляет узел в конец очереди). На базовом уровне узел вставлен в массив. В JavaScript доступен метод push (), который перемещает элемент в конец массива.
Примечание. Метод enqueue () не соответствует условию переполнения. Условие переполнения проверяет, заполнена ли очередь (есть ли больше памяти для добавления нового элемента). Это условие переполнения не реализовано в созданном мной классе, поскольку мы предполагаем, что очередь динамически растет.
dequeue() {
if(this.elements.length > 0) {
return this.elements.shift();
} else {
return 'Underflow situation';
}
}
Метод dequeue (не статический метод) выводит из очереди / удаляет элемент из передней части очереди. Метод проверяет, больше ли элементов в очереди 0; в противном случае возникает ситуация потери значимости. На базовом уровне элемент сдвинут из массива. В JavaScript доступен метод shift (), который удаляет первый элемент из массива. Вот где временная сложность сбивается с толку. В своей предыдущей статье я объяснил: как изменяется временная сложность операции удаления из очереди при реализации очереди с использованием массива.
Примечание. Метод dequeue () следует условию потери значимости. Условие потери значимости проверяет, остались ли в очереди элементы для удаления из очереди. Вы не можете удалить пустую очередь из очереди, не так ли?
isEmpty() {
return this.elements.length == 0;
}
Метод isEmpty (ни один из методов не является статическим) проверяет, пуста ли очередь или нет. На базовом уровне он возвращает, равна ли длина массива 0 или нет. Что ж, этот метод не требует пояснений.
front() {
if(this.elements.length > 0) {
return this.elements[0];
} else {
return "The Queue is empty!";
}
}
Метод front возвращает первый элемент очереди. Он проверяет, больше ли длина массива элементов 0, и на основе этого возвращает значение. Вы можете настроить оператор if-else на более короткий оператор, например тернарные операторы. Мне нравится оригинальный способ!
print() {
return this.elements;
}
Последний метод print () возвращает массив элементов. Опять же, все говорит само за себя.
Это работает?
Теперь давайте проверим, работает ли очередь. Для этого я создал простой тестовый код.
const queue = new Queue();
//Logs: true
console.log(queue.isEmpty());
queue.enqueue(new Node({"number": 1}));
queue.enqueue(new Node({"number": 2}));
queue.enqueue(new Node({"number": 3}));
queue.enqueue(new Node({"number": 4}));
queue.enqueue(new Node({"number": 5}));
//Logs: false
console.log(queue.isEmpty());
/* Logs:
[
Node { data: { number: 1 } },
Node { data: { number: 2 } },
Node { data: { number: 3 } },
Node { data: { number: 4 } },
Node { data: { number: 5 } }
]
*/
console.log(queue.print());
queue.dequeue();
//Logs: false
console.log(queue.isEmpty());
queue.dequeue();
queue.dequeue();
queue.dequeue();
queue.dequeue();
//Logs: true
console.log(queue.isEmpty());
//Logs: []
console.log(queue.print());
Окончательный код
Вот окончательный код с репозиторием GitHub. Ссылка: https://github.com/Megh-Agarwal/Queue-data-structure
Мы успешно реализовали структуру данных очереди с использованием массива в javascript! Поздравляю! Если бы статья вам понравилась, то аплодисменты побудили бы меня продолжать писать такие статьи :)
