Engineering Review Lab

Appearance

栈、队列与堆（优先队列）基础与工程应用 ​

回到总览：00 基础知识（Foundations）相关模块：Android 主线程消息循环：Looper / Handler / MessageQueue延伸阅读：如果你这里关心的是 Android 主线程里的 MessageQueue，可把它理解为"以消息循环为入口、以时间排序为调度约束"的工程化消息队列：普通场景接近 FIFO，但一旦引入 postDelayed / when，真正决定先后的是"谁先到期"，因此它在调度行为上更接近"带时间优先级的队列"。

一句话定义 ​

栈（Stack，后进先出 LIFO）、队列（Queue，先进先出 FIFO）与堆（Heap，通常落地为优先队列 PriorityQueue）是移动端最常见的三类调度容器：栈负责“回退/撤销/调用嵌套”，队列负责“排队/串行消费/消息循环”，堆负责“按优先级挑下一个任务”，三者差异直接决定 Android / Flutter 工程里的路由、消息、延迟任务与 Top-K 选型。

代码索引 ​

主题Lab 说明源码
队列策略对照queue-strategy-compareQueueStrategyCompare.java

为什么需要 ​

  • 为什么 Android 主线程明明叫 MessageQueue，但实际调度又不能简单理解成 FIFO？
    • 一句话答：MessageQueue 对“立即消息”近似 FIFO，但一旦出现 postDelayed / when，真正决定先后的是“谁先到期”，所以它更像“带时间优先级的队列”。
  • 为什么 Android / Flutter 工程师要把“栈、队列、堆”分开，而不是笼统记成“容器”？
    • 一句话答：三者对应的是三种完全不同的系统约束：栈解决回退与嵌套调用，队列解决串行排队，堆解决优先级调度；容器模型选错，路由、消息、定时任务都会出事故。
  • 为什么 ArrayDeque 在 Java/Kotlin 里常同时替代 Stack 和 LinkedList？
    • 一句话答：ArrayDeque 基于循环数组，头尾操作都是 O(1) 且没有 Stack 的历史同步开销、也没有 LinkedList 的节点对象膨胀，是大多数单线程栈/队列场景的默认选择。

底层机制 ​

1. 三类容器的核心语义 ​

先不要背 API，先记“谁先出来”：

  • 栈（LIFO） ：最后压进去的元素最先弹出，适合“最近进入、最先回退”的场景。
  • 队列（FIFO） ：最早进入的元素最先处理，适合“按到达顺序串行消费”的场景。
  • 堆 / 优先队列：不是按进入时间，而是按比较器选“当前最值得先处理”的元素，适合定时器、优先级任务、Top-K。

先看一张并排对比图，再记 API：

  • 栈：push() 和 pop() 都只作用在顶部，所以最后压入的元素会最先弹出。
  • 队列：offer() 把元素放到队尾，poll() 从队头取走元素，所以最早进入的元素会最先被处理。
  • 小顶堆：poll() 总是先取出当前最小值；它不按进入先后决定顺序，而是按当前比较结果决定谁先出来。

这张图回答的是“三者出队规则有什么差异”，还没展开“堆在内部是怎么维护这个最小值的”。下面第 2、3 节就是专门解释：

  • 小顶堆数组为什么不是全局有序
  • offer() 时为什么会发生上浮（shift up / sift up）
  • poll() 时为什么会发生下沉（shift down / sift down）

复杂度对比表 ​

容器插入复杂度弹出复杂度顶端查询Java / Kotlin 常见实现
栈O(1)O(1)O(1)ArrayDeque
队列O(1)O(1)O(1)ArrayDeque / LinkedList
优先队列O(log N)O(log N)O(1)PriorityQueue（二叉堆）

2. 为什么堆不是“排序后的数组” ​

很多人第一次接触堆会误以为“既然堆顶总是最小/最大，那整个数组应该已经排好序”。这是错的。堆只保证：父节点优先级高于子节点，不保证兄弟节点有序，也不保证整棵树中序遍历有序。

