Hello 算法：栈与队列全解析——从 LIFO/FIFO 原理到数组、链表、双向队列实现选型

本篇技术文章基于《Hello 算法》的栈与队列章节小结（docs/chapter_stack_and_queue/summary.md）展开，系统梳理栈、队列、双向队列的核心结论与效率权衡，并结合开源仓库中多语言实现（以 Python 为例）逐一印证其底层原理。读完后，你将能够准确说出栈与队列的时间/空间复杂度差异、掌握环形数组与双向链表两种实现模式，并学会用"双栈"这一经典技巧实现撤销/反撤销等实际功能。

一、章节要点回顾：栈、队列与双向队列的核心结论

summary.md 以"重点回顾"形式给出了本章的五条核心结论，这也是理解整个栈与队列知识体系的骨架：

1. 栈（Stack）：遵循**先入后出（LIFO, Last-In First-Out）**原则的数据结构，可通过数组或链表实现；
2. 栈的效率对比：
   • 时间效率——数组实现平均效率较高，但扩容时单次入栈的时间复杂度会劣化至 $O(n)$；链表实现的效率表现更稳定；
   • 空间效率——数组实现可能导致一定的空间浪费（预留了未使用的容量），但链表节点占用的内存比数组元素更大（每个节点需额外存储指针引用）；
3. 队列（Queue）：遵循**先入先出（FIFO, First-In First-Out）**原则，同样支持数组与链表两种实现，其时间与空间效率的对比结论与栈相似；
4. 双向队列（Deque）：自由度更高的队列，允许在两端进行元素的添加和删除操作。

本章代码集中在 codes/python/chapter_stack_and_queue/ 目录下，包含 array_stack.py、linkedlist_stack.py、array_queue.py、linkedlist_queue.py、array_deque.py、linkedlist_deque.py 以及三个直接演示语言标准库用法的 stack.py、queue.py、deque.py，并支持 Python、Java、C++、C、C#、JavaScript、Go、Swift、Rust、Ruby、Kotlin、TypeScript、Dart 等十余种语言版本。

二、栈的实现印证：数组版与链表版的效率差异从何而来

2.1 基于数组的栈：平均高效，扩容劣化

在 codes/python/chapter_stack_and_queue/array_stack.py 中，ArrayStack 直接用 list 作为底层容器：

class ArrayStack:
    """基于数组实现的栈"""

    def __init__(self):
        self._stack: list[int] = []

    def push(self, item: int):
        """入栈"""
        self._stack.append(item)

    def pop(self) -> int:
        """出栈"""
        if self.is_empty():
            raise IndexError("栈为空")
        return self._stack.pop()

    def peek(self) -> int:
        """访问栈顶元素"""
        if self.is_empty():
            raise IndexError("栈为空")
        return self._stack[-1]

从源码结构看，push/pop/peek 都是直接对列表尾部的常数时间操作，栈顶即列表末尾（self._stack[-1]），这与"栈顶在数组尾部"的设计一致：元素总是追加/移除在同一端，因此不需要搬移任何元素。summary.md 中提到的 $O(n)$ 劣化来自底层动态数组扩容：当 list 增长触发容量翻倍时，需要整块复制所有元素，单次 append 的摊还复杂度仍为 $O(1)$，但某一次调用确实是 $O(n)$。

2.2 基于链表的栈：效率稳定，节点开销更大

在 codes/python/chapter_stack_and_queue/linkedlist_stack.py 中，LinkedListStack 将头节点当作栈顶（self._peek 指向最近入栈的节点）：

class LinkedListStack:
    """基于链表实现的栈"""

    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

入栈与出栈都只操作头节点，恒为 $O(1)$，不存在扩容问题——这正是"链表实现具有更为稳定的效率表现"的来源。代价则是 summary.md 所指出的空间问题：每个 ListNode 除 val 外还要存储一个 next 指针，节点内存占用高于定长数组元素，且链表节点分散分配在堆上，缓存局部性也不如连续数组。

三、队列的实现印证：环形数组与链表双端指针

3.1 环形数组队列：取余操作让数组"首尾相连"

朴素数组队列出队时需要搬移元素或维护空洞，而 codes/python/chapter_stack_and_queue/array_queue.py 采用了环形数组方案：

