js实现stack

使用数组实现栈

JavaScript中可以用数组模拟栈的行为，数组的push()和pop()方法天然符合栈的后进先出（LIFO）特性。

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 = [];
  }
}

使用对象实现栈

对于需要更高性能的场景，可以用对象存储元素，通过维护count变量跟踪栈顶位置。

class Stack {
  constructor() {
    this.count = 0;
    this.items = {};
  }

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

  pop() {
    if (this.isEmpty()) return undefined;
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }
}

栈的典型应用

实现括号匹配检查器：

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

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

时间复杂度分析

• push(): O(1)
• pop(): O(1)
• peek(): O(1)
• size(): O(1)

数组实现的栈在内存分配满时需要扩容，可能偶尔导致push操作变为O(n)，但均摊时间复杂度仍为O(1)。

注意事项

1. 边界情况处理：执行pop()或peek()时应检查栈是否为空
2. 实际项目中可直接使用数组作为栈，无需单独实现类
3. 对象实现的栈相比数组实现更节省内存，但代码复杂度稍高
4. 栈常用于算法中的深度优先搜索(DFS)、函数调用栈等场景