隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。

隊(duì)列介紹

隊(duì)列遵循FIFO（First In First Out，先進(jìn)先出）原則的一組有序的項(xiàng)。

隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。

隊(duì)列有基本隊(duì)列，還有其他修改版本的隊(duì)列，比如：優(yōu)先隊(duì)列、循環(huán)隊(duì)列。

基本隊(duì)列

基本隊(duì)列是隊(duì)列的基本存儲(chǔ)結(jié)構(gòu)，它是運(yùn)算受限制的基本表(線性表)。建立基本隊(duì)列結(jié)構(gòu)必須為其靜態(tài)分配或動(dòng)態(tài)申請(qǐng)一片連續(xù)的存儲(chǔ)空間，并設(shè)置兩個(gè)指針進(jìn)行管理。一個(gè)是隊(duì)頭指針front，它指向隊(duì)頭元素；另一個(gè)是隊(duì)尾指針rear，它指向下一個(gè)入隊(duì)元素的存儲(chǔ)位置，如圖所示。

20190815132004421.png

• 初始化：數(shù)組的front和rear都指向0。
• 入隊(duì)：隊(duì)不滿，數(shù)組不越界，先隊(duì)尾位置傳值，再隊(duì)尾下標(biāo)+1。
• 出隊(duì)：隊(duì)不空，先取隊(duì)頭位置元素，在隊(duì)頭+1。

基本隊(duì)列的實(shí)現(xiàn)

創(chuàng)建隊(duì)列后需要為其定義一些方法，一般來說隊(duì)列包含以下方法：

• enqueue(element)：向隊(duì)的尾部添加一個(gè)新的項(xiàng)
• dequeue()：移除隊(duì)列第一項(xiàng)，并返回被移除的元素
• front()：返回隊(duì)列第一項(xiàng)，隊(duì)列不做任何變動(dòng)
• isEmpty()：如果隊(duì)列中沒有任何元素返回true，否則返回false
• size()：返回隊(duì)列包含的元素個(gè)數(shù)

具體實(shí)現(xiàn)：

function Queue() {
  let items = []
  // 向隊(duì)列的尾部添加新元素
  this.enqueue = function (element) {
    items.push(element)
  }
  // 遵循先進(jìn)先出原則，從隊(duì)列的頭部移除元素
  this.dequeue = function () {
    return items.shift()
  }
  // 返回隊(duì)列最前面的項(xiàng)
  this.front = function () {
    return items[0]
  }
  // 返回隊(duì)列是否為空
  this.isEmpty = function () {
    return items.length === 0
  }
  // 返回隊(duì)列的長度
  this.size = function () {
    return items.length
  }
  // 打印隊(duì)列，方便觀察
  this.print = function () {
    console.log(items.toString())
  }
}

var queue = new Queue();
    queue.enqueue('hello');
    queue.enqueue('world');
    queue.enqueue('php');
    queue.enqueue('javascript');
    queue.enqueue('node.js');
    console.log(queue.isEmpty());    // false
    console.log(queue.print());      //hello,world,php,javascript,node.js 
    console.log(queue.size());       //5
    console.log(queue.front());      //hello

es6實(shí)現(xiàn)Queue

用es6的class語法實(shí)現(xiàn)Queue類，用WeakMap保存私用屬性items，并用閉包返回Queue類，來看具體實(shí)現(xiàn)：

let Queue = (function () {
  let items = new WeakMap
  class Queue {
    constructor () {
      items.set(this, [])
    }
    enqueue (element) {
      let q = items.get(this)
      q.push(element)
    }
    dequeue () {
      let q = items.get(this)
      return q.shift()
    }
    front () {
      let q = items.get(this)
      return q[0]
    }
    isEmpty () {
      let q = items.get(this)
      return q.length === 0
    }
    size () {
      let q = items.get(this)
      return q.length
    }
    print () {
      let q = items.get(this)
      console.log(q.toString())
    }
  }
  return Queue
})()

不足：每個(gè)空間域只能利用一次。造成空間浪費(fèi)。并且非常容易越界！

優(yōu)先隊(duì)列

優(yōu)先隊(duì)列是基本隊(duì)列的修改版本，元素的添加和移除是基于優(yōu)先級(jí)的。一個(gè)現(xiàn)實(shí)例子是，在銀行排隊(duì)辦業(yè)務(wù)的順序。VIP客戶的優(yōu)先級(jí)要高于普通客戶的。另一個(gè)例子是醫(yī)院的急診科候診室。醫(yī)生會(huì)優(yōu)先處理病情比較嚴(yán)重的患者。通常，護(hù)士會(huì)鑒別分類，根據(jù)患者病情的嚴(yán)重程度放號(hào)。

實(shí)現(xiàn)一個(gè)優(yōu)先隊(duì)列，有兩種選項(xiàng)：

• 設(shè)置優(yōu)先級(jí)，然后在正確的位置添加元素。（優(yōu)先添加，正常出隊(duì)）
• 用入列操作添加元素，然后按照優(yōu)先級(jí)移除它們。（正常添加，優(yōu)先出隊(duì)）

