当前位置：首页 > JavaScript

js实现堆栈

2026-02-02 06:56:28JavaScript

使用数组实现堆栈

堆栈是一种遵循后进先出（LIFO）原则的数据结构。在JavaScript中，可以通过数组的push和pop方法实现堆栈的基本操作。

js实现堆栈

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

// 使用示例
const stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.pop()); // 输出 20
console.log(stack.peek()); // 输出 10

使用链表实现堆栈

链表实现堆栈可以避免数组的动态扩容问题，适合对性能要求较高的场景。

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedListStack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  // 入栈
  push(value) {
    const newNode = new Node(value);
    newNode.next = this.top;
    this.top = newNode;
    this.size++;
  }

  // 出栈
  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    const value = this.top.value;
    this.top = this.top.next;
    this.size--;
    return value;
  }

  // 查看栈顶元素
  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.top.value;
  }

  // 判断栈是否为空
  isEmpty() {
    return this.size === 0;
  }

  // 获取栈的大小
  getSize() {
    return this.size;
  }

  // 清空栈
  clear() {
    this.top = null;
    this.size = 0;
  }
}

// 使用示例
const linkedListStack = new LinkedListStack();
linkedListStack.push(30);
linkedListStack.push(40);
console.log(linkedListStack.pop()); // 输出 40
console.log(linkedListStack.peek()); // 输出 30

堆栈的应用示例

堆栈常用于解决需要回溯的问题，例如括号匹配、函数调用栈等。

// 括号匹配检查
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();
}

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