PYTHON KNOWLEDGE · 14
栈、队列、链表与并查集
按访问顺序和更新需求理解线性结构，并掌握各操作的真实代价。
GESP 4 级GESP 5 级GESP 8 级
01 · FORMAL DEFINITION
正式定义
栈按后进先出访问，队列按先进先出访问，链表用节点引用连接次序，并查集维护元素所属的动态不相交集合。数据结构的价值在于为特定操作提供清晰语义和复杂度保证。
02 · MUST KNOW
学完这一章，必须说清楚的规则
- 01
Python list 的尾部 append/pop 可作栈，均摊 O(1)。
- 02
队列应使用 collections.deque 的 append/popleft，避免 list.pop(0) 的 O(n) 搬移。
- 03
循环队列用固定数组、队首队尾下标和取模复用空间，必须约定空与满的判定。
- 04
单链表节点保存值和 next；已知前驱时插入删除 O(1)，按下标查找仍是 O(n)。
- 05
并查集的 find 找代表元，union 合并集合；路径压缩与按大小/秩合并使均摊代价近似常数。
- 06
选择结构前先列出最频繁操作：随机访问、两端操作、按键查找或集合合并。
03 · RUNNABLE EXAMPLE
可运行示例与因果解释
from collections import deque
queue = deque(['A', 'B'])
queue.append('C')
print(queue.popleft())
print(list(queue))COMMON PITFALLS
常见误区
- 用 pop(0) 实现大规模队列
- 空栈空队列仍然弹出
- 链表改指针时丢失后续节点
- 并查集只改父节点却不理解代表元
SCOPE & BOUNDARIES
适用边界
- Python 没有课程必需的内置链表类型，教学实现用于理解指针关系；工程中应根据实际操作选择成熟容器。
- 并查集擅长连通性合并，不支持高效删除或一般最短路。