JavaScript數據結構——隊列的實現與應用

隊列與棧不同，它遵從先進先出（FIFO——First In First Out）原則，新添加的元素排在隊列的尾部，元素只能從隊列頭部移除。我們在前一篇文章中描述瞭如何用JavaScript來實現棧這種數據結構，這裡我們對應地來實現隊列。與棧的實現方式類似，唯一不同的是從隊列移除元素時取的是隊列頭 ...

　　隊列與棧不同，它遵從先進先出（FIFO——First In First Out）原則，新添加的元素排在隊列的尾部，元素只能從隊列頭部移除。

　　我們在前一篇文章中描述瞭如何用JavaScript來實現棧這種數據結構，這裡我們對應地來實現隊列。

function Queue() {
    let items = [];

    // 向隊列添加元素（一個或多個）
    this.enqueue = function (element) {
        if (element instanceof Array) items = items.concat(element);
        else items.push(element);
    };

    // 從隊列移除元素
    this.dequeue = function () {
        return items.shift();
    };

    // 返回隊列中的第一個元素
    this.front = function () {
        return items[0];
    };

    // 判斷隊列是否為空
    this.isEmpty = function () {
        return items.length === 0;
    };

    // 返回隊列的長度
    this.size = function () {
        return items.length;
    };

    // 清空隊列
    this.clear = function () {
        items = [];
    };

    // 列印隊列內的所有元素
    this.print = function () {
        console.log(items.toString());
    };
}

　　與棧的實現方式類似，唯一不同的是從隊列移除元素時取的是隊列頭部的元素（最先添加的），而棧則是取的頂部元素（最後添加的）。下麵是一些測試用例及返回結果：

let queue = new Queue();
console.log(queue.isEmpty()); // true

queue.enqueue('John');
queue.enqueue(['Jack', 'Camila']);
queue.print(); // John,Jack,Camila
console.log(queue.size()); // 3
console.log(queue.isEmpty()); // false
console.log(queue.front()); // John

console.log(queue.dequeue()); // John
queue.print(); // Jack,Camila

queue.clear();
queue.print(); //

　　註意，我們允許批量向隊列中添加元素，為此我們需要判斷enqueue方法的參數類型，如果參數是數組，則用concat()函數連接兩個數組，如果參數不是數組，則直接用push()函數將元素添加到隊列中。

　　與棧的實現方式一樣，這裡我們也同樣給出用ES6的WeakMap類來實現的隊列版本。

let Queue = (function () {
    const items = new WeakMap();

    class Queue {
        constructor() {
            items.set(this, []);
        }

        enqueue (element) {
            let q = items.get(this);
            if (element instanceof Array) items.set(this, q.concat(element));
            else q.push(element);
        };

        dequeue () {
            let q = items.get(this);
            return q.shift();
        };

        front () {
            return items.get(this)[0];
        };

        isEmpty () {
            return items.get(this).length === 0;
        };

        size () {
            return items.get(this).length;
        };

        clear () {
            items.set(this, []);
        };

        print () {
            console.log(items.get(this).toString());
        };
    }

    return Queue;
})();

　　這兩個版本的執行結果是一樣的，它們的區別我們在前一篇文章中已經提及過了，這裡不再贅述。

優先隊列

　　所謂優先隊列，顧名思義，就是說插入到隊列中的元素可以根據優先順序設置先後順序。優先順序越高位置越靠前，優先順序越低位置越靠後。假設優先順序用數字來表示，如果數字越小表示的優先順序越高，形成的隊列就稱之為最小優先隊列，反之則稱之為最大優先隊列。下麵是實現的代碼：

