Hello 算法：栈、队列与双向队列章节小结精读——核心结论回顾与撤销/重做等四类高频工程问答

本篇以《Hello 算法》栈与队列章节小结（中文版见 docs/chapter_stack_and_queue/summary.md）为骨架：先系统回顾栈、队列、双向队列三大结构的定义，以及数组与链表两种底层实现在时间/空间效率上的关键权衡；再结合仓库源码，逐条深挖"浏览器前进后退""出栈后是否释放内存""双向队列像两个栈拼接的用途""撤销与重做如何实现"四类高频问答。读完你将能把抽象结论落到仓库中可运行、可对照验证的代码层面。

一、知识点回顾：三种结构与两种底层实现

1.1 栈（Stack）：遵循后进先出（LIFO）

栈是一种遵循 后进先出（Last-In, First-Out） 原则的数据结构，只允许在同一端（栈顶）进行入栈（push）与出栈（pop）。它既可以用 数组 实现，也可以用 链表 实现，两种方式在仓库 codes 目录下均有完整、可运行的示例。

以 Python 为例，数组实现位于 array_stack.py：元素通过 append 追加到列表尾部、通过 pop 从尾部取出，天然符合"只操作栈顶"的语义；链表实现位于 linkedlist_stack.py：push 时新建节点插入链表头部，peek/pop 直接操作头节点，从而让头节点恒为栈顶：

# 摘自 codes/python/chapter_stack_and_queue/linkedlist_stack.py
def push(self, val: int):
    """入栈：将新节点插入链表头部（栈顶）"""
    node = ListNode(val)
    node.next = self._peek
    self._peek = node
    self._size += 1

def pop(self) -> int:
    """出栈：返回并摘除栈顶节点"""
    num = self.peek()
    self._peek = self._peek.next
    self._size -= 1
    return num

1.2 队列（Queue）：遵循先进先出（FIFO）

队列遵循 先进先出（First-In, First-Out） 原则：数据从队尾入队、从队首出队，同样可用数组或链表实现。小结特别强调：在时间效率、空间效率的对比上，队列的结论与栈高度相似。

仓库对应示例包括 array_queue.py（数组实现）与 linkedlist_queue.py（链表实现）。需要留意的是内置版 queue.py 中的语言约定：本书在 Python 中一般把 collections.deque 当作队列使用（append 入队、popleft 出队），而不是 queue.Queue()——后者虽更"纯正"，但主要用于线程安全的队列场景，在算法演示中并不好用，这一取舍在源码注释里有明确说明：

# 摘自 codes/python/chapter_stack_and_queue/queue.py
from collections import deque

que: deque[int] = deque()
que.append(1)          # 元素入队（队尾）
front: int = que[0]    # 访问队首元素
pop: int = que.popleft()   # 元素出队（队首）

1.3 双向队列（Deque）：两端都可操作的高自由度队列

双向队列 是"一种具有更高自由度的队列，它允许在两端进行元素的添加和删除"，因此灵活性超越普通队列。仓库内置版示例见 deque.py，手写的数组/链表实现分别见 array_deque.py 与 linkedlist_deque.py：

# 摘自 codes/python/chapter_stack_and_queue/deque.py
deq: deque[int] = deque()
deq.append(2)            # 添加至队尾
deq.appendleft(3)        # 添加至队首
front: int = deq[0]      # 队首元素
rear: int = deq[-1]      # 队尾元素
pop_front: int = deq.popleft()  # 队首元素出队
pop_rear: int = deq.pop()       # 队尾元素出队

三大结构的完整专题讲解可继续阅读 stack.md、queue.md、deque.md 三个章节文档。

二、核心结论剖析：数组与链表实现的效率权衡

小结提炼了两条贯穿全章的效率结论，下面结合源码展开。

2.1 时间效率：数组"平均更优、扩容有抖动"，链表"更稳定"

小结原文结论：栈的数组实现具有较高的平均效率，但在扩容过程中，单次入栈操作的时间复杂度会劣化至 $O(n)$；相比之下，栈的链表实现具有更稳定的效率表现。

