js 实现单链表实现栈

单链表实现栈的基本思路

使用单链表实现栈时，通常选择链表的头部作为栈顶。因为单链表的头部插入和删除操作的时间复杂度均为 O(1)，符合栈的高效操作需求。栈的 push 对应链表头部插入节点，pop 对应链表头部删除节点。

代码实现

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

class LinkedListStack {
  constructor() {
    this.head = null; // 栈顶指针
    this.size = 0;    // 栈大小
  }

  // 入栈操作
  push(val) {
    const newNode = new ListNode(val);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
  }

  // 出栈操作
  pop() {
    if (this.isEmpty()) {
      throw new Error("栈为空");
    }
    const val = this.head.val;
    this.head = this.head.next;
    this.size--;
    return val;
  }

  // 获取栈顶元素
  peek() {
    if (this.isEmpty()) {
      throw new Error("栈为空");
    }
    return this.head.val;
  }

  // 判断栈是否为空
  isEmpty() {
    return this.size === 0;
  }

  // 获取栈的大小
  getSize() {
    return this.size;
  }
}

使用示例

const stack = new LinkedListStack();
stack.push(1);
stack.push(2);
console.log(stack.peek()); // 输出 2
console.log(stack.pop());  // 输出 2
console.log(stack.getSize()); // 输出 1

关键点说明

• 时间复杂度：push、pop、peek 操作均为 O(1)，因为只涉及链表头部的操作。
• 空间复杂度：每个节点需要额外存储 next 指针，空间复杂度为 O(n)。
• 边界处理：在 pop 和 peek 时需检查栈是否为空，避免操作无效节点。

扩展优化

若需支持动态扩容或其他功能（如最小栈），可在单链表基础上扩展。例如，实现一个能获取栈中最小值的栈：

class MinStack {
  constructor() {
    this.stack = new LinkedListStack();
    this.minStack = new LinkedListStack(); // 辅助栈存储最小值
  }

  push(val) {
    this.stack.push(val);
    if (this.minStack.isEmpty() || val <= this.minStack.peek()) {
      this.minStack.push(val);
    }
  }

  pop() {
    const val = this.stack.pop();
    if (val === this.minStack.peek()) {
      this.minStack.pop();
    }
    return val;
  }

  getMin() {
    return this.minStack.peek();
  }
}