《Hello 算法》栈与队列章节小结精讲：LIFO/FIFO 两种实现方式对比，与浏览器回退、撤销/重做等 Q&A 的源码级解析

导读

本文以《Hello 算法》中文与俄语版仓库中 栈与队列章节小结（同源内容见 docs/chapter_stack_and_queue/summary.md）为骨架，系统梳理"后入先出（LIFO）的栈、先入先出（FIFO）的队列、以及双向操作的双向队列"三者的本质差异、两种典型实现（数组/链表）在时间与空间上的取舍，并结合仓库中 C 语言实现逐行印证复杂度结论。文末对"浏览器前进/后退是否用双向链表""出栈后是否必须释放内存""双向队列的用途""undo/redo 双栈原理"四个高频疑问给出严谨解答。读完本文，你将能在工程选型时准确回答"栈、队列、双向队列各自适合什么场景、数组版与链表版各有什么代价"，也能动手对照 C 源码复现全部结论。

章节小结的定位：一页浓缩三类线性容器

在《Hello 算法》中，栈、队列、双向队列 三章分别讲解了三种"操作受限的线性表"，而各语言版本目录下的 summary.md 则是章节收尾的知识压缩包，通常由两部分构成：

1. 重点回顾：用 5 条结论概括三章最核心的知识点与对比口径；
2. Q & A：回答 4 个初学阶段最容易混淆或延伸的问题。

与中文版完全同源的 俄语版小结 位于俄语翻译仓库，其结构（Резюме / Основные выводы / Q & A）与正文一致，说明这套"重点回顾 + 问答"的收尾结构是随文档体系被完整翻译同步维护的，可作为阅读任一章后的标准复盘清单。

重点回顾逐条拆解：规则、实现方式与效率取舍

小结的 5 条结论实际上建立了三条主线：存取规则、实现方式、效率对比口径。

栈：后入先出，数组与链表两种实现

栈是遵循后入先出（Last-In-First-Out, LIFO）原则的数据结构，可通过数组或链表实现。

栈只允许在一端（栈顶）进行插入与删除，push（入栈）与 pop（出栈）均作用于栈顶。仓库的 C 实现可以清晰地佐证这一约束：

• 数组版 array_stack.c：push 在 data[size] 处写入并将 size 加一，pop 只把 size 减一即完成逻辑删除，栈顶即 data[size - 1]；
• 链表版 linkedlist_stack.c：结构体只保留一个 top 指针（把头节点当作栈顶），push 新建节点并让新节点的 next 指向旧栈顶（node->next = s->top），随后更新 s->top = node。

两份代码的其余操作（peek、isEmpty、size）也都只围绕这一个端点展开，体现了"受限线性表"的含义——栈的语义不要求你访问中间元素。

时间效率：数组版"平均快、单次可能劣化"，链表版"稳定但慢一点"

时间效率方面，栈的数组实现平均效率较高，但在扩容过程中单次入栈的时间复杂度可能劣化至 $O(n)$；链表的实现效率表现更稳定。

这条结论适用于使用动态数组的语言实现（如 Java 的 ArrayDeque、C++ 的 vector 扩容逻辑）。原因链条是：

1. 数组版 push/pop 只做常数次赋值与指针/下标移动，且元素在连续内存中，缓存局部性好，因此平均耗时低；
2. 但当数组容量不足触发扩容时，需要把旧数组的全部元素拷贝进更大的新数组，这一次操作的代价为 $O(n)$，即单次操作的时延尖峰；
3. 链表版每次 push 都需 malloc 一个新节点（见 linkedlist_stack.c），单次操作本身是 $O(1)$，不依赖栈的规模，因此波动更小、表现更稳定。

从源码结构看，仓库为了教学演示刻意规避了扩容劣化： array_stack.c 以 #define MAX_SIZE 5000 预分配了超大数组，并注释"初始化一个大容量，避免扩容"，push 在满时直接打印"栈已满"后返回。这与 Java/Python 语言章节中讲解的动态扩容 O(n) 属于"教学固定容量版 vs 工程动态数组版"两种形态，前者便于演示 LIFO 逻辑，后者才需要承担扩容成本——阅读时注意区分。

空间效率：数组版可能浪费空间，链表节点则更"胖"

空间效率方面，数组版实现可能造成一定空间浪费；但链表节点所占内存比数组元素更大。

• 数组版：元素挨个存放、几乎没有冗余（若预分配大于实际使用量则会有少量空闲区，array_stack.c 中 MAX_SIZE 与 size 之差即是这部分浪费）；
• 链表版：每个节点除了 val，还要额外保存指针域。如 linkedlist_stack.c 中每个 ListNode 含数据域加 next 指针，若存 int，指针开销往往比数据本身还大；若考虑 malloc 分配的元数据与内存对齐，实际开销更高。