展开来说：基于数组的栈只要容量充足，push 只需在尾部追加、pop 只需移动"大小"标记，均为 $O(1)$，且连续内存对 CPU 缓存友好，因此平均效率高。但当元素数量逼近容量上限时，底层必须扩容：申请更大内存并把旧元素整体搬迁，导致这一次 push 退化到 $O(n)$（从均摊角度看仍为 $O(1)$，但单次响应存在抖动）。

这一点在 C 语言实现中体现得最直观。数组版 array_stack.c 的构造函数一次性预分配 MAX_SIZE = 5000 并注释"初始化一个大容量，避免扩容"，此后 push 只需一次赋值加自增：

// 摘自 codes/c/chapter_stack_and_queue/array_stack.c
#define MAX_SIZE 5000

void push(ArrayStack *stack, int num) {
    if (stack->size == MAX_SIZE) {   // 容量已满则拒绝（示例未做自动扩容）
        printf("栈已满\n");
        return;
    }
    stack->data[stack->size] = num;
    stack->size++;
}

链表版 linkedlist_stack.c 则相反：每次 push 都要 malloc 一个节点并改写指针，单次代价恒定、不随规模变化，因此性能表现更稳定、无扩容抖动。两种实现正是"平均高效但有偶发尖峰"与"恒定平稳"的直观对照。

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

小结原文结论：栈的数组实现可能导致一定程度的空间浪费；但链表节点所占用的内存空间比数组元素更大。

• 数组实现可能浪费空间：为减少扩容频率，数组往往预留超出实际元素数量的容量（如 C 示例一次性分配 5000 个 int），扩容后旧容量也不会立刻收缩。观察 array_stack.c 的 pop 可以发现，它只把 size 减一，被弹出元素所在的槽位仍然占着底层缓冲，这正是"空间浪费"的代码级体现：

// 摘自 codes/c/chapter_stack_and_queue/array_stack.c
int pop(ArrayStack *stack) {
    int val = peek(stack);
    stack->size--;   // 仅缩小逻辑大小，底层缓冲槽位仍被占用
    return val;
}

• 链表节点占用更多内存：每个链表节点除数据外还需存储指向下一节点的指针（next）及节点自身的分配元数据，单位元素的内存开销高于数组元素。

因此"谁更省空间"取决于使用模式：元素规模波动小、可预估上限时数组更省；元素频繁增减、规模难预估时，链表按需分配反而更贴合实际占用。

三、Q & A 精讲：四类高频工程问题

3.1 浏览器前进/后退是"双向链表"实现的吗？

不是。浏览器的前进后退本质上是"栈"的体现。

用户访问新页面时，该页面被"压入"栈顶；点击"后退"时，当前页面从栈顶"弹出"，浏览器回到其下方的页面。这与栈的 LIFO 语义完全一致：你只能回到"最近访问过"的那一页，而不能随意跳到中间的任意页面（若要任意跳转，才需要链表式的历史列表）。

小结同时指出：使用双向队列可以方便地实现一些额外操作（如两端式的辅助处理），这一点在"双向队列"章节 deque.md 中有提及。核心结论不变：主流程走栈，双向队列仅承担锦上添花的辅助扩展。

3.2 出栈之后，是否需要手动释放被弹出节点的内存？

取决于后续是否还需要该节点，以及语言的内存管理机制。

• 若弹出节点后续仍会被使用（如转交给另一个结构持有），则不能释放，否则产生悬空引用；
• 若确认不再使用：Java、Python 等具备自动垃圾回收机制的语言无需手动释放；而在 C 与 C++ 中必须手动释放，否则造成内存泄漏。

仓库的 C 链表栈 linkedlist_stack.c 给出了教科书式示范：pop 摘除栈顶节点后立刻 free(tmp)，析构函数 delLinkedListStack 再遍历释放全部剩余节点：

// 摘自 codes/c/chapter_stack_and_queue/linkedlist_stack.c
int pop(LinkedListStack *s) {
    int val = peek(s);
    ListNode *tmp = s->top;
    s->top = s->top->next;
    free(tmp);      // 手动释放被弹出节点的内存
    s->size--;
    return val;
}

