当前位置：首页 > JavaScript

js堆栈实现

2026-04-06 03:08:43JavaScript

堆栈的基本概念

堆栈（Stack）是一种遵循后进先出（LIFO）原则的数据结构。主要操作包括压栈（push）和弹栈（pop），还可以包含查看栈顶元素（peek）等辅助操作。

数组实现堆栈

使用数组实现堆栈是最直观的方式，通过维护一个指针（如top）来跟踪栈顶位置。

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

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

链表实现堆栈

链表实现的堆栈在动态内存分配方面更灵活，每个节点包含数据和指向下一个节点的指针。

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

  peek() {
    if (this.isEmpty()) return null;
    return this.top.value;
  }

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

  getSize() {
    return this.size;
  }
}

// 使用示例
const llStack = new LinkedListStack();
llStack.push(100);
llStack.push(200);
console.log(llStack.pop()); // 输出200

堆栈的应用场景

堆栈常用于需要回溯操作的场景，例如：

浏览器历史记录（前进/后退功能）
函数调用栈（执行上下文管理）
括号匹配等语法检查
深度优先搜索（DFS）算法

性能对比

数组实现的堆栈在JavaScript引擎中通常性能较好，因为数组操作经过高度优化。链表实现虽然理论上在某些操作上有优势，但实际在JavaScript中可能因对象创建开销而稍慢。

错误处理

实现时需要考虑边界条件，例如：

js堆栈实现

空栈时调用pop()或peek()
栈大小限制（如有）时调用push()

// 增强错误处理的pop方法示例
pop() {
  if (this.isEmpty()) {
    throw new Error("Stack underflow: Cannot pop from empty stack");
  }
  return this.items.pop();
}

以上实现提供了堆栈的核心功能，可根据具体需求进行扩展，如添加迭代器、序列化等方法。