摘要：初始化隊(duì)列初始化一個(gè)存儲(chǔ)隊(duì)列中元素的數(shù)據(jù)結(jié)構(gòu)，如果未傳入默認(rèn)賦值空數(shù)組，傳入需先校驗(yàn)類型是否正確。頭等艙和商務(wù)艙乘客的優(yōu)先級(jí)要高于經(jīng)濟(jì)艙乘客。在有些國家，老年人和孕婦或帶小孩的婦女登機(jī)時(shí)也享有高于其他乘客的優(yōu)先級(jí)。

有一天，當(dāng)回顧自己走過的路時(shí)，你會(huì)發(fā)現(xiàn)這些奮斗不息的歲月，才是最美好的人生。——弗洛伊德

隊(duì)列，英文 First In First Out 簡稱 FIFO，遵從先進(jìn)先出的原則，與 “棧” 相反，在隊(duì)列的尾部添加元素，在隊(duì)列的頭部刪除元素，如果隊(duì)列中沒有元素就稱為空隊(duì)列。

隊(duì)列對(duì)應(yīng)到生活場景中有很多例子，例如，我們?nèi)セ疖囌敬翱谫徠笨傄抨?duì)，先排隊(duì)的人先購票，有新的人來了則在隊(duì)尾排隊(duì)等待前面的完成了依次購票。另外我們的訂單超時(shí)隊(duì)列、活動(dòng)搶購先到先得等等，隊(duì)列在生活中應(yīng)用很廣泛。

作者簡介：五月君，Nodejs Developer，熱愛技術(shù)、喜歡分享的 90 后青年，公眾號(hào)「Nodejs技術(shù)棧」，Github 開源項(xiàng)目 https://www.nodejs.red

JavaScript 中提供的數(shù)組功能即可實(shí)現(xiàn)一個(gè)簡單的隊(duì)列，使用起來也很方便，熟悉相關(guān) API 即可，下面我們來看下基于 JS 數(shù)組的入隊(duì)、出隊(duì)過程實(shí)現(xiàn)。

以上圖片展示了隊(duì)列的初始化、入隊(duì)、出隊(duì)過程，下面我們采用 JavaScript 原型鏈的方式實(shí)現(xiàn)。

初始化隊(duì)列

初始化一個(gè)存儲(chǔ)隊(duì)列中元素的數(shù)據(jù)結(jié)構(gòu)，如果未傳入默認(rèn)賦值空數(shù)組，傳入需先校驗(yàn)類型是否正確。

function QueueStudy(elements) {
    if (elements && !(elements instanceof Array)) {
        throw new Error("必須為數(shù)組格式！");
    }

    this.elements = elements || [];
}

隊(duì)列添加元素

實(shí)現(xiàn)一個(gè) enQueue 方法，向隊(duì)列添加元素，注意只能是隊(duì)列尾部添加，使用 JavaScript 數(shù)組中的 push 方法。

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

隊(duì)列移除元素

實(shí)現(xiàn)一個(gè) deQueue 方法，向隊(duì)列頭部彈出元素，使用 JavaScript 數(shù)組中的 shift 方法。

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

通過 JavaScript 數(shù)組實(shí)現(xiàn)是很簡單的，源碼參見 https://github.com/Q-Angelo/project-training/tree/master/algorithm/queue-js.js

優(yōu)先隊(duì)列，元素的添加、刪除是基于優(yōu)先級(jí)進(jìn)行的。一個(gè)現(xiàn)實(shí)的例子就是機(jī)場登機(jī)的順序。頭等艙和商務(wù)艙乘客的優(yōu)先級(jí)要高于經(jīng)濟(jì)艙乘客。在有些國家，老年人和孕婦（或帶小孩的婦女）登機(jī)時(shí)也享有高于其他乘客的優(yōu)先級(jí)。

優(yōu)先隊(duì)列對(duì)應(yīng)到我們生活場景中也有很多例子，例如我們?nèi)ャy行辦理業(yè)務(wù)，一般都會(huì)排號(hào)先到的先辦理，但是呢，還會(huì)有 VIP 會(huì)員優(yōu)先辦理，又或者去火車站窗口上購票也會(huì)有提示軍人可以優(yōu)先辦理等等

實(shí)現(xiàn)步驟

核心實(shí)現(xiàn)繼 JavaScript 數(shù)組實(shí)現(xiàn)隊(duì)列的例子，對(duì)入隊(duì)函數(shù)進(jìn)行改造如下所示：

聲明 queueElement 對(duì)象，包含了要添加到隊(duì)列的元素

如果隊(duì)列為空直接入隊(duì)

如果找到一個(gè)比 priority 優(yōu)先級(jí)大的元素，插入新元素，這里使用到了 JS 數(shù)組中的 splice 方法

最后如果隊(duì)列中的所有元素的優(yōu)先級(jí)都小于 priority，則直接在隊(duì)列尾部入隊(duì)

另外打印輸出的方法也做了簡單修改

代碼示例

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(" | "));
}

運(yùn)行測試

const queue = new PriorityQueue();
queue.enQueue("普通會(huì)員1", 5);
queue.enQueue("普通會(huì)員2", 10);
queue.print() // 普通會(huì)員1 | 普通會(huì)員2
queue.enQueue("VIP會(huì)員1", 3);
queue.print() // VIP會(huì)員1 | 普通會(huì)員1 | 普通會(huì)員2
queue.enQueue("VIP會(huì)員2", 3);
queue.print() // VIP會(huì)員1 | VIP會(huì)員2 | 普通會(huì)員1 | 普通會(huì)員2
queue.deQueue();
queue.print() // VIP會(huì)員2 | 普通會(huì)員1 | 普通會(huì)員2