数组表示的小顶堆与树形映射

  • 这里 3 < 8/5、8 < 12/20、5 < 9，所以是合法小顶堆。
  • 但数组并不是全局有序：8 在 5 前面，不代表 8 < 5。

这个约束非常重要，因为它解释了：

  • peek() 只要看堆顶，所以是 O(1)。
  • offer() / poll() 只需要沿父子路径“上浮 / 下沉”，所以是 O(log N)。
  • 若你真的想全局有序，最终还得不断 poll() 或额外排序。

3. 上浮与下沉：优先队列真正的维护成本 ​

先把两个名字解释清楚：

  • 上浮（shift up / sift up） ：新元素先插到数组末尾；如果它比父节点更小，就一路向上交换，直到父节点不再比它大，或者它已经来到根节点。
  • 下沉（shift down / sift down） ：堆顶被拿走后，把最后一个元素临时放到根；如果它比某个子节点更大，就和更小的那个子节点交换，一路往下沉，直到重新满足小顶堆约束。

可以把它们分别理解成：

  • 上浮 = “新来的值太小了，应该往更高优先级的位置爬”
  • 下沉 = “临时顶上来的值太大了，应该往更低优先级的位置掉”
java
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(8);
minHeap.offer(3);
minHeap.offer(5);
minHeap.offer(12);
System.out.println(minHeap.peek()); // 3
System.out.println(minHeap.poll()); // 3
System.out.println(minHeap.peek()); // 5
  • 为什么是堆 / 优先队列：你关心的不是“谁先进入”，而是“当前最小 / 最大 / 最先到期的是谁”。
  • 可能执行顺序
    1. offer(8)：堆只有一个节点。
    2. offer(3)：插到尾部，发现 3 < 8，向上交换一次。
    3. offer(5)：插到尾部，与父节点比较后停下。
    4. poll()：取出堆顶 3，把最后一个节点移到根，再不断向下与更小的子节点交换。
  • 可能输出
    text
    3
3
5
  • 预期现象
    • 堆顶始终是“当前优先级最高的元素”。
    • 插入和弹出都不会全量重排，只修复一条根到叶子的路径。
  • 观察重点
    • PriorityQueue 不保证遍历顺序就是优先级顺序。
    • 如果业务需要稳定顺序（同优先级按进入时间先后），要自己在比较器里补 sequenceId。

4. Android 消息循环为什么更像“时间优先队列 + 串行消费器” ​

对应 Lab：queue-strategy-compare · QueueStrategyCompare.java深入阅读：Android 主线程消息循环：Looper / Handler / MessageQueue对应 Lab（主线程消息循环） ：looper-handler-demo · LooperHandlerDemoActivity.kt

Android Looper 背后的 MessageQueue 有两个必须同时记住的特性：

  1. 同一线程串行消费：主线程一次只处理一条消息，这一点像普通队列。
  2. 按 when 选下一条可执行消息：延迟消息不按插入时间直接出队，而是按到期时间排序，这一点又像优先调度。

工程上可以这样理解：

  • post {} / sendMessage()：接近普通 FIFO。
  • postDelayed(500) / sendMessageAtTime()：进入“到期时间排序”。
  • sync barrier / Choreographer 帧消息：又在“时间排序”之外叠加了优先级插队。

所以如果你把主线程消息循环完全等同于“排队叫号”，会误判很多现象：

  • 为什么一个后发的立即消息会先于更早插入、但尚未到期的延迟消息执行。
  • 为什么动画、输入、绘制在某些时刻能抢占普通业务消息。

5. 栈不只存在于算法题，也存在于路由与异常恢复 ​

栈最常见的工程映射，不是“背一个 push/pop”，而是：

  • Android 返回栈：Activity A → B → C，按 Back 时 C、B、A 倒序退出。
  • Flutter Navigator 栈：push 详情页，pop 回主页，本质也是 LIFO。
  • 撤销 / 重做：最近一次编辑最先被撤销。
  • 递归调用栈：函数嵌套越深，栈帧越深；递归没有收口就会栈溢出。

