在计算机科学中，栈 (Stack) 是一种基本且极为重要的数据结构，它遵循后进先出 (Last In, First Out - LIFO) 的原则。想象一个堆叠的盘子：你只能从顶部添加新盘子，也只能从顶部取走盘子。最后放上去的盘子，总是第一个被拿走。栈的这种特性使其在许多算法和系统实现中发挥着核心作用，例如函数调用管理、表达式求值、浏览器历史记录、撤销/重做功能等。

理解栈的工作原理及其在 JavaScript 中的高效实现，对于编写健壮、可维护且高性能的代码至关重要。尽管 JavaScript 并没有内置的 Stack 类，但我们可以利用其强大的数组 (Array) 或链表 (Linked List) 特性，轻松地构建出功能完善的栈数据结构。

本教程将全面深入地探讨 JavaScript 中栈的实现和操作。我们将从栈的核心概念（LIFO 原则、基本操作）入手，详细剖析其工作原理。随后，我们将通过两种主要方式——基于数组和基于链表——逐步构建功能完善的栈实现，并详细解释其 push (入栈)、pop (出栈)、peek (查看栈顶)、isEmpty (判断是否为空) 和 size (获取大小) 等基本操作。我们还将讨论栈的主要应用场景，并对比不同实现方式的优劣，以及栈与其他数据结构（如队列）的区别。最后，我们将提供最佳实践和常见陷阱，帮助您彻底掌握 JavaScript 中的栈，为更高级的算法学习和系统设计奠定坚实基础。

1. 栈的核心概念

栈是一种线性数据结构，其特点是只允许在集合的一端进行插入和删除操作，这一端被称为栈顶 (Top)。

后进先出 (LIFO) 原则：
这是栈最核心的特性。这意味着最后添加到栈中的元素将是第一个被移除的元素。

栈的基本操作：

  1. push(element) (入栈)： 将一个新元素添加到栈顶。
  2. pop() (出栈)： 移除并返回栈顶的元素。
  3. peek() 或 top() (查看栈顶)： 返回栈顶的元素，但不将其移除。
  4. isEmpty() (判断是否为空)： 检查栈是否包含任何元素。
  5. size() (获取大小)： 返回栈中元素的数量。
  6. clear() (清空栈)： 移除栈中的所有元素。

栈的图示：

                  Stack Top
                 ^
                 |
                 |  [Element 3] (Last In)
                 |  [Element 2]
                 |  [Element 1] (First In)
                 V
                Stack Bottom

2. JavaScript 栈的实现

在 JavaScript 中，实现栈最常见且最有效的方法是利用数组的内置方法。为了更深入理解数据结构，我们也将探讨基于链表的实现。

2.1 基于数组的栈 (Array-based Stack) - 推荐

由于 JavaScript 数组的 push() 和 pop() 方法天然地提供了 LIFO 行为，使用数组实现栈非常简洁高效。

/**
 * @class ArrayStack
 * @description 基于 JavaScript 数组实现的栈数据结构
 */
class ArrayStack {
  /**
   * @constructor
   * 初始化一个空栈
   */
  constructor() {
    this.items = []; // 使用数组来存储栈中的元素
  }

  /**
   * @method push
   * @description 将元素添加到栈顶 (入栈)
   * @param {*} element - 要添加到栈中的元素
   * @returns {number} 栈中元素的数量
   * @timecomplexity O(1)
   */
  push(element) {
    this.items.push(element);
    return this.items.length; // 返回新栈的大小
  }

  /**
   * @method pop
   * @description 移除并返回栈顶的元素 (出栈)
   * @returns {*} 栈顶的元素，如果栈为空则返回 undefined
   * @timecomplexity O(1)
   */
  pop() {
    if (this.isEmpty()) {
      return undefined; // 或者可以抛出错误
    }
    return this.items.pop();
  }

  /**
   * @method peek
   * @description 返回栈顶的元素，但不移除它
   * @returns {*} 栈顶的元素，如果栈为空则返回 undefined
   * @timecomplexity O(1)
   */
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.items.length - 1];
  }

  /**
   * @method isEmpty
   * @description 检查栈是否为空
   * @returns {boolean} 如果栈为空则返回 true，否则返回 false
   * @timecomplexity O(1)
   */
  isEmpty() {
    return this.items.length === 0;
  }

  /**
   * @method size
   * @description 返回栈中元素的数量
   * @returns {number} 栈的当前大小
   * @timecomplexity O(1)
   */
  size() {
    return this.items.length;
  }

  /**
   * @method clear
   * @description 清空栈中的所有元素
   * @timecomplexity O(1)
   */
  clear() {
    this.items = [];
  }

  /**
   * @method toString
   * @description 将栈中的元素转换为字符串表示 (栈顶在右边)
   * @returns {string} 栈的字符串表示
   */
  toString() {
    return this.items.toString();
  }

  /**
   * @method print
   * @description 打印栈中的所有元素
   */
  print() {
    console.log(this.toString());
  }
}

