One day, when you look back on the road you have traveled, you will find that these years of constant struggle are the best life. —— Freud

Queue, FIFO for short, follows the principle of First In First Out. Contrary to the "stack", it adds elements at the end of the queue and deletes elements at the head of the queue. If there are no elements in the queue, it is called empty queue.

There are many examples of queues corresponding to life scenarios. For example, when we go to the train station window to buy tickets, we always queue up. The first person in the queue buys tickets first. When new people arrive, they wait in the queue at the end of the queue for the tickets before they are finished. In addition, our order timeout queue, activity buy first come first served and so on, queue is widely used in life.

Author's Profile: May Jun, Nodejs Developer, post-90s youth who love technology and like to share, Public No. Nodejs Technology Stack, Github Open Source Project https://www.nodejs.red

JavaScript array implementation queue

The array function provided in JavaScript can realize a simple queue. It's also very convenient to use. Familiar with the relevant API s is enough. Let's look at the implementation of the queue entry and queue exit process based on JS arrays.

The above pictures show the process of queue initialization, queue entry and queue exit. Now we use JavaScript prototype chain to implement.

Initialization queue

Initialize a data structure that stores elements in a queue. If the default assignment empty array is not passed in, the type is checked first.

function QueueStudy(elements) {
    if (elements && !(elements instanceof Array)) {
        throw new Error('Must be in array format!');
    }

    this.elements = elements || [];
}

Queue Added Elements

Implement an enQueue method to add elements to the queue. Note that only the end of the queue can be added, using the push method in the JavaScript array.

QueueStudy.prototype.enQueue = function(element) {
    this.elements.push(element);
}

Queue Removal Elements

Implement a deQueue method that pops up elements at the head of the queue using the shift method in the JavaScript array.

QueueStudy.prototype.deQueue = function() {
    return this.elements.shift();
}

It's easy to implement with JavaScript arrays. See the source code. https://github.com/Q-Angelo/project-training/tree/master/algorithm/queue-js.js

Priority queue

Priority queue, element addition and deletion is based on priority. A practical example is the sequence of airport boarding. First class and business class passengers have higher priority than economy class passengers. In some countries, older people and pregnant women (or women with children) also enjoy higher priority on boarding than other passengers.

Priority queues correspond to many examples in our life scenarios. For example, when we go to the bank to handle business, we usually arrange the number first, first come first, first handle, but there will also be VIP members first handle, or when we go to the train station window to buy tickets, there will also be prompts for soldiers to handle the number first, and so on.

Implementation steps

The core implementations follow the example of JavaScript arrays for queuing, and modify the queuing function as follows:

• Declare queueElement objects that contain elements to be added to the queue
• If the queue is empty, enter the queue directly.
• If you find an element with a higher priority than priority, insert a new element, using the splice method in the JS array
• Finally, if the priority of all the elements in the queue is less than priority, they enter the queue directly at the end of the queue.
• Simple modifications have also been made to the print-out method.

Code examples

PriorityQueue.prototype.enQueue = function(element, priority) {
    const queueElement = { element, priority };

    if (this.isEmpty()) {
        return this.elements.push(queueElement);
    }

    let added = false;
    for (let i=0; i < this.elements.length; i++) {
        if (priority < this.elements[i]['priority']) {
            added = true;
            this.elements.splice(i, 0, queueElement)
            break;
        }
    }

    if (!added) {
        this.elements.push(queueElement);
    }
}

PriorityQueue.prototype.print = function() {
    console.log(this.elements.map(item => item.element).join(' | '));
}

Running test

const queue = new PriorityQueue();
queue.enQueue('General membership 1', 5);
queue.enQueue('General membership 2', 10);
queue.print() // Ordinary Membership 1 | Ordinary Membership 2
queue.enQueue('VIP Membership 1', 3);
queue.print() // VIP Member 1 | Ordinary Member 1 | Ordinary Member 2
queue.enQueue('VIP Membership 2', 3);
queue.print() // VIP Membership 1 | VIP Membership 2 | Ordinary Membership 1 | Ordinary Membership 2
queue.deQueue();
queue.print() // VIP Member 2 | Ordinary Member 1 | Ordinary Member 2

Legend display

The following illustrations show how the above priority queue program works

