企业官网建设流程全解析

Hello 算法 栈与队列练习精讲：从 LIFO/FIFO 心智模型到环形数组与双向队列的源码级验证

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本文围绕《Hello 算法》“栈与队列”一章的配套练习（练习文档）展开，完整讲解三道知识巩固题（栈队列出元素顺序、环形数组取余、双向队列两端操作）和一道括号合法性编程题。结合仓库中 基于环形数组的队列实现、基于环形数组的双向队列实现 等源码，将每道练习题的关键公式逐一落到真实代码行，帮助读者在动手刷题前建立可验证的数据结构直觉。

练习题全貌与学习路径

练习文档将本章练习分为两部分：

• 知识巩固：通过纸面推演建立栈、队列、双向队列的操作心智模型，共 3 题；
• 编程练习：用栈实现经典的括号序列合法性判断，共 1 题。

建议的学习路径是：先独立推演前 3 题，再对照本文的逐步解析与源码验证，最后动手完成编程题。本章的概念基础分别来自 栈、队列、双向队列 三篇文档，文末的 小结 还附有 Q & A 可作为延伸阅读。

练习一：栈和队列会先取出谁

题目

准备一个空栈S和一个空队列Q，分别对它们执行同一组操作：

1. 加入A；
2. 加入B；
3. 移除一个元素并记录；
4. 加入C；
5. 不断移除并记录，直到容器为空。

请分别写出S和Q中元素被移除的顺序，并用“先入后出”或“先入先出”解释差异。

参考答案与逐步推演

栈S的移除顺序是B、C、A。逐步状态如下：

加入A、B后先弹出最近加入的B，再加入C，此后依次弹出C、A，体现“先入后出”（LIFO）。

队列Q的移除顺序是A、B、C。逐步状态如下：

加入A、B后先移除最早加入的A，再加入C，此后依次移除B、C，体现“先入先出”（FIFO）。

源码验证

这道题的本质是确认“栈只从一端进出、队列从两端分别进出”。仓库中的 数组栈实现 正好体现了这一点：push调用self._stack.append(item)，pop调用self._stack.pop()，两者都只作用于数组尾部这一个位置（见 array_stack.py L23-L37），因此后进的元素必然先出。而 链表栈 采用头插法实现，效果等价。用栈类语言（如 Java 的Stack.push()/pop()、C++ 的std::stack）复现这组操作，得到的顺序与上表完全一致。

练习二：队尾越过数组末尾怎么办

题目

用长度为 5 的环形数组实现队列，数组索引为0～4。当前front = 3、size = 2，队列中的A、B分别位于索引 3、4。

1. 执行“C入队”时，C应放在哪个索引？入队后size是多少？
2. 接着执行一次出队，弹出哪个元素？新的front和size分别是多少？
3. 此时从队首到队尾的逻辑顺序是什么？出队时是否需要移动数组中的其他元素？为什么？

参考答案

1. 新元素的位置为(front + size) % 5 = (3 + 2) % 5 = 0，所以C放在索引 0。入队后size = 3。
2. 出队弹出当前队首A。新的队首索引为(3 + 1) % 5 = 4，因此front = 4、size = 2。
3. 有效元素的逻辑顺序为B、C，其中B位于索引 4，C位于索引 0。出队时只需移动front并修改size，环形数组用取余让索引回到开头，因此无须把其他元素整体向前移动。

源码验证：环形数组取余的真实代码

这正是 queue.md 中“基于数组的队列实现”的核心设计：以front指向队首、size记录长度，定义rear = front + size（越过尾部后回绕），有效元素区间为[front, rear - 1]。仓库中 array_queue.py 的push与pop逐行对应了题目中的两个公式：

def push(self, num: int): """入队""" if self._size == self.capacity(): raise IndexError("队列已满") # 计算队尾指针，指向队尾索引 + 1 # 通过取余操作实现 rear 越过数组尾部后回到头部 rear: int = (self._front + self._size) % self.capacity() # 将 num 添加至队尾 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

• 入队公式rear = (front + size) % capacity（array_queue.py L35）与题目中的(3 + 2) % 5 = 0完全一致；
• 出队公式front = (front + 1) % capacity（array_queue.py L44）与题目中的(3 + 1) % 5 = 4完全一致；
• 全程只改指针和计数器，没有任何元素搬移，印证了第 3 小问的结论。

此外，该文件末尾的 Driver Code 还专门用一轮循环验证了环形回绕行为（array_queue.py L94-L98）：连续执行 10 次“入队 + 出队”，front会在取余作用下不断从索引 4 绕回 0，可直接运行观察。

需要注意的边界：当size == capacity时push抛出“队列已满”异常，即本实现是固定容量队列；文档中也指出，若需容量可增长，可将定长数组替换为动态数组并引入扩容机制。

练习三：双向队列的两端操作

题目

这里规定：push_first表示从队首加入，push_last表示从队尾加入，pop_first表示从队首弹出，pop_last表示从队尾弹出。对一个空的双向队列deq依次执行：

1. push_last(A)

2. push_last(B)

3. push_first(C)

4. pop_last()

5. push_last(D)

6. pop_first()

7. 两次弹出的元素分别是什么？

8. 全部操作完成后，从队首到队尾还剩哪些元素？

9. 检查这 6 步操作：只允许从队尾加入、从队首删除的队列能否全部完成？如果不能，请指出无法完成的操作；再说明双向队列能否完成及其原因。

参考答案

前三步后，双向队列从队首到队尾为[C, A, B]。

