基础知识

约 3289 字大约 11 分钟

2025-07-01

前端算法中，栈（Stack）、队列（Queue） 和 堆（Heap） 是三种非常重要且基础的数据结构。它们在解决特定类型的问题时非常高效。虽然 JavaScript/TypeScript 等前端语言没有直接内置堆的实现（需要手动模拟或使用类库），但理解和掌握它们对提升算法能力和解决复杂问题至关重要。下面详细介绍它们的基础知识、特点、应用场景以及解题思路和方法。

一、栈（Stack）

基本概念（后进先出 - LIFO）：
- 栈是一种操作受限的线性表。
- 只允许在数据结构的一端（称为栈顶 - Top）进行数据的插入（Push） 和 删除（Pop） 操作。
- 最后放入的元素总是第一个被取出，就像一摞盘子，你只能拿走最上面（最后放）的那个。
- 常用操作：push（入栈）、pop（出栈并返回栈顶元素）、peek/top（仅返回栈顶元素不移除，JS数组可以用array[array.length-1]）、isEmpty、size。
实现方式（前端）：
- 数组（Array）：最常用。使用 push 和 pop 方法即可完美模拟栈。

let stack = [];
stack.push(1); // [1]
stack.push(2); // [1, 2]
let top = stack.pop(); // 2, stack = [1]
let currentTop = stack[stack.length - 1]; // 1 (peek)

核心特点与适用场景：
- 需要“撤销”操作的场景：浏览器历史记录（前进/后退栈）、编辑器撤销操作。
- 函数调用栈：编程语言管理函数调用和返回地址。
- 表达式求值（中缀转后缀，后缀表达式求值）。
- 括号匹配问题：{[()]} 等。
- 深度优先搜索（DFS）：在树或图的遍历中，通常用栈来模拟递归过程（显式栈代替递归的隐式调用栈）。
- 方向逆转：当需要逆序处理数据时。
解题思路与方法：
- 匹配性问题：遇到“开启符”（如 (, [, {）入栈，遇到“关闭符”（如 ), ], }）则检查栈顶是否匹配，匹配则出栈，否则不合法。遍历结束，栈应为空。
  - LeetCode实例：20. Valid Parentheses
- 单调栈：维护一个栈内元素保持单调性（单调递增或单调递减）。常用于解决“下一个更大元素（Next Greater Element）”、“柱状图中的最大矩形”、“接雨水”等问题。思路是遍历数组，对于每个元素，若破坏栈的单调性，则弹出栈顶元素并计算结果，直到栈空或满足单调性后压入当前元素。
  - LeetCode实例：84. Largest Rectangle in Histogram, 42. Trapping Rain Water, 739. Daily Temperatures。
- DFS迭代模拟：用栈显式模拟递归调用过程。将初始节点入栈，循环中取出节点处理，并将其子节点按顺序入栈（注意入栈顺序，通常是逆序）。
  - LeetCode实例：144. Binary Tree Preorder Traversal (迭代法)
- 逆序输出/计算：栈天然支持逆序操作。

二、队列（Queue）

基本概念（先进先出 - FIFO）：
- 队列也是一种操作受限的线性表。
- 只允许在一端（称为队尾 - Rear / Tail） 进行插入（Enqueue） 操作，在另一端（称为队头 - Front / Head） 进行删除（Dequeue） 操作。
- 最先放入的元素最先被取出，就像在银行排队，先来的人先服务。
- 常用操作：enqueue（入队）、dequeue（出队并返回队头元素）、front/peek（仅返回队头元素不移除，JS数组可以用array[0]）、isEmpty、size。
实现方式（前端）：
- 数组（Array）：可用，但使用 shift 进行 dequeue 操作时性能较差（O(n)时间复杂度，因为需要移动所有元素）。对于普通需求或小型数据没问题。
- 链表：更高效（O(1)的 enqueue 和 dequeue）。JS 可以使用对象（节点指针）模拟，或使用 Map。

let queue = [];
queue.push(1); // [1] (Enqueue at Rear)
queue.push(2); // [1, 2]
let front = queue.shift(); // 1, queue = [2] (Dequeue from Front)
let currentFront = queue[0]; // 2 (peek front)

