棧(Stack)是計算機科學裡最基礎的數據結構之一。維基百科的定義是:棧是一種特殊的串列形式數據結構,只允許在鏈表或數組的一端(稱為棧頂,top)進行插入(push)與刪除(pop)操作,因此按照後進先出(LIFO, Last In First Out)的原則運作。
下面用 ES6 的 class 語法把它實現出來,並順手做三道經典練習題。
/**
* Stack 類
*/
class Stack {
constructor() {
this.data = []; // 用數組保存數據
this.top = 0; // 棧頂指針,同時也是元素個數
}
// 入棧,支持一次壓入多個元素
push() {
const args = [...arguments];
args.forEach(arg => this.data[this.top++] = arg);
return this.top;
}
// 出棧
pop() {
if (this.top === 0) throw new Error('The stack is already empty!');
const peek = this.data[--this.top];
this.data = this.data.slice(0, -1);
return peek;
}
// 查看棧頂元素,不出棧
peek() {
return this.data[this.top - 1];
}
// 元素個數
length() {
return this.top;
}
// 清空棧
clear() {
this.top = 0;
return this.data = [];
}
// 是否為空
isEmpty() {
return this.top === 0;
}
}
// 使用示例
const stack = new Stack();
stack.push(1);
stack.push(2, 3);
console.log(stack.data); // [1, 2, 3]
console.log(stack.peek()); // 3
console.log(stack.pop()); // 3,此時 data 為 [1, 2]
stack.push(3);
console.log(stack.length()); // 3
stack.clear(); // data 變為 []
用數組存數據、用 top 記錄棧頂位置,是實現棧最直白的思路。epxress 出棧前先判空也是必要的防禦。
進制轉換的核心是「除基取餘,逆序輸出」——「逆序」兩個字正好對應棧的後進先出。
/**
* 將數字轉換為指定進制
*/
const numConvert = (num, base) => {
const stack = new Stack();
let converted = '';
while (num > 0) {
stack.push(num % base); // 取餘入棧
num = Math.floor(num / base);
}
while (stack.length() > 0) {
converted += stack.pop(); // 依次出棧即為正確順序
}
return +converted;
};
console.log(numConvert(10, 2)); // 1010
把字符串逐個字符壓棧,再全部弹出拼接,得到的就是反轉串。與原串比較即可判定是否回文。
/**
* 判斷給定字符串或數字是否是回文
*/
const isPalindrome = words => {
const stack = new Stack();
let wordsCopy = '';
words = words.toString();
Array.prototype.forEach.call(words, word => stack.push(word));
while (stack.length() > 0) {
wordsCopy += stack.pop();
}
return words === wordsCopy;
};
console.log(isPalindrome('1a121a1')); // true
console.log(isPalindrome(2121)); // false
棧的實現代碼很短,但思想滲透得很廣:函數調用棧、表達式求值、瀏覽器后退、DOM 遍歷的非遞歸改寫,背後都是同一套 LIFO 模型。上面幾個算法僅為演示棧的用法,並非性能最優解,但足以說明問題:遇到「逆序」需求時,先想想棧。