js 实现堆栈

堆栈的基本概念

堆栈是一种遵循后进先出（LIFO）原则的数据结构，只允许在栈顶进行插入（push）和删除（pop）操作。JavaScript中可以通过数组或链表实现堆栈。

使用数组实现堆栈

数组的push和pop方法天然适合堆栈操作，直接利用数组方法即可：

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) return "Underflow";
    return this.items.pop();
  }

  peek() {
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }

  print() {
    console.log(this.items.toString());
  }
}

// 使用示例
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.pop(); // 返回20

使用链表实现堆栈

链表实现可以避免数组动态扩容的性能开销：

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedListStack {
  constructor() {
    this.top = null;
    this.length = 0;
  }

  push(value) {
    const newNode = new Node(value);
    newNode.next = this.top;
    this.top = newNode;
    this.length++;
  }

  pop() {
    if (this.isEmpty()) return null;
    const value = this.top.value;
    this.top = this.top.next;
    this.length--;
    return value;
  }

  peek() {
    if (this.isEmpty()) return null;
    return this.top.value;
  }

  isEmpty() {
    return this.length === 0;
  }

  size() {
    return this.length;
  }
}

性能对比

• 数组实现：操作时间复杂度均为O(1)，但可能触发数组扩容。
• 链表实现：无扩容问题，但每个操作需要处理指针，常数时间稍大。

实际应用场景

• 函数调用栈
• 浏览器历史记录
• 撤销操作（如编辑器）
• 括号匹配等算法问题

扩展：最小栈实现

需要支持O(1)时间获取栈中最小元素：

class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = [];
  }

  push(x) {
    this.stack.push(x);
    if (this.minStack.length === 0 || x <= this.getMin()) {
      this.minStack.push(x);
    }
  }

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

  top() {
    return this.stack[this.stack.length - 1];
  }

  getMin() {
    return this.minStack[this.minStack.length - 1];
  }
}

以上实现方式根据具体需求选择，数组实现更简单直观，链表实现更适合对性能敏感的场景。