2. 导航栈数据结构选型：数组、链表、双向链表、栈操作时间复杂度对比
导航栈的底层数据结构直接影响 push、pop、peek 的性能以及内存布局。在选择时，需要权衡增删改查的时间复杂度、缓存局部性、内存碎片和实现复杂度。本章对比数组、链表、双向链表三种主流方案，给出选型依据。
2.1 数组（Array）
动态数组（如 Java 的 ArrayList、C++ 的 std::vector）是导航栈最简单的实现方式。栈顶指针指向数组末尾，push 在尾部追加元素，pop 移除尾部元素。
- push：均摊 O(1)（需扩容时 O(n)）
- pop：O(1)（直接移动游标）
- peek：O(1)（读取栈顶下标元素）
- 内存局部性：优秀（连续内存，CPU 缓存友好）
- 缺点：动态扩容可能触发全量拷贝，频繁 push/pop 导致内存碎片
适用于对栈大小可预估、操作频率高且对缓存性能敏感的场景。
2.2 单向链表（Singly Linked List）
每个节点储存数据和指向下一个节点的指针。栈顶为链表头，push 在头部插入新节点，pop 移除头节点。
- push：O(1)（只修改头指针）
- pop：O(1)（释放头节点并更新头指针）
- peek：O(1)（读取头节点数据）
- 内存局部性：差（节点分散，每次访问可能多次缓存缺失）
- 优点：无需预分配空间，每次
push只动态分配一个节点
单向链表
pop 时需要手动管理内存释放（非 GC 语言），且无法从尾部快速移除。如果导航栈需要支持“回退到上 N 层”，单向链表遍历较慢。2.3 双向链表（Doubly Linked List）
每个节点增加指向 prev 的指针。栈顶既可以做在头部，也可以做在尾部；典型实现使用头节点作为栈顶。
- push：O(1)（头插或尾插）
- pop：O(1)（移除头节点或尾节点）
- peek：O(1)
- 内存开销：每个节点额外储存一个指针（8 字节，64 位平台）
- 优势：支持从任意方向遍历，适合嵌套栈或“栈快照”恢复
2.4 时间复杂度对比
| 操作 | 数组（动态） | 单向链表 | 双向链表 |
|---|---|---|---|
| push | O(1)* | O(1) | O(1) |
| pop | O(1) | O(1) | O(1) |
| peek | O(1) | O(1) | O(1) |
| 空间开销/节点 | 0 额外指针 | 1 指针 | 2 指针 |
| 扩容/碎片 | 可能 O(n) 拷贝 | 无 | 无 |
| 缓存友好性 | 高 | 低 | 低 |
* 均摊 O(1)，最坏 O(n) 发生在数组扩容时。
2.5 选型决策流程
2.6 实践建议
- 中小规模页面栈（小于 50 层）：优先使用动态数组，简单且缓存友好。预留容量如
new ArrayList<>(64)避免频繁扩容。 - 长时间运行、页面栈深度不可控：使用单向链表或双向链表，避免大数组拷贝。
- 需要“回退”或“快照”功能：双向链表可快速获取上一个页面（栈下方）的引用，数组则需要额外索引维护。
- 跨平台框架（如 Flutter）：通常内置
List作为栈，但应关注其insert/removeAt性能，避免在非尾部操作。
在导航栈的
push/pop 实现中，尽量保证 peek 操作也是 O(1)。如果选择链表，务必缓存 head 指针，不要遍历查找栈顶。