堆疊是**後進先出(LIFO, Last In First Out)**的線性表,僅允許在一端(棧頂)進行插入(push)與刪除(pop)操作。生活範例:疊盤子、瀏覽器歷史記錄、函式呼叫堆疊。
push(element):元素入棧。pop():移除並回傳棧頂元素。peek():查看棧頂元素但不移除。length() / size():元素數量。clear():清空堆疊。class Stack {
constructor() {
this.dataStore = [];
this.top = 0; // 指向下一個可插入位置,即棧頂索引
}
push(element) {
this.dataStore[this.top++] = element;
}
pop() {
if (this.top === 0) return undefined; // 空棧
return this.dataStore[--this.top];
}
peek() {
if (this.top === 0) return undefined;
return this.dataStore[this.top - 1];
}
length() { return this.top; }
size() { return this.top; } // 別名
clear() { this.top = 0; } // 保留底層陣列,避免頻繁 GC
// 迭代器:從棧頂到棧底
*[Symbol.iterator]() {
for (let i = this.top - 1; i >= 0; i--) yield this.dataStore[i];
}
toString() { return this.dataStore.slice(0, this.top).join(' <- '); }
}
function toBinary(num) {
const stack = new Stack();
if (num === 0) return '0';
while (num > 0) {
stack.push(num % 2);
num = Math.floor(num / 2);
}
let binary = '';
while (stack.length()) binary += stack.pop();
return binary;
}
console.log(toBinary(10)); // 1010
function isBalanced(str) {
const stack = new Stack();
const pairs = { ')': '(', ']': '[', '}': '{' };
for (const ch of str) {
if ('([{'.includes(ch)) stack.push(ch);
else if (')]}'.includes(ch)) {
if (stack.length() === 0 || stack.pop() !== pairs[ch]) return false;
}
}
return stack.length() === 0;
}
console.log(isBalanced('({[]})')); // true
console.log(isBalanced('({[})')); // false
function infixToPostfix(expr) {
const stack = new Stack();
const output = [];
const prec = { '+': 1, '-': 1, '*': 2, '/': 2, '^': 3 };
const tokens = expr.match(/\d+|\+|\-|\*|\/|\^|\(|\)/g);
for (const token of tokens) {
if (!isNaN(token)) output.push(token);
else if (token === '(') stack.push(token);
else if (token === ')') {
while (stack.length() && stack.peek() !== '(') output.push(stack.pop());
stack.pop(); // 移除 '('
} else { // 運算子
while (stack.length() && stack.peek() !== '(' && prec[stack.peek()] >= prec[token]) {
output.push(stack.pop());
}
stack.push(token);
}
}
while (stack.length()) output.push(stack.pop());
return output.join(' ');
}
console.log(infixToPostfix('3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'));
// 3 4 2 * 1 5 - 2 3 ^ ^ / +
function factorial(n) {
const stack = new Stack();
while (n > 1) stack.push(n--);
let result = 1;
while (stack.length()) result *= stack.pop();
return result;
}
console.log(factorial(5)); // 120
| 操作 | 時間 | 空間 |
|---|---|---|
| push / pop / peek / length | O(1) | O(1) |
| clear | O(1) | O(1) |
陣列原生 push/pop 已是高度優化的堆疊實現,簡單場景直接使用 [] 即可:
const stack = [];
stack.push(1); stack.push(2);
stack.pop(); // 2
自定義 Class 適用於:需要封裝額外邏輯(如最小值棧、持久化、序列化)、教學示範、或需明確語義區分「堆疊」與「陣列」的大型專案。