js 实现堆栈
使用数组实现堆栈
在JavaScript中，数组天然支持堆栈的push和pop操作，可以直接模拟堆栈行为。
const stack = [];
stack.push(1); // 入栈
stack.push(2);
const top = stack.pop(); // 出栈，返回2封装类实现堆栈
通过类封装可以更规范地实现堆栈操作，包括push、pop、peek和isEmpty等方法。
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
if (this.isEmpty()) return undefined;
return this.items.pop();
}
peek() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
clear() {
this.items = [];
}
}
// 使用示例
const stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.pop()); // 20使用链表实现堆栈
链表实现可以避免数组扩容带来的性能问题，适合动态大小堆栈。
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedListStack {
constructor() {
this.top = null;
this.length = 0;
}
push(value) {
const newNode = new Node(value);
newNode.next = this.top;
this.top = newNode;
this.length++;
}
pop() {
if (this.isEmpty()) return null;
const value = this.top.value;
this.top = this.top.next;
this.length--;
return value;
}
peek() {
if (this.isEmpty()) return null;
return this.top.value;
}
isEmpty() {
return this.length === 0;
}
size() {
return this.length;
}
}处理堆栈溢出
JavaScript引擎有调用堆栈大小限制，递归过深会导致堆栈溢出错误。可以通过尾递归优化或改用循环避免。
// 危险示例：可能堆栈溢出
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}
// 安全示例：改用循环
function safeFactorial(n) {
let result = 1;
for (let i = 2; i <= n; i++) {
result *= i;
}
return result;
}堆栈的典型应用场景
堆栈常用于实现函数调用、表达式求值、括号匹配等场景。例如实现括号匹配检查器：
function isBalanced(expr) {
const stack = [];
const map = {
'(': ')',
'[': ']',
'{': '}'
};
for (let char of expr) {
if (char in map) {
stack.push(char);
} else if (Object.values(map).includes(char)) {
if (stack.length === 0 || map[stack.pop()] !== char) {
return false;
}
}
}
return stack.length === 0;
}
console.log(isBalanced('({[]})')); // true
console.log(isBalanced('({[)}')); // false