核心特点与适用场景：
- 任务调度：打印机队列、CPU 任务调度、消息队列（JavaScript的微任务队列/宏任务队列本质上是队列）。
- 广度优先搜索（BFS）：在树或图的遍历中，通常用队列来管理待访问的节点层级。
- 数据缓冲流：数据传输或处理速率不一致时需要缓冲。
- 模拟排队：任何按先后顺序处理请求的场景。
解题思路与方法：
- BFS（层序遍历）：将起始节点入队。循环中，取出队头节点处理，并将其所有未访问过的相邻节点入队。不断重复直到队列为空。适用于最短路径（无权图）、连通块、最小步数等问题。
  - LeetCode实例：102. Binary Tree Level Order Traversal, 111. Minimum Depth of Binary Tree, 279. Perfect Squares, 127. Word Ladder。
- 滑动窗口（Sliding Window）：常用于处理数组/字符串的子串/子区间问题（如“无重复字符的最长子串”、“和为K的连续子数组”、“滑动窗口最大值”等）。双端队列（Deque）在此类问题中非常高效。
  - 经典实现（滑动窗口最大值 - 239）：使用单调队列（双端队列维护窗口内元素的单调递减顺序）。遍历数组，保证队头是窗口内最大值。窗口滑动时，移除出窗口的元素，新元素从队尾开始移除所有小于它的元素后入队。每次窗口形成后，队头即为当前窗口最大值。
  - LeetCode实例：239. Sliding Window Maximum, 3. Longest Substring Without Repeating Characters (有时也用HashSet+双指针)，76. Minimum Window Substring, 567. Permutation in String。
- 普通 FIFO 管理：直接使用队列模拟排队过程。

三、堆（Heap） / 优先队列（Priority Queue）

基本概念：
- 堆是一种特殊的完全二叉树，满足堆属性（Heap Property）：
  - 最大堆（Max-Heap）：父节点的值 总是大于或等于 其任一子节点的值。（根节点最大）
  - 最小堆（Min-Heap）：父节点的值 总是小于或等于 其任一子节点的值。（根节点最小）
