当前位置：首页 > JavaScript

js实现栈

2026-01-30 10:44:56JavaScript

栈的基本概念

栈是一种遵循后进先出（LIFO）原则的数据结构。元素的添加和移除只能在栈顶进行。常见操作包括压栈（push）、弹栈（pop）、查看栈顶元素（peek）以及检查栈是否为空。

基于数组的实现

使用数组可以简单高效地实现栈结构。数组的末尾作为栈顶，push和pop操作的时间复杂度均为O(1)。

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

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

  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items[this.items.length - 1];
  }

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

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

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

基于对象的实现

对于需要更严格控制内存的场景，可以使用对象来存储栈元素，并通过变量跟踪栈顶位置。

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

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

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

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

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

  size() {
    return this.count;
  }

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

栈的应用示例

栈在算法中有广泛应用，例如括号匹配、表达式求值、函数调用栈等。以下是一个括号匹配的示例：

js实现栈

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

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