当前位置：首页 > JavaScript

js堆栈实现

2026-02-01 10:26:46JavaScript

堆栈的基本概念

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

使用数组实现堆栈

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

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 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 poppedValue = this.top.value;
    this.top = this.top.next;
    this.size--;
    return poppedValue;
  }

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

堆栈的应用场景

堆栈在编程中有广泛的应用，例如函数调用栈、表达式求值、括号匹配、回溯算法等。

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