def push(self, num: int):
    """入队"""
    if self._size == self.capacity():
        raise IndexError("队列已满")
    # 计算队尾指针，指向队尾索引 + 1
    # 通过取余操作实现 rear 越过数组尾部后回到头部
    rear: int = (self._front + self._size) % self.capacity()
    self._nums[rear] = num
    self._size += 1

def pop(self) -> int:
    """出队"""
    num: int = self.peek()
    # 队首指针向后移动一位，若越过尾部，则返回到数组头部
    self._front = (self._front + 1) % self.capacity()
    self._size -= 1
    return num

关键点在于 % self.capacity() 这一取余操作：_front 越过数组尾部后回到头部，出队不再搬移任何元素，push 和 pop 均为 $O(1)$。与栈类似，固定容量的数组队列同样存在容量规划导致的空间浪费；若使用动态扩容，则与数组栈一样存在扩容瞬间 $O(n)$ 的代价。

3.2 链表队列：front/rear 双指针，两端各 $O(1)$

codes/python/chapter_stack_and_queue/linkedlist_queue.py 中，LinkedListQueue 同时维护头节点 self._front 与尾节点 self._rear：

def push(self, num: int):
    """入队"""
    node = ListNode(num)
    # 如果队列为空，则令头、尾节点都指向该节点
    if self._front is None:
        self._front = node
        self._rear = node
    # 如果队列不为空，则将该节点添加到尾节点后
    else:
        self._rear.next = node
        self._rear = node
    self._size += 1

入队在尾部、出队在头部，借助两个指针两端操作均为 $O(1)$；空间开销同样体现为"每个节点一个 next 指针"。这组实现恰好完整对应了 summary.md 中"队列的时间效率和空间效率对比结论与栈相似"这一论断。

四、双向队列（Deque）：把栈与队列的自由度合二为一

4.1 环形数组版 Deque

codes/python/chapter_stack_and_queue/array_deque.py 在环形数组基础上，把"只能在尾端操作"放宽为"两端皆可操作"。核心是一个统一的索引换算函数：

def index(self, i: int) -> int:
    """计算环形数组索引"""
    # 当 i 越过数组尾部后，回到头部
    # 当 i 越过数组头部后，回到尾部
    return (i + self.capacity()) % self.capacity()

队首入队时，指针先"向左"移动一位再写入，取余让 front - 1 越过数组头部后绕回尾部：

def push_first(self, num: int):
    """队首入队"""
    if self._size == self.capacity():
        print("双向队列已满")
        return
    # 队首指针向左移动一位
    self._front = self.index(self._front - 1)
    self._nums[self._front] = num
    self._size += 1

对外暴露 push_first / push_last / pop_first / pop_last / peek_first / peek_last 六种操作，全部为 $O(1)$。

4.2 双向链表版 Deque

codes/python/chapter_stack_and_queue/linkedlist_deque.py 改用带 prev 引用的双向链表节点，push 与 pop 均以 is_front 布尔参数区分操作端：

def push(self, num: int, is_front: bool):
    """入队操作"""
    node = ListNode(num)
    # 若链表为空，则令 front 和 rear 都指向 node
    if self.is_empty():
        self._front = self._rear = node
    # 队首入队操作
    elif is_front:
        self._front.prev = node
        node.next = self._front
        self._front = node  # 更新头节点
    # 队尾入队操作
    else:
        self._rear.next = node
        node.prev = self._rear
        self._rear = node  # 更新尾节点
    self._size += 1

正因为 ListNode 同时持有 next 与 prev 两个引用，任意一端的插入与删除都能 $O(1)$ 完成——这就是 summary.md 所谓"双向队列像是两个栈拼接在一起"的结构依据：它同时具备栈（两端可弹出）与队列（两端可进入）的全部逻辑，因此"可以实现栈与队列的所有应用，并且更加灵活"。

4.3 各语言中的"即取即用"版本

summary.md 强调双向队列的灵活应用，仓库中每个语言版本都配有可直接运行的演示：Python 直接使用标准库 collections.deque（见 codes/python/chapter_stack_and_queue/deque.py），其 append/appendleft/popleft/pop 正是上述两端操作的原生形态；C 语言版本可参考 codes/c/chapter_stack_and_queue/ 下的 array_deque.c、linkedlist_deque.c 等文件，其余语言目录（cpp、java、go、rust 等）中均有同名实现可对照阅读。

五、Q & A 深度解读：四个高频问题及其实现方案

本章小结的 "Q & A" 部分收录了四个读者最关心的问题，下面逐一展开并给出可对照仓库的实现方案。

