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)，但需要额外空间存储指针。

选择实现方式时需根据具体场景权衡空间和时间效率。