当前位置：首页 > JavaScript

js实现栈

2026-03-01 01:49:14JavaScript

栈的基本概念

栈是一种遵循后进先出（LIFO）原则的数据结构，只允许在栈顶进行插入（push）和删除（pop）操作。栈常用于函数调用、表达式求值等场景。

使用数组实现栈

数组是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());
  }
}

使用对象实现栈

对象实现栈可以避免数组的push和pop方法的时间复杂度问题，适合对性能要求较高的场景。

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;
  }
}

栈的应用示例

十进制转二进制

利用栈可以将十进制数转换为二进制数。

function decimalToBinary(decNumber) {
  const stack = new Stack();
  let number = decNumber;
  let rem;
  let binaryString = "";

  while (number > 0) {
    rem = Math.floor(number % 2);
    stack.push(rem);
    number = Math.floor(number / 2);
  }

  while (!stack.isEmpty()) {
    binaryString += stack.pop().toString();
  }

  return binaryString || "0";
}

平衡圆括号

栈可以用于检查表达式中的圆括号是否平衡。

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

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

  return stack.isEmpty();
}