当前位置：首页 > JavaScript

js堆栈实现

2026-03-14 09:03:45JavaScript

堆栈的基本概念

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

使用数组实现堆栈

数组实现堆栈简单直观，通过维护一个栈顶指针（或索引）来操作数据。

js堆栈实现

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) return null;
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) return null;
    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 null;
    const poppedValue = this.top.value;
    this.top = this.top.next;
    this.size--;
    return poppedValue;
  }

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

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

  getSize() {
    return this.size;
  }

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

堆栈的应用场景

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

js堆栈实现

函数调用栈
括号匹配检查
表达式求值（如逆波兰表达式）
浏览器历史记录（前进后退）
撤销操作（Undo/Redo）

性能比较

数组实现的堆栈在大多数现代JavaScript引擎中性能较好，因为数组操作经过高度优化。链表实现避免了数组的动态扩容开销，但在JavaScript中可能因对象创建和垃圾回收导致性能略低。实际选择取决于具体场景和性能测试结果。

扩展功能

可以基于基础堆栈实现扩展功能，例如：

支持迭代的堆栈（实现Symbol.iterator）
限制大小的堆栈（固定容量）
双栈结构（用于特殊算法需求）

// 可迭代堆栈示例
class IterableStack extends Stack {
  [Symbol.iterator]() {
    let index = this.items.length - 1;
    return {
      next: () => ({
        value: this.items[index--],
        done: index < -1
      })
    };
  }
}