1. 定義

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

在現(xiàn)實(shí)中，最常見的隊(duì)列的例子就是排隊(duì)：

來(lái)自《javascript數(shù)據(jù)結(jié)構(gòu)與算法》

2. 創(chuàng)建隊(duì)列

• 聲明類并聲明一個(gè)數(shù)組用于存儲(chǔ)隊(duì)列中元素的數(shù)據(jù)結(jié)構(gòu)。

function Queue() {
  var items = [];
  //這里是屬性和方法
}

• 實(shí)現(xiàn)enqueue()方法，向隊(duì)列尾部添加數(shù)個(gè)新的項(xiàng)。

this.enqueue = function(element) {
  //用push方法，將元素添加到數(shù)組末尾
  items.push(element);
};

• 實(shí)現(xiàn)dequeue()方法，移除隊(duì)的第一項(xiàng)（隊(duì)首），并返回被移除的元素。

this.dequeue = function() {
  //shift方法，移除數(shù)組中的第一項(xiàng)（索引為0）的元素
  return items.shift();
};

• front()方法，返回隊(duì)列中的第一個(gè)元素，不改變隊(duì)列。

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

• isEmpty()方法，如果隊(duì)列中不包含任何元素，返回true，否則返回false。

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

• clear()方法，清空隊(duì)列元素

this.clear = function() {
  items = [];
};

• size()方法，返回隊(duì)列包含的元素個(gè)數(shù)。

this.size = function(){
  return items.lenght;
};

• 完整代碼如下

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

var queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);

queue.print(); // "1,2"

3. 優(yōu)先隊(duì)列
   現(xiàn)實(shí)生活中也有優(yōu)先隊(duì)列，如頭等艙>商務(wù)艙>經(jīng)濟(jì)艙，接下來(lái)我們用代碼實(shí)現(xiàn)下優(yōu)先隊(duì)列。

function PriorityQueue() {
  //聲明一個(gè)items用于保存元素
  var items = [];

  //創(chuàng)建一個(gè)QueueElement類，用于保存元素和其在隊(duì)列中的優(yōu)先級(jí)(priority越小，優(yōu)先級(jí)越高)
  function QueueElement(element,priority) {
    this.element = element;
    this.priority = priority;
  }

  this.enqueue = function(element,priority) {
    var queueElement = new QueueElement(element,priority);
    //如果隊(duì)列為空，可以將元素入列
    if(this.isEmpty()) {
      items.push(queueElement);
    }else {
      var added = false;
      //反之就循環(huán)隊(duì)列里面的每一個(gè)元素，比較優(yōu)先級(jí)，如果priority小(優(yōu)先級(jí)越高)的話，就用splice()方法放在該元素的前面
      for(var i=0; i<items.length; i++) {
        if(queueElement.priority < items[i].priority) {
          items.splice(i,0,queueElement);
          added = true;
          break;
        }
      }
      //如果添加的元素的priority比隊(duì)列中的每一個(gè)元素都要大的話，就把它添加到隊(duì)列的最后面
      if(!added) {
        items.push(queueElement);
      }
    }
  };

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

  this.print = function() {
    console.log(items);
  };
}

var priorityQueue = new PriorityQueue();
priorityQueue.enqueue("one",1);
priorityQueue.enqueue("two",2);
priorityQueue.enqueue("zero",0);
priorityQueue.enqueue("four",4);

priorityQueue.print(); // "0,1,2,4"

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

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

  //將傳入的nameList遍歷，將每一項(xiàng)添加到隊(duì)列中
  for(var i=0; i<nameList; i++) {
    queue.enqueue(nameList[i]);
  }

  var eliminated = '';
  //如果隊(duì)列里的size大于1，就一直循環(huán)下去
  while(queue.size() > 1) {
    //將第一項(xiàng)放到最后一項(xiàng)，循環(huán)給定的num
    for(var i=0; i<num; i++) {
      queue.enqueue(queue.dequeue);
    }
    //傳遞次數(shù)達(dá)到了給定的數(shù)值，（移除第一項(xiàng)）
    eliminated = queue.dequeue();
    console.log(eliminated + '淘汰')；
  }
  //返回隊(duì)列中僅有的最后一項(xiàng)
  return queue.dequeue();
}

var names = ['a','b','c','d','e'];
var winner = hotPotato(names,7);
console.log('勝利者' + winner);

參考學(xué)習(xí) ：

《javascript數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)》
《數(shù)據(jù)結(jié)構(gòu)與算法javascript描述》