js 栈实现
栈的基本概念
栈是一种遵循后进先出（LIFO）原则的数据结构，仅允许在栈顶进行插入（压栈）和删除（弹栈）操作。JavaScript中可通过数组或链表实现栈。
基于数组的栈实现
数组的push和pop方法天然适合栈操作：
class ArrayStack {
constructor() {
this.items = [];
}
// 压栈
push(element) {
this.items.push(element);
}
// 弹栈
pop() {
if (this.isEmpty()) return null;
return this.items.pop();
}
// 查看栈顶
peek() {
if (this.isEmpty()) return null;
return this.items[this.items.length - 1];
}
// 判断栈空
isEmpty() {
return this.items.length === 0;
}
// 返回栈大小
size() {
return this.items.length;
}
// 清空栈
clear() {
this.items = [];
}
}基于链表的栈实现
链表实现的栈需维护头节点作为栈顶：
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;
}
clear() {
this.top = null;
this.length = 0;
}
}性能对比
- 数组栈：操作时间复杂度为O(1)，但可能触发动态数组扩容。
- 链表栈：无扩容问题，但每个节点需额外存储指针，内存开销略大。
应用场景
- 函数调用栈
- 浏览器历史记录（后退功能）
- 括号匹配等算法问题
可根据实际需求选择数组或链表实现。数组实现更简洁，链表实现适合频繁动态变化的场景。
