js栈实现

JavaScript 栈的实现方法

使用数组实现栈

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 undefined;
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }

  peek() {
    if (this.isEmpty()) return undefined;
    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;
  }
}

栈的典型应用

1. 函数调用栈：JavaScript 引擎使用调用栈管理函数调用
2. 括号匹配：检查表达式中的括号是否成对出现
3. 进制转换：将十进制数转换为其他进制
4. 撤销操作：编辑器中的撤销功能通常使用栈实现

性能考虑

• 数组实现的栈在大部分现代 JavaScript 引擎中性能良好
• 对象实现的栈在频繁插入删除操作时可能更高效
• 实际应用中应根据具体场景选择实现方式

注意事项

• 栈操作需要处理边界情况，如空栈时的 pop 操作
• JavaScript 的数组本身是动态的，不需要预先分配固定大小
• 在实际项目中可以考虑使用现成的库如 immutable.js 的栈实现