一个典型误判是：把“可随机跳转的页面集合”也用栈思维理解。实际上：

  • Tab 切换通常不是栈，而是并列状态切换。
  • Deep Link 恢复时可能一次性重建多层栈，但恢复逻辑本身不是“逐个用户点击 push”来的。

Android / Flutter / Web / Backend 对照 ​

场景Android / KotlinFlutter / DartWeb / Backend判断重点
页面回退Activity Task / FragmentManager 回退栈Navigator / Router 页面栈浏览器 history stack都是“最近进入先退出”，但 Flutter 更容易自定义路由恢复逻辑
串行消息消费Looper + MessageQueueevent loop + event queueNode.js event loop / 单线程队列消费者名字都叫 queue，但延迟任务常带时间优先级
优先任务调度PriorityQueue、DelayQueue、定时消息Timer、自建优先调度器JVM 定时任务、任务调度中心真正关心的是“谁先处理”，而不是“谁先进来”
Top-K / 最近任务PriorityQueueHeapPriorityQueue（第三方）/ 手写堆Redis ZSet / 服务端小顶堆若只要 K 个最值，小顶堆通常优于全排序

iOS 这里只做必要对照：UINavigationController 也可类比页面栈，但本页主线仍以 Android / Flutter 为主。

常见场景 ​

下面不要只看业务名词，而要先判断：这个场景到底要求的是“最近进入先退出”“先到先处理”，还是“谁更重要谁先处理”。

1. 页面返回与路由恢复（栈） ​

  • 为什么是栈：页面返回遵循 LIFO，最后进入的页面最先退出。
  • Android：订单页 → 支付页 → 支付结果页，返回时通常是结果页先出，再回支付页。
  • Flutter：同样是 Navigator.push / pop，但若使用声明式 Router，还要考虑“URL 状态恢复”和“重建栈”的额外逻辑。
  • 工程判断：只要你要表达“最近进入的页面先退出”，就是栈；如果是底部 Tab 并列切换，就不是。

2. 主线程消息排队与异步任务回传（队列） ​

对应 Lab：queue-strategy-compare · QueueStrategyCompare.java

  • 为什么是队列：生产者不断投递消息，消费者按顺序串行处理。
  • 子线程做网络/解码，主线程串行回传 UI 更新，本质是“生产者把消息丢进主线程队列”。
  • 若消息带延迟、超时、重试窗口，就不只是 FIFO，还会引入“按时间排序”的约束。

3. Top-K、排行榜与定时任务（堆 / 优先队列） ​

java
public List<Integer> findTopK(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    return new ArrayList<>(minHeap);
}
  • 为什么是堆 / 优先队列：你关心的不是“谁先进入”，而是“当前最小 / 最大 / 最先到期的是谁”。
  • 可能执行顺序
    1. 先让前 k 个元素入堆。
    2. 之后每来一个新元素，只和堆顶比较。
    3. 如果新元素更大，淘汰堆顶，把它放进去。
  • 可能输出
    text
    堆中最终保留最大的 K 个元素（顺序未必有序）
  • 预期现象
    • 时间复杂度从“全排序 O(N log N)”降到 O(N log K)。
    • k 远小于 N 时收益极大。
  • 观察重点
    • 如果业务最后还要有序展示，堆只是中间结构，最终还要再排序一次。

4. BLE / 网络串行操作队列（队列） ​

在 BLE、上传下载、支付状态轮询里，经常要“同一时刻只允许一个请求在途”。这时你要的不是栈，也不是优先队列，而是严格串行 FIFO 队列：

  • BLE GATT 读写必须上一条回调完成后再发下一条。
  • 上传 SDK 为避免并发踩状态，也常维护任务队列。
  • 如果某些任务允许插队（比如取消、超时回收），才考虑额外叠加优先级。

常见误配、事故后果与排障 ​

1. 误配：把 Stack 当默认栈实现继续使用 ​

  • 原因：历史资料沿用 java.util.Stack。
  • 后果：继承自 Vector，自带过时同步语义；单线程下有额外锁成本，API 也不够现代。
  • 修法：默认换 ArrayDeque；只有跨线程共享时再显式考虑并发容器或外部同步。