圖例展示

下面以圖例的形式展示以上優(yōu)先隊(duì)列程序的運(yùn)行過程

以上是將優(yōu)先級(jí)最小的元素放置于隊(duì)列前面，稱之為最小優(yōu)先隊(duì)列，最大優(yōu)先隊(duì)列的實(shí)現(xiàn)則反之。源碼參見 https://github.com/Q-Angelo/project-training/tree/master/algorithm/queue-priority.js

循環(huán)隊(duì)列有些地方也稱之為環(huán)形隊(duì)列，其本身是一種環(huán)形結(jié)構(gòu)的隊(duì)列，相較于普通隊(duì)列有個(gè)好處是第一個(gè)元素出隊(duì)之后，剩下元素?zé)o需依次向前移位，充分利用了向量空間，在以下介紹中給出了完整的實(shí)現(xiàn)過程。

在設(shè)計(jì)環(huán)形隊(duì)列時(shí)即可順時(shí)針也可逆時(shí)針兩個(gè)方向進(jìn)行實(shí)現(xiàn)，在入隊(duì)時(shí)可根據(jù) (tail % capacity) 規(guī)則，進(jìn)行隊(duì)尾添加元素，tail 表示隊(duì)尾的指針，capacity 表示容量，出隊(duì)同樣以（head % capacity）規(guī)則操作，head 表示隊(duì)頭指針，下面以長度為 6 的隊(duì)列進(jìn)行圖文形式說明下實(shí)現(xiàn)過程。

ES6 實(shí)現(xiàn)循環(huán)隊(duì)列

以下采用 EcameScript 6 的 Class 寫法，實(shí)現(xiàn)一個(gè)環(huán)形隊(duì)列，需要做哪些點(diǎn)呢？以下列出需要實(shí)現(xiàn)的功能點(diǎn)：

創(chuàng)建隊(duì)列，初始化隊(duì)列空間

檢查隊(duì)列是否為空

檢查隊(duì)列是否溢出

入隊(duì)

出隊(duì)

隊(duì)列長度

清空隊(duì)列

銷毀隊(duì)列，內(nèi)存空間也將釋放

隊(duì)列遍歷輸出

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

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

        this.capacity = capacity; // 初始化容量
        this[Init]();
    }

    /**
     * 清空隊(duì)列，內(nèi)存保留
     */
    clear() {
        this[Init]()
    }

    [Init]() {
        this.queue = new Array(this.capacity); // 初始化隊(duì)列內(nèi)存空間
        this.queueLen = 0; // 初始化隊(duì)列元素
        this.head = 0; // 隊(duì)頭
        this.tail = 0; // 尾部
    }

    /**
     * 隊(duì)列是否為空
     */
    isEmpty() {
        return this.queueLen === 0 ? true : false;
    }

    /**
     * 隊(duì)列是否溢出
     */
    isOverflow() {
        return this.queueLen === this.capacity
    }

    /**
     * 入隊(duì)
     */
    enQueue(element) {
        if (this.isOverflow()) {
            return false;
        }

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

    /**
     * 出隊(duì)
     */
    deQueue() {
        if (this.isEmpty()) {
            throw new Error("隊(duì)列為空");
        } else {
            const element = this.queue[this.head];
            this.head++; // 隊(duì)頭位置移動(dòng)
            this.head = this.head % this.capacity;
            this.queueLen--;
            return element;
        }
    }

    /**
     * 隊(duì)列長度
     */
    len() {
        return this.queueLen;
    }

    /**
     * 銷毀隊(duì)列，內(nèi)存回收
     */
    destroy() {
        this.queue = null;
    }

    /**
     * 隊(duì)列元素遍歷
     */
    traversing() {
        console.log("------------traversing start------------");
        
        for (let i=this.head; i
運(yùn)行測試
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("出隊(duì): ", q1.deQueue());
q1.enQueue("g");
q1.traversing();
console.log("出隊(duì): ", q1.deQueue());
console.log("出隊(duì): ", q1.deQueue());
q1.enQueue("h");
console.log("出隊(duì): ", q1.deQueue());
console.log("出隊(duì): ", q1.deQueue());
console.log("出隊(duì): ", q1.deQueue());
q1.traversing();
q1.clear();
q1.traversing();

源碼參見 https://github.com/Q-Angelo/project-training/tree/master/algorithm/queue-ring.js
總結(jié)
以上就是隊(duì)列的講解，最開始講解了在 JavaScript 中如何應(yīng)用隊(duì)列，同時(shí)也使用 JavaScript 數(shù)組提供的 API 功能實(shí)現(xiàn)了優(yōu)先隊(duì)列，最后介紹了從零開始如何實(shí)現(xiàn)一個(gè)環(huán)形隊(duì)列，這個(gè)是重點(diǎn)，通過環(huán)形隊(duì)列這個(gè)例子也可以幫助大家理解隊(duì)列的基本實(shí)現(xiàn)機(jī)制是怎么樣的，對(duì)環(huán)形隊(duì)列這塊不理解的建議多看幾遍，總之多動(dòng)手、多實(shí)踐。
推薦我在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)中看的兩本書 學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（第2版）、圖解數(shù)據(jù)結(jié)構(gòu)使用 Python 當(dāng)然也不乏有其它更好的資源，供大家學(xué)習(xí)參考。