DIV CSS 佈局教程網

JavaScript 中的佇列:一般佇列、優先佇列與循環佇列
編輯:關於JavaScript     

佇列(Queue)是一種遵循先進先出(FIFO)原則的有序集合:新元素從尾端加入,元素從頭端移除。

一、用生活理解佇列

最貼切的例子就是排隊,這個名字本身已經很直觀了。

它和堆疊很像,只是堆疊是後進先出,佇列則是先進先出。

用詞對應如下:最前面是隊頭,最後面是隊尾;出隊從隊頭,入隊從隊尾。

二、建立一個佇列

需要的能力,用「排隊上廁所」來類比就很好懂:

  • 加入元素(進入排隊隊伍)
  • 移除隊頭元素(最前面的人進廁所)
  • 檢視隊頭元素(看看最前面是誰)
  • 判斷是否為空(隊伍裡有沒有人)
  • 清空隊伍(廁所炸了,大家散了吧)
  • 取得元素個數(排隊的有幾人)

實作上直接用陣列即可,陣列的頭就當作隊列頭:

function Queue() {
  var items = [];

  this.enqueue = function (ele) {          // 入隊
    items.push(ele);
  };
  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());
  };
}

var queue = new Queue();

三、使用佇列模擬排隊

var queue = new Queue();
console.log("隊列是否為空: " + queue.isEmpty());

queue.enqueue('Mr.A');
queue.enqueue('Mr.B');
queue.enqueue('Mr.C');

console.log("當前隊列:");
queue.print();

console.log("出隊的人: " + queue.dequeue());
console.log("當前隊列:");
queue.print();

四、優先佇列

排隊上廁所時,來了一位持 VIP 卡的先插到最前面;過一會兒又來一位 SVIP,插到 VIP 前面。這個比喻未必恰當,但生活中確實存在帶優先順序的隊列:優先級高的人排在前面。

依規則不同可分成兩種:最小優先佇列把優先值小的放前面,最大優先佇列則相反。兩者實作方式相同,差別只是一個比較運算的方向。

優先佇列與普通佇列的差異在於:入隊時要判斷優先級,並且需要把元素包裝成帶有優先屬性的物件。既然每個元素結構相同,用建構函式來產生就相當合適。

function PriorityQueue() {
  var items = [];

  // 把元素包裝成帶優先級的物件
  function QueEle(ele, priority) {
    this.ele = ele;            // 元素
    this.priority = priority;  // 優先級
  }

  this.enqueue = function (ele, priority) {
    var queObj = new QueEle(ele, priority);
    if (this.isEmpty()) {
      items.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);
          bAdded = true;
          break;
        }
      }
      if (!bAdded) {
        items.push(queObj);    // 找不到可插入的位置就放尾部
      }
    }
  };

  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 () {
    var temp = [];
    for (var i = 0, len = items.length; i < len; i++) {
      temp.push(items[i].ele);
    }
    console.log(temp.toString());
  };
}

同樣用它來模擬排隊:

var pQueue = new PriorityQueue();
pQueue.enqueue('Mr.A', 3);
pQueue.enqueue('Mr.B', 3);
pQueue.enqueue('Mr.C', 3);
console.log("原隊列:");
pQueue.print();

pQueue.enqueue('VIP', 2);
pQueue.enqueue('SVIP', 1);
console.log("新隊列:");
pQueue.print();

五、循環佇列:擊鼓傳花

循環佇列最典型的例子就是擊鼓傳花。還記得高中晚自習停電時我們就玩這個,拿一樣東西當「花」輪流傳,鼓聲一停,拿到花的人就得站起來唱歌。

它的實作很巧妙:把「出隊後立刻入隊」當成傳花的動作,走滿固定次數後,再把隊頭的人淘汰,反覆直到只剩一人。

function hotPotato(pepoleList, frequency) {
  // 參數:人員陣列、傳花頻率
  var queue = new Queue();

  for (var i = 0, len = pepoleList.length; i < len; i++) {
    queue.enqueue(pepoleList[i]);   // 全部進入佇列
  }

  var eliminated;
  while (queue.size() > 1) {        // 至少還有兩人時持續進行
    for (var i = 0; i < frequency; i++) {
      queue.enqueue(queue.dequeue());   // 出隊再入隊,模擬傳花
    }
    eliminated = queue.dequeue();
    console.log(eliminated + ' 被淘汰');
  }
  return queue.dequeue();           // 最後留下的贏家
}

var pepole = ['Mr.A', 'Mr.B', 'Mr.C', 'Mr.D', 'Mr.E', 'Mr.F'];
var gameWinner = hotPotato(pepole, 12);
console.log('全場最佳:' + gameWinner);

以上就是 JavaScript 中佇列的實作,並延伸理解了優先佇列與循環佇列這兩個常見變體。三者共用同一套骨架,差別只在入隊規則與出隊時機——把這層關係想通,就不必為每個變體重新記一遍 API。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved