js 堆栈实现

堆栈的基本概念

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

基于数组的实现

使用数组实现堆栈时，需要维护一个指针（通常称为top）来跟踪栈顶位置。

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

  push(element) {
    this.top++;
    this.items[this.top] = element;
  }

  pop() {
    if (this.isEmpty()) return undefined;
    const poppedItem = this.items[this.top];
    this.top--;
    return poppedItem;
  }

  peek() {
    if (this.isEmpty()) return undefined;
    return this.items[this.top];
  }

  isEmpty() {
    return this.top === -1;
  }

  size() {
    return this.top + 1;
  }

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

基于链表的实现

链表实现堆栈时，每个节点包含数据和指向下一个节点的指针。栈顶是链表的头节点。

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

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

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

  pop() {
    if (this.isEmpty()) return undefined;
    const poppedNode = this.top;
    this.top = this.top.next;
    this.size--;
    return poppedNode.data;
  }

  peek() {
    if (this.isEmpty()) return undefined;
    return this.top.data;
  }

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

  getSize() {
    return this.size;
  }

  clear() {
    this.top = null;
    this.size = 0;
  }
}

堆栈的应用场景

堆栈常用于需要回溯操作的场景，例如：

• 函数调用栈
• 浏览器历史记录
• 撤销操作（Undo）
• 括号匹配校验
• 表达式求值

时间复杂度分析

堆栈操作的时间复杂度均为O(1)：

• push：O(1)
• pop：O(1)
• peek：O(1)
• isEmpty：O(1)

空间复杂度取决于存储的元素数量，为O(n)。

实际应用示例：括号匹配

使用堆栈检查表达式中的括号是否匹配：

function isBalanced(expression) {
  const stack = new Stack();
  const map = {
    '(': ')',
    '[': ']',
    '{': '}'
  };

  for (let char of expression) {
    if (char in map) {
      stack.push(char);
    } else if (char === ')' || char === ']' || char === '}') {
      if (stack.isEmpty() || map[stack.pop()] !== char) {
        return false;
      }
    }
  }

  return stack.isEmpty();
}

扩展实现：最小栈

设计一个能在O(1)时间内获取最小元素的栈：

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

  push(val) {
    this.stack.push(val);
    if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
      this.minStack.push(val);
    }
  }

  pop() {
    const val = this.stack.pop();
    if (val === this.minStack[this.minStack.length - 1]) {
      this.minStack.pop();
    }
    return val;
  }

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

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