js 栈实现
栈的基本概念
栈（Stack）是一种遵循后进先出（LIFO）原则的线性数据结构。主要操作包括入栈（push）、出栈（pop）、查看栈顶元素（peek）和判断栈是否为空。
JavaScript 栈的实现
JavaScript 中可以通过数组或链表实现栈。以下是基于数组的栈实现代码示例：
class Stack {
constructor() {
this.items = [];
}
// 入栈
push(element) {
this.items.push(element);
}
// 出栈
pop() {
if (this.isEmpty()) {
return "栈为空";
}
return this.items.pop();
}
// 查看栈顶元素
peek() {
if (this.isEmpty()) {
return "栈为空";
}
return this.items[this.items.length - 1];
}
// 判断栈是否为空
isEmpty() {
return this.items.length === 0;
}
// 返回栈的大小
size() {
return this.items.length;
}
// 清空栈
clear() {
this.items = [];
}
// 打印栈内容
print() {
console.log(this.items.toString());
}
}栈的使用示例
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.print(); // 输出: 10,20,30
console.log(stack.pop()); // 输出: 30
console.log(stack.peek()); // 输出: 20
console.log(stack.size()); // 输出: 2栈的应用场景
- 函数调用栈
- 表达式求值（如括号匹配）
- 浏览器历史记录（前进/后退）
- 撤销操作（Undo/Redo）
时间复杂度分析
- 入栈（push）：O(1)
- 出栈（pop）：O(1)
- 查看栈顶（peek）：O(1)
- 判断空栈（isEmpty）：O(1)
注意事项
- JavaScript 数组本身已提供类似栈的操作（push/pop），直接使用数组也可实现栈功能。
- 对于大规模数据，需注意数组实现的栈可能存在内存连续性问题，链表实现更适合动态扩容场景。
