摘要：隊列是遵行先進(jìn)先出原則的一組有序的項。優(yōu)先隊列是默認(rèn)隊列的變種，它的元素的添加和移除是基于優(yōu)先級的。如此循環(huán)，直至隊列的長度等于，返回勝者行。同時，還掌握了很著名的優(yōu)先隊列循環(huán)隊列這兩種結(jié)構(gòu)。

《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》讀書筆記。

隊列是遵行FIFO(First In First Out, 先進(jìn)先出)原則的一組有序的項。隊列再尾部添加新元素，并從頂部移除元素。

在現(xiàn)實中，最常見的隊列的例子就是排隊。

1.創(chuàng)建隊列

現(xiàn)在，我們來創(chuàng)建一個類來表示一個隊列。先從最基本的聲明類開始：

function Queue(){
    // 這里是屬性和方法
}

首先，需要一個用戶存儲隊列中元素的數(shù)據(jù)結(jié)構(gòu)，我們可以使用數(shù)組。

var items = [];

接下來，聲明一些隊列可用的方法：

enqueue(element(s))：進(jìn)隊，向隊列尾部添加一個（或多個）新項。

dequeue()：移除隊列的第一項，并返回被移除的元素。

front()：返回隊列中第一個元素-最先被添加，也會是最先被移除的元素。（只返回，不移除）。

isEmpty()：如果隊列為空，返回true，否則，返回false。

size()：返回隊列的長度。

首先，我們來實現(xiàn)enqueue的方法，這個方法負(fù)責(zé)向隊列中添加新元素。只能是添加到隊列的尾部。

    this.enqueue = function(element) {
        items.push(element);
    }

接下來要實現(xiàn)的是dequeue方法，這個方法負(fù)責(zé)從隊列移除項。由于隊列遵循的是先進(jìn)先出原則，所以最先移除的就是最先添加的，元素是排在數(shù)組的第一位。

    this.dequeue = function() {
        return items.shift();
    }

只有enqueue方法和dequeue方法可以添加和移除元素，這樣就確保了Queue類遵循先進(jìn)先出原則。
現(xiàn)在來為我們的類實現(xiàn)一些額外的輔助方法：

    // front()：返回隊列中第一個元素
    this.front = function() {
        return items[0];
    }
    
    // isEmpty()：如果隊列為空，返回true，否則，返回false
    this.isEmpty = function() {
        return items.length === 0;
    }
    
    // size()：返回隊列的長度
    this.size = function() {
        return items.length;
    }

完成，我們的Queue類實現(xiàn)好了，現(xiàn)在來看看Queue完整的實現(xiàn)是怎么樣的：

function Queue() {
    var items = [];
    
    this.enqueue = function(element) {
        items.push(element);
    }
    
    this.dequeue = function() {
        return items.shift();
    }
    
    this.front = function() {
        return items[0];
    }
    
    this.isEmpty = function() {
        return items.length === 0;
    }
    
    this.clear = function() {
        items = [];
    }
    
    this.size = function() {
        return items.length;
    }
    
    this.print = function() {
        console.log(items.toString());
    }
}

2.使用Queue類

var queue = new Queue();
console.log(queue.isEmpty()); // 輸出 true
queue.enqueue("John");        // 添加元素 John
queue.enqueue("Jam");         // 添加元素 Jam
queue.enqueue("Camila");      // 添加元素 Camila
queue.print();
console.log(queue.size);      // 輸出 3
console.log(queue.isEmpty);   // 輸出 false
queue.dequeue();              // 移除元素
queue.dequeue();            
queue.print();

運(yùn)行上面的代碼，我們可以看出，我們已經(jīng)實現(xiàn)了隊列，遵循了先入先出原則。

3.優(yōu)先隊列

上面我們已經(jīng)實現(xiàn)了一個隊列，現(xiàn)在，逐步深入，我們來看看什么是優(yōu)先隊列。

優(yōu)先隊列是默認(rèn)隊列的變種，它的元素的添加和移除是基于優(yōu)先級的。一個現(xiàn)實的例子就是醫(yī)院的（急診科）候診室。醫(yī)生會優(yōu)先處理病情比較嚴(yán)重的患者。