- 优先队列（Priority Queue） 是一种抽象数据类型，其行为类似于队列，但每个元素都具有一个“优先级”。具有最高优先级的元素最先出队（相当于队头）。堆是实现优先队列最常用、最高效的数据结构。因此，在算法中，“堆”和“优先队列”常常可以互换使用。JavaScript 没有内置堆，但可以用数组实现。
- 常用操作：insert / add / offer（插入一个元素）、poll（删除并返回堆顶元素）、peek（返回堆顶元素不移除）、size、isEmpty。核心操作 insert 和 poll（或 removeMax/removeMin）的时间复杂度通常是 O(log n)。
实现方式（前端模拟）：
- 数组（Array）模拟二叉堆（最常见）：
  - 索引规则（假设根节点索引为 0）：
    - 父节点索引：parent(i) = Math.floor((i - 1) / 2)
    - 左孩子索引：leftChild(i) = 2 * i + 1
    - 右孩子索引：rightChild(i) = 2 * i + 2
  - 关键操作：
    - insert(val)：将元素添加到数组末尾，然后进行 siftUp（堆化向上调整）：将该节点与其父节点比较，如果违反堆属性则交换位置，直到满足堆属性或到达根节点。
    - poll()：取出堆顶（数组第一个元素）。将数组末尾元素移到堆顶（索引0），然后进行 siftDown（堆化向下调整）：将该节点与其较大（最大堆）/**较小（最小堆）**的孩子比较并交换（若违反堆属性），直到满足堆属性或成为叶子节点。
  - 堆构建（Heapify）：将一个无序数组转换为堆。高效方法是 O(n)时间复杂度：从 最后一个非叶子节点（索引为 Math.floor(size/2 - 1)） 开始，自底向上、自右向左地对每个节点执行 siftDown 操作。
核心特点与适用场景：
- 需要快速访问最大值或最小值的场景。
- 动态数据流中的 Top K 问题：求最大/最小的 K 个元素（解决这类问题最小堆/最大堆有不同的适用场景）。
- 优先任务调度：按优先级处理任务（如高优先级的系统进程）。
- 堆排序（基于堆的排序算法，但前端直接使用 sort 方法更常见）。
- 图算法：Dijkstra 最短路径算法（使用最小堆高效地选择当前最小距离的顶点）、Prim 最小生成树算法。
- 中位数查找：动态维护数据流的中位数（通常使用两个堆：一个最大堆存较小的一半，一个最小堆存较大的一半）。
解题思路与方法：
- Top K 问题：
  - 求最大(前)K个元素（或Kth Largest）：
    - 方法1（小顶堆）：维护一个大小为 K 的 最小堆。遍历数据流，比堆顶大的元素替换堆顶（poll + insert），堆中始终存放迄今为止遇到的最大的K个数，堆顶是这K个中最小的一个，即第K大的数。时间复杂度 O(n log K)。
    - 方法2（快速选择）：类似快速排序的分区思想，平均 O(n)，最坏 O(n²)。
  - 求最小(前)K个元素（或Kth Smallest）：
    - 方法1（大顶堆）：维护一个大小为 K 的 最大堆。遍历数据流，比堆顶小的元素替换堆顶，堆中存放最小的K个数，堆顶是这K个中最大的一个，即第K小的数。时间复杂度 O(n log K)。
  - LeetCode实例：215. Kth Largest Element in an Array, 347. Top K Frequent Elements, 692. Top K Frequent Words。
- 中位数查找（数据流）：
  - 维护两个堆：
    - lo（低半部分）为一个最大堆（存放较小的一半元素，堆顶是该部分的最大值）。
    - hi（高半部分）为一个最小堆（存放较大的一半元素，堆顶是该部分的最小值）。
  - 保证：lo.size() == hi.size()（偶数个时）或 lo.size() == hi.size() + 1（奇数个时，保证中位数在 lo 堆顶）。
  - addNum(num)：
    - 初始向任一堆添加（如lo）。
    - 后续添加：如果 num <= lo.peek()，则加入 lo；否则加入 hi。
    - 调整平衡：如果 lo.size() < hi.size()，将 hi 堆顶移到 lo；如果 lo.size() > hi.size() + 1，将 lo 堆顶移到 hi。
  - findMedian()：如果 lo.size() > hi.size()，返回 lo.peek()；否则返回 (lo.peek() + hi.peek()) / 2.0。
  - LeetCode实例：295. Find Median from Data Stream。
- 模拟优先队列：直接调用堆的操作来调度任务。

四、如何选择与综合应用

栈 vs 队列：
- 顺序：需要 “撤销”、“回溯”、“匹配”、"逆序" -> 栈。需要 “排队”、“公平性”、“层级遍历”、“依赖顺序” -> 队列。
- 树/图遍历：深度优先（DFS） -> 栈。广度优先（BFS） -> 队列。
- 滑动窗口：通常用队列（尤其是双端队列） 维护窗口内的元素。
堆（优先队列） vs 栈/队列：
- 当你只需要按严格的顺序（FIFO/LIFO）处理元素时，用栈或队列。
- 当你需要根据某种优先级（大小、频率等） 动态决定下一个处理哪个元素时，用堆（优先队列）。
综合应用：
- 复杂问题可能需要结合使用多种数据结构。例如：
  - 图的 Dijkstra 算法：用队列管理路径（BFS思想），但用 最小堆 选择当前最短路径点。
  - 设计一个可以快速获取最小值的栈：用一个辅助栈同步记录当前最小值。
  - 栈 + 堆：某些调度问题。
- LeetCode 综合实例（带难度）：
  - 中等：853. Car Fleet (排序 + 单调栈)
  - 困难：23. Merge k Sorted Lists (堆/优先队列)
  - 困难：815. Bus Routes (图的BFS建模比较难)
  - 困难：895. Maximum Frequency Stack (栈+最大堆+哈希表)

五、学习与练习建议

理解本质：彻底理解每种结构的操作原理（LIFO, FIFO, 堆属性）和核心操作流程（入栈/出栈、入队/出队、插入/删除元素在堆中的 siftUp/siftDown 过程）。
亲手实现：特别是在JS中手动实现一个堆（包括insert, poll, siftUp, siftDown, heapify），这对深入理解其内部机制非常有帮助。
刻意练习：针对每种结构对应的经典题目类型进行集中练习。LeetCode、剑指Offer等都是很好的资源。初期可以按数据结构标签（Stack, Queue, Heap）刷题。
分析复杂度：思考每种操作的时间、空间复杂度，理解为什么在这种场景下使用这种数据结构是最优或最合适的。
模式总结：掌握常见的解题模式（如前所述的括号匹配、单调栈、BFS、Top K、中位数查找的堆用法、滑动窗口的队列用法）。
前端视角：思考这些数据结构在实际前端工作中的应用（如浏览器历史栈、任务队列、Promise回调队列、Redux中间件链式调用、性能监控、实现更复杂的UI功能等）。理解浏览器内部的调用栈、事件循环（微任务队列、宏任务队列）与队列的关系。

通过深入理解和熟练应用栈、队列和堆，你将能更高效、更优雅地解决大量前端算法面试题和工程中的复杂问题。这些是构建更高级算法和系统设计的基石。加油！