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());
}
}基于链表的栈实现
通过链表节点实现栈，避免数组动态扩容的性能开销：
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 poppedValue = this.top.value;
this.top = this.top.next;
this.length--;
return poppedValue;
}
peek() {
return this.isEmpty() ? null : this.top.value;
}
isEmpty() {
return this.top === null;
}
size() {
return this.length;
}
print() {
let current = this.top;
const values = [];
while (current) {
values.push(current.value);
current = current.next;
}
console.log(values.join(" -> "));
}
}性能对比
- 数组栈：操作时间复杂度为 $O(1)$，但可能触发数组扩容。
- 链表栈：无需考虑扩容，但每个操作需处理指针，常数时间略高。
应用场景
- 函数调用栈
- 浏览器历史记录（后退功能）
- 括号匹配等算法问题
注意事项
- 边界处理需检查栈是否为空（
isEmpty）。 - 链表实现时注意指针的指向变更。
- 实际项目中优先使用语言内置的栈结构（如数组）。
