摘要：初始化隊列初始化一個存儲隊列中元素的數據結構，如果未傳入默認賦值空數組，傳入需先校驗類型是否正確。頭等艙和商務艙乘客的優先級要高于經濟艙乘客。在有些國家，老年人和孕婦或帶小孩的婦女登機時也享有高于其他乘客的優先級。

有一天，當回顧自己走過的路時，你會發現這些奮斗不息的歲月，才是最美好的人生。——弗洛伊德

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

隊列對應到生活場景中有很多例子，例如，我們去火車站窗口購票總要排隊，先排隊的人先購票，有新的人來了則在隊尾排隊等待前面的完成了依次購票。另外我們的訂單超時隊列、活動搶購先到先得等等，隊列在生活中應用很廣泛。

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

JavaScript 中提供的數組功能即可實現一個簡單的隊列，使用起來也很方便，熟悉相關 API 即可，下面我們來看下基于 JS 數組的入隊、出隊過程實現。

以上圖片展示了隊列的初始化、入隊、出隊過程，下面我們采用 JavaScript 原型鏈的方式實現。

初始化隊列

初始化一個存儲隊列中元素的數據結構，如果未傳入默認賦值空數組，傳入需先校驗類型是否正確。

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

    this.elements = elements || [];
}

隊列添加元素

實現一個 enQueue 方法，向隊列添加元素，注意只能是隊列尾部添加，使用 JavaScript 數組中的 push 方法。

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

隊列移除元素

實現一個 deQueue 方法，向隊列頭部彈出元素，使用 JavaScript 數組中的 shift 方法。

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

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

優先隊列，元素的添加、刪除是基于優先級進行的。一個現實的例子就是機場登機的順序。頭等艙和商務艙乘客的優先級要高于經濟艙乘客。在有些國家，老年人和孕婦（或帶小孩的婦女）登機時也享有高于其他乘客的優先級。

優先隊列對應到我們生活場景中也有很多例子，例如我們去銀行辦理業務，一般都會排號先到的先辦理，但是呢，還會有 VIP 會員優先辦理，又或者去火車站窗口上購票也會有提示軍人可以優先辦理等等

實現步驟

核心實現繼 JavaScript 數組實現隊列的例子，對入隊函數進行改造如下所示：

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

如果隊列為空直接入隊

如果找到一個比 priority 優先級大的元素，插入新元素，這里使用到了 JS 數組中的 splice 方法

最后如果隊列中的所有元素的優先級都小于 priority，則直接在隊列尾部入隊

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

代碼示例

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

運行測試

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

圖例展示

下面以圖例的形式展示以上優先隊列程序的運行過程

以上是將優先級最小的元素放置于隊列前面，稱之為最小優先隊列，最大優先隊列的實現則反之。源碼參見 https://github.com/Q-Angelo/project-training/tree/master/algorithm/queue-priority.js

循環隊列有些地方也稱之為環形隊列，其本身是一種環形結構的隊列，相較于普通隊列有個好處是第一個元素出隊之后，剩下元素無需依次向前移位，充分利用了向量空間，在以下介紹中給出了完整的實現過程。

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

ES6 實現循環隊列

以下采用 EcameScript 6 的 Class 寫法，實現一個環形隊列，需要做哪些點呢？以下列出需要實現的功能點：

創建隊列，初始化隊列空間

檢查隊列是否為空

檢查隊列是否溢出

入隊

出隊

隊列長度

清空隊列

銷毀隊列，內存空間也將釋放

隊列遍歷輸出

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

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

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

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

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

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

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

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

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

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

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

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

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

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