列表是最基礎的資料結構,但面對某些問題會顯得力不從心,這時就需要堆疊。堆疊的原理極簡單——所有操作只發生在同一端——正因如此,它執行速度快、實作容易,應用範圍卻意外地廣。
堆疊是一種特殊的列表,元素只能從同一端存取,這端稱為「堆疊頂」。最貼切的比喻是餐館裡洗好的一疊盤子:你只能拿走最上面那個,放回時也只能放在最上面。因此堆疊被稱為「後進先出」(LIFO, Last In First Out)的資料結構。
因為這個特性,任何不在堆疊頂的元素都無法直接存取——想拿到墊在底下的元素,必須先把上面的逐一移開。堆疊的兩個核心操作是「壓入堆疊」(push)與「彈出堆疊」(pop)。pop() 雖然回傳堆疊頂元素,但該元素同時也被永久移除了;若只想看而不拿,應該用 peek()。
入堆疊與出堆疊的示意如下:

push()、pop()、peek() 是三大主要方法,此外還常用到:
clear():清除堆疊內所有元素。
length():回傳堆疊內元素個數。
先建立基本的類別結構:
function Stack() {
this.dataStore = []; // 保存堆疊內所有元素
this.top = 0; // 記錄堆疊頂位置
}
top 初始化為 0,代表堆疊頂對應陣列的起始位置;每壓入一個元素,它就隨之遞增。
push():壓入新元素
把元素放在 top 所指的位置,然後 top 加一指向下一格:
function push(element) {
this.dataStore[this.top++] = element;
}
pop():彈出堆疊頂
與 push 相反,先減一再取值:
function pop(){
return this.dataStore[--this.top];
}
peek():僅讀取堆疊頂
function peek(){
return this.dataStore[this.top - 1];
}
length():元素個數
function length(){
return this.top;
}
clear():清空堆疊
function clear() {
this.top = 0;
}
function Stack() {
this.dataStore = [];
this.top = 0;
}
Stack.prototype = {
// 向堆疊中壓入一個新元素
push: function(element) {
this.dataStore[this.top++] = element;
},
// 訪問堆疊頂元素,該元素同時被永久刪除
pop: function(){
return this.dataStore[--this.top];
},
// 回傳 top-1 位置的元素,即堆疊頂元素
peek: function(){
return this.dataStore[this.top - 1];
},
// 堆疊中存儲了多少個元素
length: function(){
return this.top;
},
// 清空堆疊
clear: function(){
this.top = 0;
}
};
var stack = new Stack();
stack.push("a");
stack.push("b");
stack.push("c");
console.log(stack.length()); // 3
console.log(stack.peek()); // c
var popped = stack.pop();
console.log(popped); // c
console.log(stack.peek()); // b
stack.push("d");
console.log(stack.peek()); // d
stack.clear();
console.log(stack.length()); // 0
console.log(stack.peek()); // undefined
5! = 5 × 4 × 3 × 2 × 1,這個順序剛好可以用堆疊的後進先出特性來處理:
function fact(n) {
var s = new Stack();
while(n > 1) {
s.push(n--);
}
var product = 1;
while(s.length() > 0) {
product *= s.pop();
}
return product;
}
console.log(fact(5)); // 120
邏輯是:先把 5 傳入,用 while 迴圈每次遞減 1 並把當前值壓入堆疊,直到 n 不再大於 1。接著定義 product,透過 length() 判斷堆疊是否還有元素,每次 pop() 取出堆疊頂並相乘。由於 pop() 取完就移除,迴圈會自動收束,最終得到 5×4×3×2×1。
這個階乘例子只是為了示範操作,實務上堆疊的價值遠不止於此。函數呼叫本身就是一個堆疊(呼叫堆疊),這也是遞迴太深會拋出堆疊溢出的原因;瀏覽器的返回上一頁是堆疊;程式的撤銷(undo)功能、括號配對檢查、表達式的中序轉後序、以及深度優先搜尋,背後都是同一個資料結構。理解「後進先出」這四個字,等於拿到了這一整類問題的鑰匙。