Above all, the element with the lowest priority is placed in front of the queue, which is called the lowest priority queue, while the implementation of the highest priority queue is the opposite. Source code see https://github.com/Q-Angelo/project-training/tree/master/algorithm/queue-priority.js

Cyclic queue

Circular queue is also called circular queue in some places. It is a kind of circular structure queue itself. Compared with ordinary queue, it has the advantage that after the first element is out of the queue, the remaining elements do not need to move forward in turn, making full use of vector space. The complete implementation process is given in the following introduction.

When designing a circular queue, it can be implemented clockwise or counter-clockwise. When entering the queue, it can add elements at the end of the queue according to the (tail%) capacity rule. Tail means the pointer at the end of the queue, capacity means the capacity. Out of the queue, it can also be operated by the (head%) capacity rule. Head means the pointer at the end of the queue. Queues with degree 6 are illustrated in graphic form.

ES6 implements circular queue

What needs to be done to implement a circular queue using EcameScript 6's Class? The following are the functional points that need to be implemented:

• Create a queue and initialize the queue space
• Check if the queue is empty
• Check if the queue overflows
• Join the team
• Team out
• queue length
• ClearQueue
• Destroy the queue, and memory space will be freed
• Queue traversal output

const Init = Symbol('QueueStudy#Init');

class QueueStudy {
    constructor (capacity) {
        if (!capacity) {
            throw new Error('The capacity field is required!');
        }

        this.capacity = capacity; // Initialization capacity
        this[Init]();
    }

    /**
     * Clear the queue, save memory
     */
    clear() {
        this[Init]()
    }

    [Init]() {
        this.queue = new Array(this.capacity); // Initialize queue memory space
        this.queueLen = 0; // Initialize queue elements
        this.head = 0; // Team leader
        this.tail = 0; // tail
    }

    /**
     * Is the queue empty?
     */
    isEmpty() {
        return this.queueLen === 0 ? true : false;
    }

    /**
     * Queue Overflow
     */
    isOverflow() {
        return this.queueLen === this.capacity
    }

    /**
     * Join the team
     */
    enQueue(element) {
        if (this.isOverflow()) {
            return false;
        }

        this.queue[this.tail] = element;
        this.tail++;
        this.tail = this.tail % this.capacity;
        this.queueLen++;
        return true;
    }

    /**
     * Team out
     */
    deQueue() {
        if (this.isEmpty()) {
            throw new Error('The queue was empty');
        } else {
            const element = this.queue[this.head];
            this.head++; // Team Head Position Moving
            this.head = this.head % this.capacity;
            this.queueLen--;
            return element;
        }
    }

    /**
     * queue length
     */
    len() {
        return this.queueLen;
    }

    /**
     * Destroy queues, memory recovery
     */
    destroy() {
        this.queue = null;
    }

    /**
     * Queue element traversal
     */
    traversing() {
        console.log('------------traversing start------------');
        
        for (let i=this.head; i<this.queueLen + this.head; i++) {
            console.log(this.queue[i % this.capacity]);
        }
        console.log('------------traversing end------------\n');
    }
}

Running test

const q1 = new QueueStudy(6);

q1.enQueue('a');
q1.traversing();
q1.enQueue('b');
q1.enQueue('c');
q1.enQueue('d');
q1.enQueue('e');
q1.enQueue('f');
q1.traversing();
console.log('Team out: ', q1.deQueue());
q1.enQueue('g');
q1.traversing();
console.log('Team out: ', q1.deQueue());
console.log('Team out: ', q1.deQueue());
q1.enQueue('h');
console.log('Team out: ', q1.deQueue());
console.log('Team out: ', q1.deQueue());
console.log('Team out: ', q1.deQueue());
q1.traversing();
q1.clear();
q1.traversing();

Source code see https://github.com/Q-Angelo/project-training/tree/master/algorithm/queue-ring.js

summary

The above is the explanation of queue. At first, it explains how to apply queue in JavaScript. At the same time, it uses API function provided by JavaScript array to realize priority queue. Finally, it introduces how to implement a ring queue from scratch. This is the key point. Through the example of ring queue, we can also help you understand it. What is the basic implementation mechanism of the queue? Look at the suggestion of circular queue that you don't understand several times. In a word, do more and practice more.

Recommend two books I read in learning data structures Learning JavaScript Data Structure and Algorithms (2nd Edition),Graphical data structures use Python Of course, there are other better resources for your reference.