佇列(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。