實現(xiàn)一個優(yōu)先隊列，有兩種選擇：設(shè)置優(yōu)先級，然后在正確的位置添加元素；或者用默認(rèn)入列操作添加元素，任何按照優(yōu)先級移除它們。下面，我們將會在正確的位置添加元素，任何用默認(rèn)你的出列操作。

    function PriorityQueue() {
        var items = [];
        
        // {1}
        function QueueElement(element, priority) {
            this.element = element;
            this.priority = priority;
        }
        
        this.enqueue = function(element, priority) {
            var queueElement = new QueueElement(element, priority);
            
            if(this.isEmpty()) {
                items.push(queueElement);  // {2}
            } else {
                var added = false;
                for(var i = 0; i < items.length; i++) {
                    if(queueElement.priority < items.[i].priority) {
                        items.splice(i, 0, queueElement);    // {3}
                        added = true;
                        break;
                    }
                }
                if(!added) {    // {4}
                    items.push(queueElement);
                }
            }
        }
        
        // 其他方法與默認(rèn)隊列一樣
    }

我們創(chuàng)建了一個特殊的元素(行{1})，這個元素包含了要添加到隊列的元素及其優(yōu)先級。

如果隊列為空，則直接將元素入列(行{2})。否則，就要進(jìn)行比較。當(dāng)找到一個比要添加的元素的priority值更大(優(yōu)先級更低)時，就將元素插入到它之前(行{3})。

如果要添加的元素的priority指大于任何已有的元素，則直接將其添加到隊列的末尾(行{4})。

var priorityQueue = new PriorityQueue();
priorityQueue.enqueue("John", 2);
priorityQueue.enqueue("Jam", 1);
priorityQueue.enqueue("Sam", 1);
priorityQueue.print();

至此，我們已經(jīng)實現(xiàn)了優(yōu)先隊列，下面，將再介紹一種隊列——循環(huán)隊列

4.循環(huán)隊列——擊鼓傳花

循環(huán)隊列是默認(rèn)隊列的另一種修改版，什么是循環(huán)隊列呢？舉個現(xiàn)實中的例子，記得小時候玩過的傳花游戲嗎？
幾個孩子圍成一圈，開始擊鼓了，孩子就把花盡快地傳遞給旁邊的人，某一時刻鼓聲停止了，傳花也就停止了，這個時候花落在誰手上，誰就被淘汰。鼓聲響起，繼續(xù)傳花，如此循環(huán)，直至只剩下一個孩子，即勝者。

function hotPotato(namelist, num) {
    var queue = new Queue();
    for (var i = 0; i < namelist.length; i++) {     // {1}
        queue.enqueue(namelist[i]);
    }
    var eliminated = "";
    while (queue.size() > 1) {                 // {2}
        for (var i = 0; i < num; i++) {
            queue.enqueue(queue.dequeue());    // {3}
        }
        eliminated = queue.dequeue();    // {4}
        console.log(eliminated + "在擊鼓傳花游戲中被淘汰");
    }
    return queue.dequeue();    // {5}
}
var names = ["john", "jack", "camila", "ingrid", "carl"];
var winner = hotPotato(names, 7);
console.log("勝利者： " + winner);      //john

首先，先把名單添加到隊列里面(行{1})。

當(dāng)隊列的的長度大于1的時候(行{2})，根據(jù)指定的一個數(shù)字(num)迭代隊列，將隊列的頭一個移除并將其添加到隊尾(行{3})。

一旦傳遞次數(shù)達(dá)到給定的數(shù)字，則刪除此時的隊列第一項(行{4})，即拿著花的那個人，他將被淘汰。

如此循環(huán)，直至隊列的長度等于1，返回勝者(行{5})。

5.小結(jié)

通過這篇文章的介紹，我們學(xué)會了如何用數(shù)組構(gòu)造出隊列的類。同時，還掌握了很著名的優(yōu)先隊列、循環(huán)隊列這兩種結(jié)構(gòu)。

附：
JavaScript數(shù)據(jù)結(jié)構(gòu)和算法系列：
JS 棧

JavaScript設(shè)計模式系列：
JavaScript設(shè)計模式之策略模式
JavaScript設(shè)計模式之發(fā)布-訂閱模式（觀察者模式）-Part1