js 实现单链表实现栈
单链表实现栈的思路
使用单链表实现栈的核心在于利用链表的头部插入和删除操作，这些操作的时间复杂度均为 O(1)，符合栈的后进先出（LIFO）特性。栈的主要操作包括 push（入栈）、pop（出栈）、peek（查看栈顶元素）和 isEmpty（判断栈是否为空）。
单链表节点定义
链表的每个节点需要存储数据和指向下一个节点的指针。
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}栈的实现
定义一个 Stack 类，包含栈的基本操作方法。
class Stack {
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 null;
}
const poppedValue = this.top.value;
this.top = this.top.next;
this.size--;
return poppedValue;
}
// 查看栈顶元素
peek() {
if (this.isEmpty()) {
return null;
}
return this.top.value;
}
// 判断栈是否为空
isEmpty() {
return this.size === 0;
}
// 获取栈的大小
getSize() {
return this.size;
}
}使用示例
以下是如何使用 Stack 类的示例代码：
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.peek()); // 输出 3
console.log(stack.pop()); // 输出 3
console.log(stack.peek()); // 输出 2
console.log(stack.isEmpty()); // 输出 false
console.log(stack.getSize()); // 输出 2关键点说明
- 入栈（push）：新节点插入到链表头部，并更新
top指针指向新节点。 - 出栈（pop）：移除链表头部节点，并更新
top指针指向下一个节点。 - 查看栈顶（peek）：返回
top指针指向的节点的值，不修改栈。 - 时间复杂度：所有操作均为 O(1)，因为只涉及链表头部的操作。
通过单链表实现栈，可以高效地完成栈的基本操作，同时避免了数组实现中可能存在的动态扩容问题。
