JavaScript隊(duì)列、優(yōu)先隊(duì)列與循環(huán)隊(duì)列

更新時(shí)間：2016年11月14日 11:05:31 作者：payson_tsung

這篇文章主要為大家詳細(xì)介紹了JavaScript隊(duì)列、優(yōu)先隊(duì)列與循環(huán)隊(duì)列的相關(guān)資料,具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

隊(duì)列是一種遵從先進(jìn)先出（FIFO）原則的有序集合
隊(duì)列在尾部添加新元素，從頂部移除元素

隊(duì)列的理解

隊(duì)列在我們生活中最常見(jiàn)的場(chǎng)景就是排隊(duì)了
隊(duì)列這個(gè)名字也已經(jīng)很通俗易懂了

和棧很像，這不過(guò)隊(duì)列是先入先出的數(shù)據(jù)結(jié)構(gòu)

隊(duì)列的前面是隊(duì)頭
隊(duì)列的后面是隊(duì)尾
出隊(duì)從隊(duì)頭出
入隊(duì)從隊(duì)尾入

隊(duì)列的創(chuàng)建

和棧類似，這里我就不就不啰嗦了
同樣需要實(shí)現(xiàn)一些功能
這里我類比生活中的排隊(duì)上廁所

向隊(duì)列中添加元素（進(jìn)入排隊(duì)的隊(duì)伍中）
移除隊(duì)頭元素（隊(duì)伍最前面的人出隊(duì)進(jìn)入廁所）
查看隊(duì)頭元素（查看隊(duì)伍最前面的人）
判斷隊(duì)列是否為空（看看隊(duì)伍中有沒(méi)有人）
移除隊(duì)伍全部元素（廁所炸了，都散了吧）
查看棧里元素個(gè)數(shù)（查看排隊(duì)的有多少人）

于是我們可以創(chuàng)建一個(gè)完整隊(duì)列實(shí)現(xiàn)，同樣是利用我們的數(shù)組實(shí)現(xiàn)
數(shù)組頭就是隊(duì)列頭

function Queue() {
  var items = [];
  this.enqueue = function (ele) {
    items.push(ele);
  };//入隊(duì)
  this.dequeue = function () {
    return items.shift();
  };//出隊(duì)
  this.front = function () {
    return items[0];
  };//查看隊(duì)頭元素
  this.isEmpty = function () {
    return items.length === 0;
  };//判斷隊(duì)列是否為空
  this.size = function () {
    return items.length;
  };//隊(duì)列大小
  this.clear = function () {
    items = [];
  };//清空隊(duì)列
  this.print = function () {
    console.log(items.toString());
  };//打印隊(duì)列
}
var queue = new Queue(); //聲明隊(duì)列的實(shí)例

隊(duì)列的使用

下面我們就用這個(gè)隊(duì)列簡(jiǎn)單模擬排隊(duì)

var queue = new Queue();
console.log("隊(duì)列是否為空： " + queue.isEmpty());
queue.enqueue('Mr.A');
queue.enqueue('Mr.B');
queue.enqueue('Mr.C');
console.log("當(dāng)前隊(duì)列：");
queue.print();
console.log("出隊(duì)的人： " + queue.dequeue());
console.log("當(dāng)前隊(duì)列：");
queue.print();

控制臺(tái)打?。?/p>

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

在我們排隊(duì)上廁所的時(shí)候，來(lái)了一位擁有VIP會(huì)員卡的朋友，插到了隊(duì)伍的最前面
過(guò)了一會(huì)兒又來(lái)了一位擁有SVIP會(huì)員卡的朋友，插到了VIP的前面

雖然這個(gè)比喻可能不恰當(dāng)，但是生活中可能存在有優(yōu)先級(jí)的隊(duì)列
優(yōu)先級(jí)高的人可以查到優(yōu)先級(jí)低的人前面

這就是循環(huán)隊(duì)列

