PYTHON LESSON 056
括号侦探与食堂叫号机
理解栈（后进先出）与队列（先进先出）的思想，用列表实现两者，认识循环队列。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- append() / pop() 搭出栈
- append() / pop(0) 搭出队列
- front / rear 指针 + 取模围成循环队列
01 · 核心概念
栈、队列与循环队列
栈、队列与循环队列：栈只有一端能操作：append 把元素“压”到栈顶，pop() 从栈顶“弹”出元素。最后放进去的最先被拿走，这就是后进先出（LIFO）。撤销、后退按钮背后都是它。
GESP Python 4 级 · 栈GESP Python 4 级 · 队列与循环队列复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
02 · 语法与规则
先记住这 3 条，再开始写程序
append() / pop() 搭出栈先准确读出这条写法的结构与作用。
append() / pop(0) 搭出队列换一组最小数据，手工推演一次结果。
front / rear 指针 + 取模围成循环队列再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 第一幕：括号侦探（栈，后进先出）
def check(formula):
"""检查算式的圆括号是否正确配对"""
stack = []
for ch in formula:
if ch == "(":
stack.append(ch) # 左括号进栈
elif ch == ")":
if not stack:
return False # 没有可配对的左括号
stack.pop() # 配成一对，左括号出栈
return len(stack) == 0
for f in ["(1+2)*3", "((1+2)", "(1+2))("]:
print(f, "→", "配对成功" if check(f) else "配对失败")
print("——————")
# 第二幕：食堂叫号机（队列，先进先出）
window = []
for num in ["A01", "A02", "A03"]:
window.append(num)
print("取号：", num, "｜队伍：", window)
while window:
serving = window.pop(0) # 队首出队
print("叫号：", serving, "请取餐｜剩余：", window)(1+2)*3 → 配对成功 ((1+2) → 配对失败 (1+2))( → 配对失败 —————— 取号： A01 ｜队伍： ['A01'] 取号： A02 ｜队伍： ['A01', 'A02'] 取号： A03 ｜队伍： ['A01', 'A02', 'A03'] 叫号： A01 请取餐｜剩余： ['A02', 'A03'] 叫号： A02 请取餐｜剩余： ['A03'] 叫号： A03 请取餐｜剩余： []
栈像一摞盘子（最后放上的最先拿走），队列像排队打饭（先来的先服务）。
04 · 逐步理解
每一步只解决一个问题
- 01
栈：后进先出的一摞盘子
栈只有一端能操作：append 把元素“压”到栈顶，pop() 从栈顶“弹”出元素。最后放进去的最先被拿走，这就是后进先出（LIFO）。撤销、后退按钮背后都是它。
stack.append(ch) stack.pop() - 02
用栈配括号
见到左括号就进栈，见到右括号就弹出一个配对；弹出时栈是空的，或最后栈里还有剩，都算配对失败。栈顶永远是“最近的、还没配对的左括号”，这正是配对需要的。
elif ch == ")": if not stack: return False stack.pop() - 03
三种失败情形
“((1+2)”左括号有剩、“(1+2))(”右括号多余、加了中括号后“([)]”顺序错位。三种失败都能被栈算法抓住——把每种都手动模拟一遍，你就真正懂栈了。
- 04
队列：先进先出的队伍
队列从队尾进（append）、队首出（pop(0)），先来先服务（FIFO）。pop(0) 在超大列表上偏慢，工程里常用 collections.deque，思想完全一样。
window.append(num) window.pop(0) - 05
循环队列：围成一圈的窗口
固定容量的数组也能当队列：front 指队首、rear 指队尾，走到数组末尾就用取模绕回开头，队列便“循环”起来，空间一点不浪费。
rear = (rear + 1) % k front = (front + 1) % k - 06
生活中的栈与队列
浏览器的后退前进、编辑器的撤销重做是栈；打印机任务、客服排队、消息通知是队列。下次用软件时猜一猜：这个功能背后站的是栈还是队列？
- 07
四级综合挑战
配套题库里的“浏览器后退前进”和“食堂循环叫号”是本单元的综合挑战：前者要两个栈打配合，后者要用循环队列防“假满”。通关它们，四级数据结构就算拿下！
05 · 练习与检验
自己写出来，才算真正学会
- 1运行括号侦探，验证三行算式
- 2自己写一行不匹配的考验它
- 3运行叫号机，观察出队顺序
- 4画出循环队列 front / rear 的移动图
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
核心数据结构栈、队列、链表与并查集按访问顺序和更新需求理解线性结构，并掌握各操作的真实代价。＋
正式定义
栈按后进先出访问，队列按先进先出访问，链表用节点引用连接次序，并查集维护元素所属的动态不相交集合。数据结构的价值在于为特定操作提供清晰语义和复杂度保证。
必须掌握
- Python list 的尾部 append/pop 可作栈，均摊 O(1)。
- 队列应使用 collections.deque 的 append/popleft，避免 list.pop(0) 的 O(n) 搬移。
- 循环队列用固定数组、队首队尾下标和取模复用空间，必须约定空与满的判定。
- 单链表节点保存值和 next；已知前驱时插入删除 O(1)，按下标查找仍是 O(n)。
- 并查集的 find 找代表元，union 合并集合；路径压缩与按大小/秩合并使均摊代价近似常数。
- 选择结构前先列出最频繁操作：随机访问、两端操作、按键查找或集合合并。
常见误区
- 用 pop(0) 实现大规模队列
- 空栈空队列仍然弹出
- 链表改指针时丢失后续节点
- 并查集只改父节点却不理解代表元
适用边界
- Python 没有课程必需的内置链表类型，教学实现用于理解指针关系；工程中应根据实际操作选择成熟容器。
- 并查集擅长连通性合并，不支持高效删除或一般最短路。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
Python 基础运算符、表达式与优先级完整区分算术、比较、逻辑、成员、身份和位运算，并用优先级表消除歧义。＋
正式定义
表达式求值得到一个值。运算符规定如何组合操作数；当一个表达式含多个运算符时，优先级和结合方向决定求值顺序，括号可以明确改变顺序。
必须掌握
- / 总是得到浮点结果；// 是向负无穷方向取整的整除；% 与 // 满足 a == (a // b) * b + a % b。
- 比较可以链式书写，如 0 <= x < 10；and/or 会短路并返回最后求值的操作数，不一定返回 bool。
- == 比较值是否相等，is 比较是否为同一个对象；判断 None 应写 is None。
- in/not in 做成员测试；对 dict 测试的是键。
- 位运算作用于整数的二进制位；负整数按无限长二进制补码语义理解。
- 复杂表达式即使能靠优先级正确运行，也应使用括号表达意图。
常见误区
- 把 // 当成简单截断
- 用 is 比较数字或字符串的值
- 忘记 and 的优先级高于 or
- 连续位移、比较和逻辑运算却不加括号
适用边界
- 浮点数比较受二进制表示误差影响，需要按问题选择容差。
- 运算符可由自定义类重载，因此相同符号对不同类型可能有不同语义。
完成检查