因此"链表省空间"是常见误区：链表确实避免了数组整体扩容的拷贝，但每个元素都背负额外的指针开销，二者在空间上的取舍要结合元素大小与容量利用率具体衡量。

队列与双向队列：同样结论，更高自由度

队列遵循先入先出（First-In-First-Out, FIFO），同样可用数组或链表实现，时间与空间效率的对比结论与栈相似。 双向队列是自由度更高的队列，允许在两端进行添加和删除。

队列的 FIFO 规则要求"队尾入、队首出"。其两种实现与栈形成对照，仓库 C 源码给出了富有教学价值的细节：

• 数组版队列的关键不是扩容，而是"环形"。若朴素地在数组上做队首出队并整体搬移，每次出队都会退化为 $O(n)$。因此 array_queue.c 用 front 指针加元素个数 queSize 描述队列，并用取余运算让队尾指针绕回头部：int rear = (front + queSize) % queCapacity，出队时 front = (front + 1) % queCapacity。这就是"环形数组"消除搬移开销的关键——空间上会留出一个用于区分"满/空"的空位，正是小结所说"数组实现可能造成一定空间浪费"在队列上的具体表现。
• 链表版队列需要双端指针。与栈只用一个 top 不同，linkedlist_queue.c 的结构体同时保存 front 与 rear：入队在 rear 之后挂新节点，出队从 front 摘除，两端的 malloc/free 都是常数时间，故性能稳定但节点含额外指针。

双向队列（deque） 则把上述约束进一步放开：两端都可 push/pop。其"环形数组"实现需要在两个方向处理索引回绕，array_deque.c 中专门抽出的 dequeIndex 函数用 (i + capacity) % capacity 统一处理"队首向左越界回尾"与"队尾向右越界回头"；链表版 linkedlist_deque.c 则必须使用双向链表节点（同时带 prev 与 next），否则无法在 $O(1)$ 内从尾部摘除节点。

下表是三类容器与两种实现方式的完整对比口径（对应小结第 1、4、5 条）：

容器	存取规则	数组实现特点	链表实现特点
栈	LIFO，单端进出	平均快、缓存友好；动态扩容时单次 push 到 $O(n)$	每次 push 需建节点，性能稳定；节点带指针开销
队列	FIFO，队尾入队首出	需用环形数组消除出队搬移；留空位致少量空间浪费	需 front/rear 双指针，端到端均 $O(1)$
双向队列	两端进出	双向取余回绕，逻辑稍复杂	需双向链表（带 prev/next）才能两端快速摘除

Q & A 精讲：四个高频疑问的严谨答案

小结的问答部分直击初学者的认知盲区，以下结合正文章节与源码逐一展开。

Q1：浏览器的前进/后退是用双向链表实现的吗？

答案是否定的——其核心本质是"栈"，而不是双向链表。

回顾小结给出的逻辑：用户访问新页面时，当前页面会被压入栈顶；点击"后退"时，把栈顶页面弹出，回到上一页。这一系列"后进先出"的访问历史，与 stack.md 正文 的应用列举完全吻合："每当我们打开新的网页，浏览器就会对上一个网页执行入栈……后退操作实际上是在执行出栈。"

那"前进"怎么实现？小结指出："如果要同时支持后退和前进，则需要两个栈来配合实现"——这与下面 Q4 的 undo/redo 双栈模型是同构的。至于双向链表/双向队列的作用，deque.md 给出了一个经典场景：许多软件限制撤销步数（如仅保留 50 步），当历史记录超限时需要在栈底（即队首）删除最旧的记录，而普通栈无法做到这一点，此时才需要借助双向队列在两端操作的能力。可见双向队列解决的是"栈 + 容量淘汰"的组合需求，而不是前进/后退本身。

Q2：出栈之后，需要手动释放被弹出节点的内存吗？

小结给出了分语言、分场景的判断框架：

• 场景一：弹出的节点后续仍会用到——不释放内存（如 undo/redo 中从撤销栈弹到重做栈，节点在 A、B 两栈间转移，始终被持有）；
• 场景二：弹出的节点不再需要：
  • 在 Java、Python、Go 等具备自动垃圾回收（GC）机制的语言中，节点不再被任何栈引用后由 GC 自动回收，无需也无法手动释放；
  • 在 C、C++ 这类手动管理内存的语言中，必须在逻辑删除的同时 free 弹出的节点，否则会产生内存泄漏。

