The previous two articles covered lists and stacks, but let’s take a look at Queue

  • The List of data structure | let’s learn a piece of data structure
  • Data structure of Stack | let’s learn a piece of data structure

Overview of the queue

A queue is a list, except that you can only insert elements at the end of the queue and delete elements at the first. Queues are used to store data in order, first-in, first-out, unlike stacks, where the last element pushed into the stack is processed first. Think of the queue as a queue in front of a bank. The people at the front of the queue are the first to do business, and newcomers have to wait in line until it is their turn.

A queue is a first-in-first-out (FIFO) data structure. Queues are used for things like submitting a series of processes to the operating system for execution, printing a pool of tasks, etc. Some simulation systems use queues to simulate customers standing in line at a bank or grocery store.

Based on the queue

The two main operations of a queue are to insert a new element into the queue and to delete an element from the queue. Insertion is also called queuing and deletion is called queuing. The in-queue operation inserts new elements at the end of the queue, and the out-of-queue operation deletes elements at the head of the queue. The following figure illustrates both operations.

Another important operation of a queue is to read the queue header element. This operation is calledpeek(). This operation returns the queue header element, but does not remove it from the queue. In addition to reading the queue header element, we also want to know how many elements are stored in the queue, which can be usedlengthAttributes meet this requirement; To clear all the elements in the queue, useclear()Method to implement.

Using arrays to implement queues seems logical. Arrays in JavaScript have advantages that are not found in other programming languages. The push() method adds elements to the end of the array, and the shift() method removes the first element.

Build Queue class

class Queue {
    constructor() {
        this.dataStore = [];
    }
    enqueue(element) {
        this.dataStore.push(element);
    }
    dequeue() {
        return this.dataStore.shift();
    }
    front() {
        return this.dataStore[0];
    }
    back() {
        return this.dataStore[this.dataStore.length - 1];
    }
    empty() {
        return this.dataStore.length === 0;
    }
    toString() {
        return this.dataStore.toString();
    }
    length() {
        return this.dataStore.length; }}Copy the code

Priority queue

In general, the element to be deleted from the queue must be the first element to be queued. However, there are some applications that use queues and do not have to follow the first-in, first-out convention when deleting elements. This application needs to be simulated using a data structure called a priority queue.

When removing an element from a priority queue, you need to consider the limitation of priority. A hospital emergency department waiting room is an example of a priority queue. When a patient enters the waiting room, the triage nurse assesses the severity of the patient’s condition and then gives a priority code. High-priority patients were treated ahead of low-priority patients, and patients of the same priority were treated on a first-come-first-served basis.

Let’s define the object that stores the queue elements, and then build our priority queue system:

class Patient {
    constructor(name, code) {
        this.name = name;
        this.code = code; }}Copy the code

The variable code is an integer indicating the priority or severity of the patient (a smaller code means a more severe condition).

Now you need to redefine the dequeue method of the Queue class so that it removes the highest priority element in the Queue. The new dequeue() method iterates through the queue’s underlying storage array, finding the elements with the lowest priority code, and then uses the array’s splice() method to remove the elements with the highest priority. The new dequeue() method is defined as follows:

dequeue() {
    let priority = this.dataStore[0];
    for (const i = 0, len = this.dataStore.length; i < len; i++){
        if (this.dataStore[i].code < priority) { priority = i; }}return this.dataStore.splice(priority, 1);
}
Copy the code

Finally, you need to define the toString() method to display the Patient object.

toString() {
    let retStr = "";
    for (var i = 0; i < this.dataStore.length; ++i) {
        retStr += `The ${this.dataStore[i].name} code: The ${this.dataStore[i].code}\n`;
    }
    return retStr;
}
Copy the code

Test priority queue

deque

A deque, or double-ended queue, is a special queue that allows us to add and remove elements from both the front end and the back end.

In computer science, a common use of a dual-end queue is to store a sequence of undo operations. Whenever a user performs an operation in the software, the operation is stored in a dual-end queue. When the user clicks the Undo button, the action is ejected from the dual-end queue, indicating that it has been removed from the back end. After a certain number of operations have been performed, the first operation is removed from the front end of the dual-end queue. Since the two-endian queue follows the first in first out (FIFO) and last in first out (LIFO) principles, it is a data structure that combines queue and stack.

Create a Deque class

class Deque {
    constructor() {
        this.dataStore = [];
    }
    addFront(element) {
        if(this.empty()){
            this.addBack(element)
        }else{
            this.dataStore.unshift(element); }}addBack(element) {
        this.dataStore.push(element);
    }
    removeFront() {
        return this.dataStore.shift();
    }
    removeBack() {
        return this.dataStore.pop();
    }
    front() {
        return this.dataStore[0];
    }
    back() {
        return this.dataStore[this.dataStore.length - 1];
    }
    empty() {
        return this.dataStore.length === 0;
    }
    toString() {
        return this.dataStore.toString();
    }
    length() {
        return this.dataStore.length; }}Copy the code

Test code for the Deque class

Practical application –> palindrome string judgment

Palindrome is the phenomenon that a word, phrase, or number written backwards is the same as if written backwards. For example, the words “dad” and “racecar” are palindromes; If Spaces and punctuation are ignored, the following sentence is also A reply: “A man, A plan, A canal: Panama”; The number 1001 is also a palindrome.

In the previous article, we used the Stack data structure, but in fact, we use the double-ended queue (Deque) to determine the size of the palindrome string.

function isPalindrome(word) {
    if (typeofword ! = ="string") {
        throw TypeError(The parameter is not of string type);
    }
    let tmp = new Deque();
    for (let element of word) {
        tmp.addBack(element);
    }
    while (tmp.length() > 1) {
        if(tmp.removeFront() ! == tmp.removeBack()) {return false; }}return true;
}

console.log(isPalindrome("racecar")) // true
console.log(isPalindrome("hello")) // false
Copy the code

The resources

  • Data structures and algorithms described in JavaScript
  • Learn JavaScript data structures and algorithms 3rd edition

If you find it helpful; Your “like” is the biggest recognition for me.