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)，因为只涉及链表头部的操作。

通过单链表实现栈，可以高效地完成栈的基本操作，同时避免了数组实现中可能存在的动态扩容问题。