对比 Python 版 linkedlist_stack.py：pop 只做指针前移并返回数值，完全不需要 free 类操作，内存回收交给解释器自动完成。两个文件恰好是"手动释放"与"自动回收"两大语言阵营的镜像对照，值得并排阅读。

3.3 双向队列像是两个栈拼在了一起，用途是什么？

确实可以这样理解，而这正是它的设计价值所在。

双向队列"像是栈和队列的组合，或两个栈拼在了一起"，同时表现出栈与队列的逻辑：既能在单端严格按 LIFO 存取（对应栈），也能两端对称地"首进首出"（对应队列），还支持"一端进、另一端出"的中间形态。因此：

• 它可以实现栈与队列的全部应用场景；
• 它提供更高的自由度与灵活性，如 deque.py 所示，队首、队尾都能通过对称的 append/appendleft/pop/popleft 完成增删。

适用边界同样清晰：若业务只要求严格的单端进出，直接用栈或队列更合适——语义清晰、不易误用；只有当两端增删频繁出现时，双向队列的灵活性才真正发挥价值。

3.4 撤销（undo）与反撤销（redo）具体如何实现？

核心方案：使用两个栈——栈 A 负责撤销历史，栈 B 负责重做历史。

完整算法如下（原文档步骤逐条继承）：

1. 每当用户执行一个新操作：把该操作压入栈 A，并清空栈 B——新操作产生新分支，旧的"可重做"记录全部失效；
2. 当用户执行"撤销"时：从栈 A 弹出最近的操作并执行其逆操作，再把它压入栈 B 暂存；
3. 当用户执行"反撤销"（redo）时：从栈 B 弹出最近被撤销的操作并重新执行，再压回栈 A。

用伪代码概括即为：

执行新操作(op):
    A.push(op)
    B.clear()            # 清空重做栈，开启新分支

undo():
    if A 非空:
        op = A.pop()
        执行 op 的逆操作
        B.push(op)       # 登记到重做栈

redo():
    if B 非空:
        op = B.pop()
        重新执行 op
        A.push(op)       # 回到撤销栈，可再次撤销

该模型成立的关键在于两个栈方向相反、互相镜像：A 的栈顶永远是最新可撤销操作，B 的栈顶永远是最新可重做操作。撤销/反撤销只是把栈顶元素在两栈间"倒来倒去"，配合第 1 步的"清空 B"，即可正确处理"撤销之后又执行新操作"的分支场景——这正是浏览器、文档编辑器、IDE 中撤销/重做功能的通用实现骨架。

四、延伸阅读：把结论落到可运行代码

若要亲手验证上述全部结论，可在仓库根目录直接运行各语言的驱动示例（Driver Code），以 Python 为例：

python3 codes/python/chapter_stack_and_queue/linkedlist_stack.py
python3 codes/python/chapter_stack_and_queue/array_stack.py
python3 codes/python/chapter_stack_and_queue/queue.py
python3 codes/python/chapter_stack_and_queue/deque.py

更深入的对照阅读材料：

• 章节正文：stack.md、queue.md、deque.md、index.md
• 章节练习：exercises.md
• 中文对照小结：docs/chapter_stack_and_queue/summary.md
• Python 全套实现：codes/python/chapter_stack_and_queue/
• C 全套实现：codes/c/chapter_stack_and_queue/（数组/链表双版本完整展示了"预分配避免扩容"与"出栈即 free"两种内存策略）
• C++/Java 实现：codes/cpp/chapter_stack_and_queue/、codes/java/chapter_stack_and_queue/

除上述语言外，仓库还在 C#、Go、JavaScript、TypeScript、Dart、Kotlin、Swift、Rust、Ruby 等语言的 codes 目录中提供同名章节实现，可横向对比不同语言在"扩容策略"与"内存回收"上的差异——这正是把小结中时间/空间效率结论内化为工程直觉的最佳实践入口。