当前位置：首页 > JavaScript

js 堆栈实现

2026-01-30 13:12:10JavaScript

堆栈的基本概念

堆栈（Stack）是一种遵循后进先出（LIFO）原则的数据结构。主要操作包括压栈（push）和弹栈（pop），其他常见操作有查看栈顶元素（peek）和判断栈是否为空（isEmpty）。

使用数组实现堆栈

数组是实现堆栈的简单方式，通过维护一个指针（通常称为top）来跟踪栈顶位置。

class Stack {
  constructor() {
    this.items = [];
    this.top = -1; // 初始状态下栈为空
  }

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

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

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

  isEmpty() {
    return this.top === -1;
  }

  size() {
    return this.top + 1;
  }

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

使用链表实现堆栈

链表实现堆栈更灵活，动态内存分配避免了数组的固定大小限制。

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

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

  push(value) {
    const newNode = new Node(value);
    newNode.next = this.top;
    this.top = newNode;
    this.length++;
  }

  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    const poppedNode = this.top;
    this.top = this.top.next;
    this.length--;
    return poppedNode.value;
  }

  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.top.value;
  }

  isEmpty() {
    return this.top === null;
  }

  size() {
    return this.length;
  }

  clear() {
    this.top = null;
    this.length = 0;
  }
}

堆栈的应用场景

堆栈常用于需要回溯或反转的场景，例如：

函数调用栈：记录函数的调用顺序。
括号匹配：检查表达式中的括号是否成对。
撤销操作：保存操作历史以便回退。

示例：括号匹配

使用堆栈检查字符串中的括号是否匹配：

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