佇列與堆疊是最基礎的兩種資料結構,用 JavaScript 的陣列就能輕鬆模擬。本文從概念談到實作,最後再比較幾個方法的效能差異。
佇列(Queue):先進先出(FIFO, First-In-First-Out),先放入的資料先取出。

堆疊(Stack):後進先出(LIFO, Last-In-First-Out),後放入的資料先取出。

shift():移除並回傳第一個元素unshift():在開頭加入元素,回傳新長度push():在尾端加入元素,回傳新長度pop():移除並回傳最後一個元素
<script type="text/javascript">
var a = new Array();
console.log(a);
console.log("入隊");
a.unshift('a1'); console.log(a);
a.unshift('a2'); console.log(a);
a.unshift('a3'); console.log(a);
console.log("出隊,先進先出");
console.log(a);
a.pop(); console.log(a);
a.pop(); console.log(a);
a.pop(); console.log(a);
</script>

<script type="text/javascript">
var a = new Array();
console.log(a);
console.log("入堆疊");
a.push('a1'); console.log(a);
a.push('a2'); console.log(a);
a.push('a3'); console.log(a);
console.log("出堆疊,後進先出");
console.log(a);
a.pop(); console.log(a);
a.pop(); console.log(a);
a.pop(); console.log(a);
</script>

兩者都能新增元素,但 unshift() 每加一筆就得把既有元素全部往後挪一格,成本自然高得多。實測一下:
<script type="text/javascript">
// +new Date() 等同 new Date().valueOf(),回傳當前毫秒數
var arr = [];
var startTime = +new Date();
for (var i = 0; i < 100000; i++) { arr.push(i); }
var endTime = +new Date();
console.log("push 新增 10 萬筆耗時 " + (endTime - startTime) + " 毫秒");
startTime = +new Date();
arr = [];
for (var i = 0; i < 100000; i++) { arr.unshift(i); }
endTime = +new Date();
console.log("unshift 新增 10 萬筆耗時 " + (endTime - startTime) + " 毫秒");
</script>

在 Chrome 上跑一次,unshift() 大約慢了 100 倍。所以處理大陣列時應避免在頭部插入。
如果業務邏輯一定要「頭部進」,可以先用 push() 全部加完,再一次 reverse() 反轉,效果等同逐筆 unshift(),但快得多:
<script type="text/javascript">
var a = new Array();
a.push('a1'); a.push('a2'); a.push('a3'); a.push('a4');
console.log("反轉前");
console.log(a);
a.reverse(); // 一次反轉
console.log("反轉後");
console.log(a);
</script>

<script type="text/javascript">
var arr = [], s = +new Date;
for (var i = 0; i < 100000; i++) { arr.push(i); }
arr.reverse();
console.log("reverse 10 萬筆耗時:" + (+new Date - s) + " 毫秒");
</script>

結果顯示 reverse() 的耗時極低,可以放心使用。這也說明了一個道理:選擇資料結構時,不只要看「能不能做」,還要看「做得多快」。