2. 误配：用普通队列处理“应该按优先级执行”的任务 ​

  • 原因：只想到了“任务都要排队”，没识别“紧急任务需要插队”。
  • 后果：超时回收、保活任务、重试退避任务被普通任务淹没，造成延迟或错误重试。
  • 修法：明确业务约束是 FIFO 还是 priority；若要“先到期先执行”，直接建优先队列或延迟队列。

3. 误配：把 PriorityQueue 当成“随时可有序遍历”的排序容器 ​

  • 原因：看到堆顶最小，就误以为内部遍历已全局有序。
  • 后果：日志、UI、导出结果顺序混乱，排障时误以为算法错了。
  • 修法：PriorityQueue 只保证 peek/poll 顺序，不保证迭代顺序；需要有序结果时，复制后排序或连续 poll()。

4. 事故：递归过深导致栈溢出 ​

  • 原因：把树遍历、DFS、页面回调链写成无保护递归。
  • 后果：StackOverflowError、主线程崩溃，Flutter/Android 都可能中招。
  • 排障与修法：看崩溃栈是否出现大量重复方法帧；必要时改显式栈迭代写法，或增加收口条件。

与相近概念对比 ​

概念真正语义常见误解
栈最近进入先出来任何“有顺序”的集合都叫栈
队列先进入先处理只要叫 Queue 就一定纯 FIFO
优先队列按比较器选下一个元素内部遍历天然全局有序
堆一种实现优先队列的结构堆 = 内存堆 / GC heap
调用栈函数嵌套的运行时栈帧与页面返回栈完全同一概念

对应实验 ​

Lab说明源码
queue-strategy-compare对比 FIFO 队列、优先队列、延迟任务调度行为QueueStrategyCompare.java

复习检查题 ​

  1. 为什么 Android 的 MessageQueue 不能简单等同于“先进先出队列”？

    答：因为它除了串行消费这一层像普通队列，还会根据 when / postDelayed 选择“最先到期”的消息；一旦引入延迟消息或同步屏障，调度行为就不再是单纯 FIFO。

  2. 为什么 Java / Kotlin 里更推荐 ArrayDeque 而不是 Stack 做本地栈？

    答：Stack 继承自历史包袱很重的 Vector，方法带同步开销；ArrayDeque 基于循环数组，头尾操作同样是 O(1)，但对象更轻、性能更稳，适合绝大多数单线程栈/队列场景。

  3. 为什么求“最大的 K 个元素”通常使用容量为 K 的小顶堆？

    答：因为堆顶始终保存当前 K 个候选里最小的那个，新元素只需与堆顶比较，必要时替换即可，把复杂度从全排序的 O(N log N) 压到 O(N log K)。

  4. PriorityQueue 为什么不能拿来直接当“有序列表”遍历展示？

    答：因为它只维护父子优先级关系，保证 peek/poll 正确，不保证内部数组或迭代顺序全局有序；需要展示有序结果时还得再排序或连续 poll()。

  5. Android / Flutter 路由里的“返回上一页”为什么更接近栈而不是队列？

    答：因为页面退出顺序遵循“最后进入的页面先离开”，这正是 LIFO；如果是队列，最早进入的首页会先被弹出，显然不符合返回导航逻辑。

速记 ​

  • 栈：解决“最近进入先回退”，典型是路由返回、撤销、递归调用。
  • 队列：解决“先到先处理”，典型是主线程串行消息、任务排队。
  • 堆：解决“谁更重要谁先处理”，典型是定时器、Top-K、优先任务。
  • MessageQueue 心智：名字像 Queue，调度像“时间优先队列 + 串行消费器”。
  • 工程口令：回退用栈、排队用队列、选最值/最近到期用堆。

站点构建时间：2026/08/24 23:45:00

Copyright © 2026-present Engineering Review Lab. All Rights Reserved. (CC BY-NC-SA 4.0)

站点构建时间：2026/8/24 23:43:17

Copyright © 2026-present Engineering Review Lab. All Rights Reserved. (CC BY-NC-SA 4.0)