使用示例：

const myStack = new ArrayStack();
console.log("Is stack empty?", myStack.isEmpty()); // true

myStack.push(10);
myStack.push(20);
myStack.push(30);
console.log("Stack after pushes:");
myStack.print(); // 10,20,30
console.log("Stack size:", myStack.size()); // 3

console.log("Top element (peek):", myStack.peek()); // 30

console.log("Popped element:", myStack.pop()); // 30
console.log("Stack after pop:");
myStack.print(); // 10,20
console.log("Stack size:", myStack.size()); // 2

console.log("Is stack empty?", myStack.isEmpty()); // false

myStack.clear();
console.log("Stack after clear:");
myStack.print(); // (空行)
console.log("Stack size:", myStack.size()); // 0

为什么数组实现通常是首选？
在 JavaScript 中，数组的 push() 和 pop() 方法经过高度优化，通常能在 O(1) 时间内完成操作。此外，数组在内存中的连续存储也有利于缓存命中，性能表现通常优于链表实现。

2.2 基于链表的栈 (Linked List-based Stack)

使用链表实现栈，通常是将其作为一种更纯粹的数据结构练习。栈的 push 操作对应于链表的头插 (prepend)，pop 操作对应于链表的头删 (removeHead)。

首先，我们需要一个 Node 类：

/**
 * @class Node
 * @description 代表链表中的一个节点
 */
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

/**
 * @class LinkedListStack
 * @description 基于单向链表实现的栈数据结构
 */
class LinkedListStack {
  /**
   * @constructor
   * 初始化一个空栈
   */
  constructor() {
    this.head = null; // 栈顶就是链表的头节点
    this.count = 0;   // 栈中元素的数量
  }

  /**
   * @method push
   * @description 将元素添加到栈顶 (入栈，对应链表的头插)
   * @param {*} element - 要添加到栈中的元素
   * @timecomplexity O(1)
   */
  push(element) {
    const newNode = new Node(element);
    newNode.next = this.head; // 新节点的 next 指向当前栈顶
    this.head = newNode;      // 更新栈顶为新节点
    this.count++;
  }

  /**
   * @method pop
   * @description 移除并返回栈顶的元素 (出栈，对应链表的头删)
   * @returns {*} 栈顶的元素，如果栈为空则返回 undefined
   * @timecomplexity O(1)
   */
  pop() {
    if (this.isEmpty()) {
      return undefined;
    }
    const removedData = this.head.data;
    this.head = this.head.next; // 栈顶指向下一个节点
    this.count--;
    return removedData;
  }

  /**
   * @method peek
   * @description 返回栈顶的元素，但不移除它
   * @returns {*} 栈顶的元素，如果栈为空则返回 undefined
   * @timecomplexity O(1)
   */
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.head.data;
  }

  /**
   * @method isEmpty
   * @description 检查栈是否为空
   * @returns {boolean} 如果栈为空则返回 true，否则返回 false
   * @timecomplexity O(1)
   */
  isEmpty() {
    return this.count === 0;
  }

  /**
   * @method size
   * @description 返回栈中元素的数量
   * @returns {number} 栈的当前大小
   * @timecomplexity O(1)
   */
  size() {
    return this.count;
  }

  /**
   * @method clear
   * @description 清空栈中的所有元素
   * @timecomplexity O(1)
   */
  clear() {
    this.head = null;
    this.count = 0;
  }

  /**
   * @method print
   * @description 打印栈中的所有元素
   */
  print() {
    if (this.isEmpty()) {
      console.log("Stack is empty.");
      return;
    }
    let current = this.head;
    let stackValues = [];
    while (current) {
      stackValues.push(current.data);
      current = current.next;
    }
    console.log("TOP -> " + stackValues.join(" -> ") + " -> BOTTOM");
  }
}

使用示例：

const myLinkedListStack = new LinkedListStack();
console.log("\n--- Linked List Stack ---");
console.log("Is stack empty?", myLinkedListStack.isEmpty()); // true

myLinkedListStack.push("A");
myLinkedListStack.push("B");
myLinkedListStack.push("C");
console.log("Stack after pushes:");
myLinkedListStack.print(); // TOP -> C -> B -> A -> BOTTOM
console.log("Stack size:", myLinkedListStack.size()); // 3