如果優(yōu)先值小的元素放到隊(duì)列的前面，這叫做最小優(yōu)先隊(duì)列
反之優(yōu)先值大的元素放到隊(duì)列的前面，這叫做最大優(yōu)先隊(duì)列
但其實(shí)他們兩個(gè)僅僅是一個(gè)判斷的改變，實(shí)現(xiàn)方式是一樣的
優(yōu)先隊(duì)列較普通隊(duì)列的區(qū)別也就是入隊(duì)要判斷優(yōu)先級(jí)，并且需要對(duì)我們的元素進(jìn)行處理，其他方法不變
這處理也就是把元素包裝為一個(gè)擁有優(yōu)先級(jí)的對(duì)象
既然所有對(duì)象都有著同樣的屬性，那我們毫無(wú)疑問(wèn)就應(yīng)該使用工廠構(gòu)建
我們可以稍微修改一下我們的隊(duì)列類
來(lái)實(shí)現(xiàn)一個(gè)最小優(yōu)先隊(duì)列

function PriorityQueue() {
  var items = [];
  function QueEle(ele, priority){ //封裝我們的元素為一個(gè)對(duì)象
    this.ele = ele; //元素
    this.priority = priority; //優(yōu)先級(jí)
  }
  this.enqueue = function (ele, priority) {
    var queObj = new QueEle(ele, priority); //創(chuàng)建隊(duì)列元素對(duì)象
    if(this.isEmpty()){ //如果隊(duì)列是空的，直接插入
      this.push(queObj);
    }else{
      var bAdded = false;
      for(var i = 0, len = items.length; i < len; i++){ 
        if(priority < items[i].priority){
          items.splice(i, 0, queObj); // 循環(huán)隊(duì)列，如果優(yōu)先級(jí)小于這個(gè)位置元素的優(yōu)先級(jí)，插入
          bAdded = true;
          break;
        }
      }
      if(!bAdded){
        items.push(queObj); // 如果循環(huán)一圈都沒(méi)有找到能插隊(duì)的位置，直接插入隊(duì)列尾部
      }
    }
  };
  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 () {
    //這個(gè)地方稍微修改一下下
    var temp = [];
    for(var i = 0, len = items.length; i < len; i++){
      temp.push(items[i].ele);
    }
    console.log(temp.toString());
  };
}

解釋我已經(jīng)在代碼里說(shuō)的很明白
下面我們就用這個(gè)優(yōu)先隊(duì)列同樣來(lái)模擬排隊(duì)上WC

var pQueue = new PriorityQueue();
pQueue.enqueue('Mr.A', 3);
pQueue.enqueue('Mr.B', 3);
pQueue.enqueue('Mr.C', 3);
console.log("原隊(duì)列:");
pQueue.print();
pQueue.enqueue('VIP', 2);
pQueue.enqueue('SVIP', 1);
console.log("新隊(duì)列:");
pQueue.print();

控制臺(tái)打?。?/p>

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

循環(huán)隊(duì)列典型的例子擊鼓傳花
還記得在我上高中的時(shí)候我們晚自習(xí)一停電就玩這個(gè)
拿一個(gè)東西當(dāng)“花”，輪著傳，“鼓”一停，拿到花的同學(xué)就要站起來(lái)唱歌
可以把循環(huán)隊(duì)列當(dāng)作是隊(duì)列的應(yīng)用
下面我們來(lái)模擬實(shí)現(xiàn)循環(huán)隊(duì)列擊鼓傳花

function hotPotato(pepoleList, frequency){ //參數(shù)：表示人的數(shù)組，傳花的頻率
  var queue = new Queue();
  for(var i = 0, len = pepoleList.length; i < len; i++){
    queue.enqueue(pepoleList[i]); //初始化，進(jìn)入隊(duì)列
  }
  var eliminated;//被淘汰的同學(xué)
  while(queue.size() > 1){ //只要隊(duì)列至少還有兩個(gè)人，就一直循環(huán)
    for(var i = 0; i < frequency; i++){//出隊(duì)入隊(duì)，模擬循環(huán)效果
      queue.enqueue(queue.dequeue());
    }
    eliminated = queue.dequeue();//清算
    console.log(eliminated + '被淘汰');
  }
  return queue.dequeue();//返回隊(duì)列中的最后一人
}
var pepole = ['Mr.A','Mr.B','Mr.C','Mr.D','Mr.E','Mr.F'];
var gameWinner = hotPotato(pepole, 12);
console.log('全場(chǎng)最佳:' + gameWinner);

控制臺(tái)輸出：