佇列只允許在一端插入、另一端刪除,是一種先進先出(FIFO, First-In-First-Out)的線性表。它在程式設計中使用得非常頻繁,而 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 動畫會更流暢。