1. pop_last()弹出B；加入D后队列为[C, A, D]，pop_first()再弹出C。
2. 最后剩下[A, D]。
3. 只允许在队尾添加、在队首删除的队列不能完成全部操作：第 3 步push_first(C)要求从队首加入，第 4 步pop_last()要求从队尾删除，都超出了这种队列的操作范围。双向队列的两端都可以添加和删除，因此能够完成这 6 步操作。

完整推演表如下：

源码验证：环形数组如何支持两端操作

这道题的四个操作在 array_deque.py 中都有对应实现。与队列实现的关键差异是双向队列需要一个能处理负数索引的取余函数：

def index(self, i: int) -> int: """计算环形数组索引""" # 通过取余操作实现数组首尾相连 # 当 i 越过数组尾部后，回到头部 # 当 i 越过数组头部后，回到尾部 return (i + self.capacity()) % self.capacity()

（array_deque.py L29-L34）+ self.capacity()保证当push_first使front越过数组头部（front - 1变成负数）时，取余结果仍能回到尾部。

四个操作的指针变化分别是：

• push_first：先执行self._front = self.index(self._front - 1)再写入元素（L36-L46）——对应题目第 3 步C被插入到A之前；
• push_last：rear = self.index(self._front + self._size)后写入（L48-L57）；
• pop_first：self._front = self.index(self._front + 1)（L59-L65）；
• pop_last：仅将size减 1，因为队尾元素索引恒为index(front + size - 1)（L67-L71）。

仓库还提供了基于双向链表的另一种实现 linkedlist_deque.py：push(num, is_front)与pop(is_front)两个统一方法通过布尔参数区分端点，队首入队时维护node.next / front.prev，队尾入队时维护rear.next / node.prev（L35-L53），与 deque.md 中“双向链表两端增删”的图示流程一致。两种实现的对比结论与队列相同：数组实现缓存局部性好、扩容可能触发O(n)的一次性开销；链表实现效率更稳定但节点携带额外指针。

编程练习：检查括号序列

题目

给定一个只包含()、[]、{}这三类括号的字符串s，请使用栈判断它是否合法。

合法序列须同时满足：每个右括号都必须与最近一个尚未配对的左括号类型匹配，并且遍历结束后没有未配对的左括号。返回布尔值表示判断结果。

解题提示

1. 可以建立“右括号到对应左括号”的映射；
2. 遇到右括号时，先检查栈是否为空，再检查栈顶是否匹配；
3. 遍历结束后，栈也必须为空。

本题对应 LeetCode 的“Valid Parentheses”（有效的括号）题目，原文档附有线上平台与题目解析的入口链接。

参考实现

结合本章知识，用 ArrayStack 即可实现。核心逻辑与仓库栈实现一一对应：遇到左括号push入栈，遇到右括号用peek检查栈顶类型后pop配对：

def is_valid(s: str) -> bool: """判断括号序列是否合法""" # 右括号 -> 对应左括号 的映射（提示 1） pairs = {")": "(", "]": "[", "}": "{"} stack: list[str] = [] for ch in s: if ch in pairs.values(): # 左括号：入栈 stack.append(ch) else: # 右括号：出栈配对 # 提示 2：先判空，再判栈顶是否匹配 if not stack or stack.pop() != pairs[ch]: return False # 提示 3：遍历结束后栈必须为空 return len(stack) == 0

三个边界情况各对应一条判据，缺一不可：

• 右括号无左括号可配：如")("中第一个字符就是右括号，此时栈为空，若直接访问栈顶会越界，因此必须先判空；
• 类型不匹配：如"(]"，栈顶是(却遇到了]，pop后比较不相等即返回False；
• 遍历后仍有剩余：如"((("，所有右括号都配平了但栈中残留左括号，最终len(stack) != 0返回False。

时间复杂度 $O(n)$（每个字符最多一次入栈、一次出栈，栈操作均为 $O(1)$），空间复杂度 $O(n)$（最坏情况全为左括号）。也可以改用各语言内置容器——如 Python 的list、C++ 的std::stack、Java 的Stack——替代自建栈，效果等价，这正是 stack.md 中“把数组/内置类当作栈使用”的推荐做法。

延伸：本章练习可对照的仓库源码

完成练习后，建议通读以下多语言实现，观察同一逻辑在不同语言中的表达差异：

• 栈：Python 数组栈、Python 链表栈；
• 队列：Python 环形数组队列、Python 链表队列；
• 双向队列：Python 环形数组双向队列、Python 双向链表双向队列；
• 概念与图示文档：栈、队列、双向队列；
• 章节要点回顾与 Q & A：小结。

另外，deque.md 末尾的“撤销步数上限”案例值得结合练习三理解：当撤销栈长度超过上限时，需要从栈底删除元素，普通栈无法完成，这正是双向队列pop_first的用途——linkedlist_deque.py 的pop_first方法可直接复用在该场景中。

小结

本章练习以三道纸面推演题加一道编程题，覆盖了“栈与队列”一章的三个关键认知点：

1. 顺序差异源于端点规则：栈两端合一（顶），队列两端分离（首、尾），LIFO 与 FIFO 的顺序差异可直接从操作序列推演得出；
2. 环形数组用取余代替搬移：(front + size) % capacity决定了入队位置，(front + 1) % capacity完成出队，全程 $O(1)$ 且不移动任何元素；
3. 双向队列补齐两端对称操作：push_first需要“负方向”取余（(i + capacity) % capacity），这是环形数组实现双向队列比实现普通队列多出的唯一难点；
4. 栈的经典应用：括号匹配是“最近未配对项优先”问题的标准解法，判空、判类型、判剩余三条判据对应三种非法形态。

按“先推演、再对代码、后写程序”的顺序完成这套练习，即可把本章的概念性知识固化为可直接落地的实现能力。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo