用js实现堆栈

使用数组实现堆栈

堆栈是一种遵循后进先出（LIFO）原则的数据结构。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());
  }
}

使用对象实现堆栈

对于需要更高性能的场景，可以使用对象来实现堆栈，避免数组方法带来的额外开销。

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

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

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

  peek() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    return this.items[this.count - 1];
  }

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

  size() {
    return this.count;
  }

  clear() {
    this.items = {};
    this.count = 0;
  }

  toString() {
    if (this.isEmpty()) {
      return "";
    }
    let objString = `${this.items[0]}`;
    for (let i = 1; i < this.count; i++) {
      objString = `${objString},${this.items[i]}`;
    }
    return objString;
  }
}

使用闭包实现堆栈

闭包可以创建私有变量，保护堆栈内部数据不被外部直接访问。

const Stack = (function() {
  const items = new WeakMap();

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

    push(element) {
      const s = items.get(this);
      s.push(element);
    }

    pop() {
      const s = items.get(this);
      return s.pop();
    }

    peek() {
      const s = items.get(this);
      return s[s.length - 1];
    }

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

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

    clear() {
      items.set(this, []);
    }

    toString() {
      return items.get(this).toString();
    }
  }

  return Stack;
})();

堆栈的实际应用示例

堆栈常用于解决需要后进先出处理的场景，如括号匹配、函数调用栈、撤销操作等。

// 括号匹配检查
function isBalanced(exp) {
  const stack = new Stack();
  const map = {
    '(': ')',
    '[': ']',
    '{': '}'
  };

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

  return stack.isEmpty();
}

console.log(isBalanced("{([])}")); // true
console.log(isBalanced("{[}]"));   // false

每种实现方式各有优缺点，数组实现简单直观，对象实现性能更优，闭包实现提供了更好的封装性。根据具体应用场景选择最适合的实现方式。