js 堆栈实现
堆栈的基本概念
堆栈（Stack）是一种遵循后进先出（LIFO）原则的数据结构。主要操作包括压栈（push）和弹栈（pop），还可以包含查看栈顶元素（peek）等辅助操作。
使用数组实现堆栈
数组是实现堆栈的直观方式，利用数组的push和pop方法可直接模拟堆栈行为。
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
if (this.isEmpty()) {
return "Stack is empty";
}
return this.items.pop();
}
peek() {
if (this.isEmpty()) {
return "Stack is empty";
}
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
clear() {
this.items = [];
}
}使用链表实现堆栈
链表实现堆栈时，通常选择单链表，并在链表的头部进行push和pop操作以保证时间复杂度为O(1)。
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedListStack {
constructor() {
this.top = null;
this.size = 0;
}
push(value) {
const newNode = new Node(value);
newNode.next = this.top;
this.top = newNode;
this.size++;
}
pop() {
if (this.isEmpty()) {
return "Stack is empty";
}
const poppedValue = this.top.value;
this.top = this.top.next;
this.size--;
return poppedValue;
}
peek() {
if (this.isEmpty()) {
return "Stack is empty";
}
return this.top.value;
}
isEmpty() {
return this.size === 0;
}
getSize() {
return this.size;
}
clear() {
this.top = null;
this.size = 0;
}
}堆栈的应用场景
堆栈常用于需要回溯或反转的场景，例如：
- 函数调用栈
- 括号匹配检查
- 表达式求值（如逆波兰表达式）
- 浏览器历史记录（前进/后退）
性能对比
- 数组实现：操作简单，但动态数组可能需要扩容，均摊时间复杂度为O(1)。
- 链表实现：无需扩容，每次操作严格O(1)，但需要额外空间存储指针。
选择实现方式时需根据具体场景权衡空间和时间效率。