这一点在仓库 C 源码中体现得淋漓尽致：链表栈 linkedlist_stack.c 的 pop 先取 val，再 free(tmp) 释放被弹出的节点；链表队列 linkedlist_queue.c 的 pop 同样在摘下队首后 free(tmp)；析构函数 delLinkedListQueue 会沿链表逐个释放所有剩余节点。反观数组实现则完全不同：数组栈的 pop 仅执行 stack->size--（array_stack.c），元素仍停留在原槽位，只是被"逻辑废弃"，将来会被后续 push 覆盖，因此不存在逐节点释放的问题——这也是"数组实现是否需要释放内存"与"链表实现"答案不同的根源。

Q3：双向队列像是两个栈拼在一起，它到底有什么用？

小结的回答切中本质：双向队列表现的正是"栈 + 队列"的合并逻辑，因此它既能覆盖栈、队列各自的所有应用场景，又因为能在两端操作而更加灵活。

为什么说"像两个栈拼接"？从接口看，若只使用它的首端进出，它就是栈；若只使用"首进尾出"，它就是队列；若首尾同时可进出，则栈与队列的能力被合而为一。仓库 C 源码正好提供了这种"组合"的直接证据：

• array_deque.c 同时实现了 pushFirst/pushLast、popFirst/popLast、peekFirst/peekLast 六个方法，而普通队列只有 push/pop/peek 三个；
• linkedlist_deque.c 的内部 push(deque, num, isFront) 与 pop(deque, isFront) 用一个布尔参数区分首尾，从接口设计上即可看出它是"栈能力 + 队列能力"的参数化组合。

最贴切的实战例子即 Q1 中提到的受限撤销：正常情况下 undo 用栈实现（后入先出），但加上"最多保留 50 步、超限删栈底"的约束后，栈无能为力，而双向队列既能以栈的方式从一端压入/弹出，又能从另一端删除最旧记录，恰好两全其美。注意这里的核心逻辑仍是栈的 LIFO，deque 只是提供了更灵活的两端操作手段——这正是小结想强调的分寸。

Q4：撤销（undo）与重做（redo）具体是怎么实现的？

小结给出了标准的双栈模型，设栈 A 存撤销历史、栈 B 存被撤销的动作：

1. 用户每执行一个新操作，将其 push 进栈 A，同时清空栈 B（因为产生了新分支，此前的重做记录全部作废）；
2. 用户执行"撤销"时，从栈 A 顶部 pop 出最近的操作，将其 push 进栈 B，同时执行该操作的逆动作回滚状态；
3. 用户执行"重做"时，从栈 B 顶部 pop 出最近被撤销的操作，push 回栈 A，并重新执行它以恢复状态。

这套模型与前文两处内容互相印证：其一，stack.md 明确指出撤销/反撤销是栈的典型应用之一，且"如果同时支持后退和前进，需要两个栈配合"，与浏览器前进/后退（Q1）是同一架构在不同产品形态下的复现；其二，deque.md 补充了工程化约束——当软件限制撤销步数（如 50 步）时，栈 A 容量超限需从栈底淘汰最旧动作，这一步就要借助双向队列的能力完成。三个疑问在双栈模型上闭环，读者可以把 A/B 两个栈理解成一组"时间线"：A 指向过去，B 指向未来，任何新动作都会抹掉未来。

从小结到实战：如何系统复习并动手验证

小结是章节知识的"验收清单"，建议按以下闭环使用：

1. 规则层：能不看资料复述——栈 LIFO、队列 FIFO、deque 两端皆可，并各举一个现实场景（浏览器历史、打印任务队列 queue.md 中"先来后到"的排队、软件撤销）；
2. 实现层：对照 C 源码逐行比较——array_stack.c 与 linkedlist_stack.c 看栈的单端约束、array_queue.c 看环形数组回绕、linkedlist_deque.c 看双向链表为何是 deque 的链表版前提；
3. 复杂度层：用"平均 vs 单次、时间 vs 空间"四个象限做口头小结，即本文上表中的对比结论；
4. 问答层：把四个 Q&A 当作面试自测题，尤其要能说清"撤销为什么用两个栈""为什么双向队列能删除栈底"。

上述 C 实现均随仓库 CMake 工程编译运行（如 codes/c/chapter_stack_and_queue/CMakeLists.txt），Java、Python、Go、Rust 等语言在 codes 下有同构实现，可任选一门语言运行 Driver Code 观察输出，以最直观的方式验证栈顶/队首指针的移动规律。若希望进一步巩固，可继续阅读章节对应的习题页，将小结结论转化为亲手推导的能力。