function PriorityQueue() {
        var items = [];
        //需要插入隊(duì)列的元素（該元素為對(duì)象，包括值和優(yōu)先級(jí)）
        function QueueElement(element, priority) {
            this.element = element;
            this.priority = priority;
        }

        //插入元素到隊(duì)列中的方法
        this.enqueue = function (element, priority) {
            //需要插入隊(duì)列的元素
            var queueElement = new QueueElement(element, priority);

            if(this.isEmpty()) {
                //當(dāng)隊(duì)列為空時(shí)，直接往隊(duì)列中添加元素
                items.push(queueElement);
            }else{
                //當(dāng)隊(duì)列不為空時(shí)，遍歷隊(duì)列中的元素，當(dāng)需要添加的元素的優(yōu)先級(jí)小于（隊(duì)列中）當(dāng)前元素的優(yōu)先級(jí)，就把該元素插入到當(dāng)前元素之前
                var added = false;
                for(var i = 0; i < items.length; i++){
                    if(queueElement.priority < items[i].priority) {
                        items.splice(i, 0, queueElement);
                        added = true;
                        break;//終止隊(duì)列循環(huán)
                    }
                }
                //當(dāng)需要添加的元素的優(yōu)先級(jí)比隊(duì)列中任何一個(gè)元素的優(yōu)先級(jí)都要高時(shí)，把該元素插入到隊(duì)列的末尾
                if(!added){
                    items.push(queueElement);
                }
            }
        }
        //查看隊(duì)列是否為空，如果為空，返回true；否則返回false
        this.isEmpty = function() {
            return items.length == 0;
        }    
        //查看隊(duì)列
        this.print = function() {
            return items;
        }        
    }

    var priorityQueue = new PriorityQueue();
    priorityQueue.enqueue('dee', 10);
    priorityQueue.enqueue('Learning', 2);
    priorityQueue.enqueue('JavaScript', 8);
    priorityQueue.enqueue('Algorithms', 20);
    priorityQueue.enqueue('Data Structures', 20);

    console.log(priorityQueue.print());

入隊(duì)時(shí)如果隊(duì)列為空直接加入隊(duì)列，否則進(jìn)行比較，priority小的優(yōu)先級(jí)高，優(yōu)先級(jí)越高放在隊(duì)列的越前面.

循環(huán)隊(duì)列

針對(duì)上述的問題。循環(huán)隊(duì)列可以有效的內(nèi)存重復(fù)利用。

數(shù)組實(shí)現(xiàn)的循環(huán)隊(duì)列就是在邏輯上稍作修改。我們假設(shè)(約定)數(shù)組的最后一位的下一個(gè)index是首位。因?yàn)槲覀冴?duì)列中只需要front和tail兩個(gè)指標(biāo)。不需要數(shù)組的實(shí)際地址位置相關(guān)數(shù)據(jù)。和它無關(guān)。所以我們就只需要考慮尾部的特殊操作即可。

• 初始化：數(shù)組的front和rear都指向0.
• 入隊(duì)：隊(duì)不滿，先隊(duì)尾位置傳值，再rear=(rear + 1) % maxsize;
• 出隊(duì)：隊(duì)不空，先取隊(duì)頭位置元素，front=(front + 1)%maxsize;
• 是否為空：return rear == front;
• 大?。簉eturn (rear+maxsize-front)%maxsize;

• 有幾點(diǎn)需要注意的，指標(biāo)相加如果遇到最后需要轉(zhuǎn)到頭的話?？梢耘袛嗍欠竦綌?shù)組末尾位置。也可以直接+1求余。其中maxsize是數(shù)組實(shí)際大小。

  
  
  20190816002656435.png

循環(huán)隊(duì)列的一個(gè)例子就是擊鼓傳花的游戲。在這個(gè)游戲中，孩子們圍成一個(gè)圓圈，把花盡快的傳遞給旁邊的人。某一時(shí)刻傳花停止，這個(gè)時(shí)候花在誰手里，誰就退出圓圈結(jié)束游戲。重復(fù)這個(gè)過程，直到只剩一個(gè)孩子（勝者）。
另一個(gè)類似的案例是，約瑟夫環(huán)問題。

//基本隊(duì)列Queue同上

    //循環(huán)隊(duì)列
    //@param Obj nameList 名單
    //@param Int num 指定的傳遞次數(shù)
    function hotPotato(nameList, num) {

        var queue = new Queue();

        //把名單插入隊(duì)列
        for(var i = 0; i < nameList.length; i++) {
            queue.enqueue(nameList[i]);
        }

        //淘汰者的名字初始值
        var eliminated = '';

        //當(dāng)隊(duì)列里的人數(shù)大于1人時(shí)，繼續(xù)傳遞
        while(queue.size() > 1) {
            for(var i = 0; i < num; i++) {
                //每次把隊(duì)列頭部彈出的隊(duì)員再次插入隊(duì)列的尾部，行程一個(gè)循環(huán)隊(duì)列
                queue.enqueue(queue.dequeue());
            }
            //當(dāng)循環(huán)停止時(shí)，即到了指定的傳遞次數(shù)時(shí)，彈出隊(duì)列頭部的隊(duì)員
            eliminated = queue.dequeue();
            console.log(eliminated + '被淘汰');
        }

        //當(dāng)隊(duì)列中只剩下一個(gè)隊(duì)員時(shí)，即是勝利者
        return queue.dequeue();
    }

    var names = ['dee', 'death mask', 'saga', 'mu', 'alexis'];
    var winner = hotPotato(names, 7);
    console.log('勝利者是' + winner);

小結(jié)

這篇文章主要對(duì)隊(duì)列做了簡單介紹，對(duì)隊(duì)列以及相關(guān)應(yīng)用做了簡單實(shí)現(xiàn)。如果有錯(cuò)誤或不嚴(yán)謹(jǐn)?shù)牡胤?，歡迎批評(píng)指正，如果喜歡，歡迎點(diǎn)贊。