上一篇介紹了列表。列表是最簡單的結構,但要處理比較複雜的場景時它顯得過於簡陋,於是我們需要某種類似列表、但能力更強的資料結構——堆疊。堆疊是一種高效的結構,因為資料只能在堆疊頂端加入或移除,操作很快,實作也很容易。
堆疊是一種特殊的列表,其中的元素只能透過同一端存取,這一端稱為「堆疊頂」。想像餐館裡洗盤子:只能先洗最上面那個,洗完之後新的盤子也只能疊回最上面。這種「後進先出」(LIFO, Last In First Out)的特性正是堆疊的核心。
由於後進先出,任何不在堆疊頂的元素都無法存取;要拿到堆疊底的元素,必須先把上面的逐一移開。堆疊的兩項主要操作是入堆疊(push)與出堆疊(pop)。pop 雖然能取得堆疊頂元素,但呼叫後該元素就永久離開堆疊了。另一個常用方法是 peek(),它只回傳堆疊頂元素而不移除。

除了 push、pop、peek 這三個主要方法,實務上通常還會補上:clear() 清除堆疊內所有元素,以及 length() 回傳元素個數。
function Stack() {
this.dataStore = []; // 保存堆疊內的所有元素
this.top = 0; // 記錄堆疊頂位置
}
dataStore 負責存放元素,變數 top 記錄堆疊頂位置,初始化為 0,代表堆疊頂對應陣列的起始位置;每當有元素被壓入,這個值就隨之遞增。
把新元素存進陣列中 top 所指的位置,然後 top 加一,指向下一個空位。
function push(element) {
this.dataStore[this.top++] = element;
}
與 push 相反,回傳堆疊頂元素並將 top 減一。
function pop() {
return this.dataStore[--this.top];
}
function peek() {
return this.dataStore[this.top - 1];
}
function length() {
return this.top;
}
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 迴圈在每次自減之前把當前值壓入堆疊,直到 n 小於 1 為止。接著定義 product,迴圈中每次呼叫 pop() 取出堆疊頂元素並相乘,同時該元素被移除,直到堆疊清空。最終 product 就等于 5 × 4 × 3 × 2 × 1。
堆疊在實務中的用處遠不止於教學示範:函數呼叫堆疊、瀏覽器的后退紀錄、編輯器的復原功能、表達式的括號配對檢查、以及深度優先搜尋,背後都是同一套後進先出的邏輯。