DIV CSS 佈局教程網

JavaScript 資料結構與演算法(二):佇列
編輯:JavaScript綜合知識     

佇列只允許在一端插入、另一端刪除,是一種先進先出(FIFO, First-In-First-Out)的線性表。它在程式設計中使用得非常頻繁,而 JavaScript 的執行模型讓它變得更加重要。

為什麼 JavaScript 特別需要佇列

因為 JavaScript 是單執行緒的,任何時間點只能執行一個任務,再加上非同步機制的存在,就衍生出兩個問題:

1. 非同步操作執行期間,同步程式碼仍在繼續跑;若同步程式碼依賴非同步的結果,自然就會出錯。
2. 多個任務在不同時間點被呼叫,需要一個機制決定它們的執行順序。

jQuery 的動畫就是最常見的例子:

$book.animate({ opacity: 0.25 })
     .animate({ opacity: 0.5 })
     .animate({ opacity: 1 });

我們的直覺是:第一段動畫結束後 opacity 變成 0.25,接著執行第二段變成 0.5,以此類推。但動畫本質上是非同步的,而 animate 是在同步返回的,所以這裡就需要一個佇列來排隊——jQuery 也正是因此提供了專門的 queue 機制。

用陣列實作佇列

JavaScript 可以直接用陣列完成這件事:push() 在尾端加入元素,shift() 移除頭部元素。

function Queue() {
  this.dataStore = [];
  this.enqueue = enqueue;
  this.dequeue = dequeue;
  this.first = first;
  this.end = end;
  this.toString = toString;
  this.empty = empty;
}

// 從隊尾加入元素
function enqueue(element) {
  this.dataStore.push(element);
}

// 移除隊首元素
function dequeue() {
  return this.dataStore.shift();
}

// 讀取隊首與隊尾
function first() { return this.dataStore[0]; }
function end()   { return this.dataStore[this.dataStore.length - 1]; }

// 顯示佇列中的所有元素
function toString() {
  var retStr = "";
  for (var i = 0; i < this.dataStore.length; ++i) {
    retStr += this.dataStore[i] + "\n";
  }
  return retStr;
}

// 判斷是否為空
function empty() {
  return this.dataStore.length == 0;
}

var q = new Queue();
q.enqueue("Aaron1");
q.enqueue("Aaron2");
q.enqueue("Aaron3");

console.log("佇列頭: " + q.first());   // Aaron1
console.log("佇列尾: " + q.end());     // Aaron3

佇列採用線性儲存,因此存在順序儲存的固有缺點:排隊買票時,第一個人買完,後面所有人都得往前補位。用陣列實作時這個成本由底層的 shift() 承擔(它需要搬移所有元素)。若追求效能,實務上會改用「頭尾兩個索引 + 環狀緩衝」或鏈表結構來避免搬移。

用佇列實作動畫排隊

下面這個精簡版本示範如何模仿 jQuery 的串行動畫:把每段動畫包成函數放進佇列,用一個「動畫鎖」確保同一時間只有一段在跑,一段結束後再取出下一段。

var animation = (function() {
  var Queue = [];        // 動畫佇列
  var fireing = false;   // 動畫鎖
  var first = true;

  var makeAnim = function(element, options, func) {
    element.style.webkitTransitionDuration = '2000ms';
    element.style.webkitTransform = 'translate3d(' + options.width + 'px,0,0)';
    element.addEventListener('webkitTransitionEnd', function() {
      func();            // 動畫結束後通知佇列
    });
  };

  var _fire = function() {
    if (!fireing) {
      var onceRun = Queue.shift();
      if (onceRun) {
        fireing = true;
        onceRun(function() {
          fireing = false;
          _fire();       // 一段結束,接著跑下一段
        });
      } else {
        fireing = true;
      }
    }
  };

  return {
    add: function(element, options) {
      Queue.push(function(func) { makeAnim(element, options, func); });
      if (first && Queue.length) {
        first = false;
        this.fire();
      }
    },
    fire: function() { _fire(); }
  };
})();

呼叫端就能寫成鏈式:

document.getElementById('div1').onclick = function() {
  $('#div1').run({ 'width': '500' })
           .run({ 'width': '300' })
           .run({ 'width': '1000' });
};

三段動畫會依序排入佇列,前一段的 webkitTransitionEnd 觸發後才會啟動下一段。

重點回顧

佇列的核心只有兩個操作:入隊與出隊,而它的價值在於「保證順序」。這個特性在人類世界與電腦科學裡反覆出現:工作排程、訊息佇列、事件迴圈、列印佇列、BFS 廣度優先搜尋,背後都是同一個抽象。實作時只要記住兩件事:一端進、另一端出;以及若用陣列實作,shift() 的成本隨佇列長度線性成長。

範例中的 webkitTransform 與 webkitTransitionEnd 是早期 WebKit 專用的寫法,現今請改用標準的 transform 與 transitionend,並搭配 requestAnimationFrame 或 CSS 動畫會更流暢。

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