console.log("Top element (peek):", myLinkedListStack.peek()); // C

console.log("Popped element:", myLinkedListStack.pop()); // C
console.log("Stack after pop:");
myLinkedListStack.print(); // TOP -> B -> A -> BOTTOM
console.log("Stack size:", myLinkedListStack.size()); // 2

myLinkedListStack.clear();
console.log("Stack after clear:");
myLinkedListStack.print(); // Stack is empty.

3. 栈的常见应用场景

栈因其 LIFO 特性，在许多计算机科学领域都有广泛应用：

  1. 函数调用栈 (Call Stack)： 当一个函数被调用时，它的执行上下文（包括局部变量、参数和返回地址）会被推入调用栈。函数执行完毕后，其上下文从栈中弹出，程序回到上一个函数的执行点。这是理解程序执行流程和递归的关键。
  2. 表达式求值： 编译器使用栈来解析和评估算术表达式（例如，将中缀表达式转换为后缀表达式，然后求值）。
  3. 撤销/重做功能 (Undo/Redo)： 许多应用程序（如文本编辑器、图形设计软件）使用栈来存储用户的操作历史，以便进行撤销和重做。
  4. 浏览器历史记录： 浏览器的“后退”按钮功能可以通过栈来实现。访问的每个页面都被推入栈，点击后退时弹出当前页面，显示上一个页面。
  5. 语法解析： 编译器和解释器使用栈来检查编程语言的语法结构，例如括号匹配、标签闭合等。
  6. 深度优先搜索 (DFS)： 在图或树的遍历中，DFS 算法通常使用栈（或递归，其底层也是调用栈）来记录待访问的节点。
  7. 回溯算法： 许多解决问题的方法，如迷宫求解、八皇后问题，都利用栈来记录路径，并在遇到死胡同时代替回溯点。

4. 栈与其他数据结构

  • 与数组的区别： 栈是基于数组（或链表）实现的抽象数据类型，它只允许在特定位置（栈顶）进行操作。数组则允许随机访问和在任意位置进行操作。
  • 与队列 (Queue) 的区别： 队列遵循 FIFO (First In, First Out) 原则，即第一个进入队列的元素也是第一个离开队列的元素，类似于排队。队列的主要操作是 enqueue (入队) 和 dequeue (出队)。

5. 最佳实践与常见陷阱

  • 选择合适的实现： 在 JavaScript 中，通常推荐使用数组来实现栈，因为它简单、高效且 JavaScript 引擎对数组操作进行了大量优化。只有在极少数特定场景下（例如，需要精确控制内存分配，或避免数组动态调整大小带来的潜在开销），才考虑链表实现。
  • 边界条件处理： 在实现 pop() 和 peek() 等操作时，务必检查栈是否为空，以避免访问 undefined 或抛出错误。
  • 命名规范： 坚持使用标准的栈操作名称 (push, pop, peek, isEmpty, size)，提高代码可读性。
  • 时间复杂度： 栈的所有基本操作（push, pop, peek, isEmpty, size）都应该在 O(1) 的时间复杂度内完成。这是栈设计的核心优势。

6. 总结与展望

栈作为一种遵循 LIFO 原则的抽象数据类型，是计算机科学中最基础且用途广泛的数据结构之一。

  • 核心： 后进先出 (LIFO)，只在栈顶进行操作。
  • 基本操作： push (入栈)、pop (出栈)、peek (查看栈顶)、isEmpty (判断是否为空)、size (获取大小)。
  • 实现方式：
    • 数组实现 (推荐)： 简洁、高效，利用 Array.prototype.push() 和 Array.prototype.pop()。
    • 链表实现： 更“纯粹”的数据结构实现，push 对应头插，pop 对应头删。
  • 时间复杂度： 所有核心操作均为 O(1)。
  • 应用： 函数调用栈、表达式求值、撤销/重做、浏览器历史、DFS 等。

通过深入理解栈的这些特性和实现方式，您将能够更有效地解决涉及元素顺序和生命周期管理的问题，为构建更复杂的算法和应用程序打下坚实的基础。

# javascript # 数据结构 # udp
Logo
AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

cover

深度 | Venice 2nm 256核发布一周：产能、竞品、市场三件事全变了

avatar AI Agent技术社区
cover

编排思想的跨域升华：从 DAG 调度到 AI Agent

avatar AI Agent技术社区

AI Agent 前端自学路线（firstDay)

‌、‌。

avatar AI Agent技术社区