function PriorityQueue() {
    let items = [];

    // 向隊列添加元素（一個或多個）
    // 參數obj的數據格式：{element, priority}
    this.enqueue = function (obj) {
        if (obj instanceof Array) {
            for (let i = 0, ci; ci = obj[i]; i++) {
                this.enqueue(ci);
            }
        }
        else {
            let added = false;
            for (let i = 0, ci; ci = items[i]; i++) {
                // 最小優先順序，即將priority值小的元素插入到隊列的前面
                if (obj.priority < ci.priority) {
                    items.splice(i, 0, obj);
                    added = true;
                    break;
                }
            }

            // 如果元素沒有插入到隊列中，則預設加到隊列的尾部
            if (!added) items.push(obj);
        }
    };

    // 從隊列移除元素
    this.dequeue = function () {
        return items.shift();
    };

    // 返回隊列中的第一個元素
    this.front = function () {
        return items[0];
    };

    // 判斷隊列是否為空
    this.isEmpty = function () {
        return items.length === 0;
    };

    // 返回隊列的長度
    this.size = function () {
        return items.length;
    };

    // 清空隊列
    this.clear = function () {
        items = [];
    };

    // 列印隊列內的所有元素
    this.print = function () {
        items.forEach(function (item) {
            console.log(`${item.element} - ${item.priority}`);
        });
    };
}

　　可以看到，唯一有區別的只有enqueue方法。我們規定所有添加到優先隊列的元素都必須滿足{element, priority}這種JSON格式，以保證隊列中的每一個元素都有一個priority屬性來表示優先順序。如果要添加的元素的優先順序和隊列中已有元素的優先順序相同，仍然遵循隊列的先進先出原則。如果隊列中所有元素的優先順序比要添加的元素的優先順序都高，則將元素添加到隊列的末尾。我們將print()方法也做了一些調整，以方便查看輸出結果。

let queue = new PriorityQueue();
console.log(queue.isEmpty()); // true

queue.enqueue({element: 'John', priority: 2});
queue.enqueue([{element: 'Jack', priority: 1}, {element: 'Camila', priority: 1}]);
queue.print(); // Jack,Camila,John

　　由於John的優先順序比其它兩個低，所以它被排在了最後面。雖然Jack和Camila的優先順序相同，但是Jack是在Camila之前先插入到隊列中的，所以Jack排在了Camila之前，這也符合了我們的預期。

迴圈隊列

　　我們用一個小游戲“擊鼓傳花”來說明迴圈隊列在實際中的應用。

function hotPotato(nameList, num) {
    let queue = new Queue();

    for (let i = 0, ci; ci = nameList[i]; i++) {
        queue.enqueue(ci);
    }

    let eliminated = '';
    while(queue.size() > 1) {
        for (let i = 0; i < num; i ++) {
            queue.enqueue(queue.dequeue());
        }
        eliminated = queue.dequeue();
        console.log(`${eliminated} has been eliminated.`);
    }

    return queue.dequeue();
}

let names = ['John', 'Jack', 'Camila', 'Ingrid', "Carl"];
let winner = hotPotato(names, 7);
console.log(`The winner is: ${winner}`);

　　在這個游戲中，我們傳入由五個名字組成的數組，用來表示參加游戲的五個人，數字7表示每一輪要傳遞的次數。在每一個過程中，我們從隊列頭部取出一個元素加到隊列的尾部，當次數用完的時候，將隊列頭部的元素取出來，作為這一輪中被淘汰的人。讓我們來看一下具體的執行過程，一開始隊列中的順序是John, Jack, Camila, Ingrid, Carl，然後傳遞7次：

　　1. Jack, Camila, Ingrid, Carl, John

　　2. Camila, Ingrid, Carl, John, Jack

　　3. Ingrid, Carl, John, Jack, Camila

　　4. Carl, John, Jack, Camila, Ingrid

　　5. John, Jack, Camila, Ingrid, Carl

　　6. Jack, Camila, Ingrid, Carl, John

　　7. Camila, Ingrid, Carl, John, Jack

　　之後從隊列中取出的是Camila。反覆執行上述過程，直到隊列中的元素只剩一個，這個就是最後的贏家！

　　下麵是完整的執行結果：

Camila has been eliminated.
Jack has been eliminated.
Carl has been eliminated.
Ingrid has been eliminated.
The winner is: John

　　下一章我們繼續來看看如何用JavaScript來實現鏈表。