js 实现堆栈
堆栈的基本概念
堆栈是一种遵循后进先出（LIFO）原则的数据结构，只允许在栈顶进行插入（push）和删除（pop）操作。JavaScript中可以通过数组或链表实现堆栈。
使用数组实现堆栈
数组的push和pop方法天然适合堆栈操作，直接利用数组方法即可：
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
if (this.isEmpty()) return "Underflow";
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 = [];
}
print() {
console.log(this.items.toString());
}
}
// 使用示例
const stack = new Stack();
stack.push(10);
stack.push(20);
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;
}
}性能对比
- 数组实现：操作时间复杂度均为O(1)，但可能触发数组扩容。
- 链表实现：无扩容问题，但每个操作需要处理指针，常数时间稍大。
实际应用场景
- 函数调用栈
- 浏览器历史记录
- 撤销操作（如编辑器）
- 括号匹配等算法问题
扩展：最小栈实现
需要支持O(1)时间获取栈中最小元素：
class MinStack {
constructor() {
this.stack = [];
this.minStack = [];
}
push(x) {
this.stack.push(x);
if (this.minStack.length === 0 || x <= this.getMin()) {
this.minStack.push(x);
}
}
pop() {
const val = this.stack.pop();
if (val === this.getMin()) {
this.minStack.pop();
}
return val;
}
top() {
return this.stack[this.stack.length - 1];
}
getMin() {
return this.minStack[this.minStack.length - 1];
}
}以上实现方式根据具体需求选择，数组实现更简单直观，链表实现更适合对性能敏感的场景。