5.1 浏览器的前进后退是双向链表吗？

结论：本质上是"栈"的体现。 用户访问新页面时，页面被压入栈顶；点击后退按钮时，页面从栈顶弹出。而"前进"操作以及"后退后清空前进栈"等更复杂的行为，则可以用双向队列方便地实现——这与本章 codes/python/chapter_stack_and_queue/linkedlist_deque.py 中两端可增删的结构能力完全对应。

5.2 出栈后是否需要释放内存？

分语言讨论：

• 若弹出的节点后续仍要使用，则显然不能释放；
• Java、Python 等具备**自动垃圾回收（GC）**的语言，程序员无需手动释放；
• C、C++ 中则必须手动释放，否则造成内存泄漏。从仓库代码结构看，C 版本的链表栈/队列实现（如 codes/c/chapter_stack_and_queue/ 中的 linkedlist_stack.c、linkedlist_queue.c）需要显式 free 出栈/出队节点，这也从实现层面印证了该结论。

5.3 双向队列的用途是什么？

它表现的是栈 + 队列的组合逻辑：既可以像栈一样从两端弹出（LIFO），也可以像队列一样从两端进入（FIFO），因此可以实现栈与队列的所有应用，且自由度更高。典型场景包括任务调度器、浏览器历史管理、以及需要在"撤销"与"重做"之间来回切换的场景。

5.4 撤销（undo）与反撤销（redo）如何实现？

summary.md 给出的经典方案是双栈模型：栈 A 存待撤销操作，栈 B 存可重做操作。规则如下：

1. 每当用户执行一个新操作，将其压入栈 A，并清空栈 B（因为新操作使旧的重做路径失效）；
2. 用户"撤销"时，从栈 A 弹出最近的操作并压入栈 B；
3. 用户"反撤销"时，从栈 B 弹出最近的操作并压回栈 A。

用本章代码稍加改造即可实现，例如以 ArrayStack 为底座：

from array_stack import ArrayStack

class UndoRedo:
    def __init__(self):
        self._a: ArrayStack = ArrayStack()  # 栈 A：待撤销
        self._b: ArrayStack = ArrayStack()  # 栈 B：可反撤销

    def do(self, action: str) -> None:
        self._a.push(action)
        while not self._b.is_empty():  # 清空栈 B
            self._b.pop()

    def undo(self) -> str:
        """撤销：A 弹出并压入 B"""
        action = self._a.pop()
        self._b.push(action)
        return action

    def redo(self) -> str:
        """反撤销：B 弹出并压回 A"""
        action = self._b.pop()
        self._a.push(action)
        return action

其中 do 时清空栈 B 的细节正是 summary.md 第 1 条规则的直接落地，保证"执行新操作后不可重做旧分支"的语义正确。

六、选型建议：数组 vs 链表、栈 vs 队列

综合 summary.md 的结论与上述源码印证，可归纳如下选型参考：

维度	数组实现	链表实现
时间效率	平均 $O(1)$，扩容瞬间单次操作 $O(n)$	恒为 $O(1)$，表现稳定
空间效率	可能预留空位造成浪费，但元素连续、无指针开销	每节点额外携带指针，单个节点内存更大
实现依据	codes/python/chapter_stack_and_queue/array_stack.py、codes/python/chapter_stack_and_queue/array_queue.py、codes/python/chapter_stack_and_queue/array_deque.py	codes/python/chapter_stack_and_queue/linkedlist_stack.py、codes/python/chapter_stack_and_queue/linkedlist_queue.py、codes/python/chapter_stack_and_queue/linkedlist_deque.py

• 若访问模式高度依赖"最近元素"（LIFO）且追求缓存局部性，优先数组栈；
• 若操作严格 FIFO 且规模不可预估，链表队列/环形数组队列都是合理选择，环形数组（% capacity 取余）是工程上的常用折中；
• 若需求允许两端进出的任意组合（撤销/重做、历史记录、滑动窗口变体等），选择双向队列，它以一份结构覆盖了栈与队列的全部能力。

以上实现均以当前仓库代码为准；由于各语言标准库（如 Python collections.deque、Java ArrayDeque/LinkedList、C# Deque<T> 等）的具体行为与扩容策略可能不同，跨语言对照时建议以对应语言的官方文档为准，仓库代码主要用于理解数据结构本身的组织方式。