Day 028 — 数据结构综合：图解
ASCII 与 Mermaid 示意图，帮助理解栈、队列、堆、二分查找和表达式求值的原理
1️⃣ 栈（Stack）— LIFO
push → pop →
┌─────┐ ┌─────┐
│ 5 │ │ │
├─────┤ ├─────┤
│ 4 │ │ 5 │
├─────┤ → ├─────┤
│ 3 │ │ 4 │
├─────┤ ├─────┤
│ 2 │ │ 3 │
├─────┤ ├─────┤
│ 1 │ │ 2 │
└─────┘ └─────┘
入栈 出栈(5)
调用栈示例
函数调用: main() → foo() → bar()
调用栈状态:
┌──────────┐
│ bar() │ ← 当前执行
├──────────┤
│ foo() │ ← 等待 bar 返回
├──────────┤
│ main() │ ← 等待 foo 返回
└──────────┘
2️⃣ 队列（Queue）— FIFO
enqueue → ← dequeue
│ │
▼ ▼
┌────┬────┬────┬────┬────┐
│ 5 │ 4 │ 3 │ 2 │ 1 │
└────┴────┴────┴────┴────┘
队尾 队头
入队顺序: 1 → 2 → 3 → 4 → 5
出队顺序: 1 → 2 → 3 → 4 → 5
双向队列 (deque) 操作
appendleft append
│ │
▼ ▼
┌────┬────┬────┬────┬────┐
│ 1 │ 2 │ 3 │ 4 │ 5 │
└────┴────┴────┴────┴────┘
▲ ▲
popleft pop
3️⃣ 堆（Heap）— 最小堆
完全二叉树结构
1
/ \
/ \
3 5
/ \ / \
7 6 8 9
数组表示: [1, 3, 5, 7, 6, 8, 9]
索引关系:
parent(i) = (i-1)//2
left_child(i) = 2*i + 1
right_child(i)= 2*i + 2
堆的插入（上浮）
插入 0:
初始: [1, 3, 5, 7, 6, 8, 9]
追加: [1, 3, 5, 7, 6, 8, 9, 0]
↑
比较 0 < 7 → 交换
[1, 3, 5, 0, 6, 8, 9, 7]
↑
比较 0 < 3 → 交换
[1, 0, 5, 3, 6, 8, 9, 7]
↑
比较 0 < 1 → 交换
[0, 1, 5, 3, 6, 8, 9, 7]
堆的删除（下沉）
弹出最小值 0:
初始: [0, 1, 5, 3, 6, 8, 9, 7]
弹出 0，将末尾 7 移到堆顶
[7, 1, 5, 3, 6, 8, 9]
比较 7 > min(1, 5) → 与 1 交换
[1, 7, 5, 3, 6, 8, 9]
比较 7 > min(3, 6) → 与 3 交换
[1, 3, 5, 7, 6, 8, 9] ✓ 满足堆性质
4️⃣ 二分查找（Binary Search）
查找目标: 7
┌───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 3 │ 5 │ 7 │ 9 │11 │13 │15 │17 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┘
↑ ↑ ↑
L=0 mid=4 R=8
arr[4]=9 > 7 → R=3
┌───┬───┬───┬───┬───┐
│ 1 │ 3 │ 5 │ 7 │ 9 │
└───┴───┴───┴───┴───┘
↑ ↑ ↑
L=0 mid=1 R=3
arr[1]=3 < 7 → L=2
┌───┬───┬───┬───┐
│ 5 │ 7 │ 9 │ │
└───┴───┴───┴───┘
↑ ↑ ↑
L=2 mid=2 R=3
arr[2]=5 < 7 → L=3
┌───┬───┬───┬───┐
│ 7 │ 9 │ │ │
└───┴───┴───┴───┘
↑ ↑
L=3 R=3
arr[3]=7 == 7 ✓ 找到!
5️⃣ 表达式求值流程
输入: "3 + 4 * (2 - 1)"
Token
│
▼
┌──────────────┐
│ Tokenize │
└──────────────┘
│
["3","+","4","*","(","2","-","1",")"]
│
▼
┌──────────────┐
│ 调度场算法 │
│ (两个栈) │
└──────────────┘
│
["3","4","2","1","-","*","+"]
│
▼
┌──────────────┐
│ 后缀求值 │
│ (一个栈) │
└──────────────┘
│
结果: 7.0
调度场算法执行过程
Token │ 操作 │ 输出 │ 运算符栈
───────┼─────────────┼───────────────────┼─────────────
3 │ 入队 │ 3 │
+ │ 入栈 │ 3 │ +
4 │ 入队 │ 3 4 │ +
* │ 入栈(*>+优先级)│ 3 4 │ + *
( │ 入栈 │ 3 4 │ + * (
2 │ 入队 │ 3 4 2 │ + * (
- │ 入栈 │ 3 4 2 │ + * ( -
1 │ 入队 │ 3 4 2 1 │ + * ( -
) │ 弹栈直到( │ 3 4 2 1 - │ + *
│ 入栈结束 │ │
│ 清空栈 │ 3 4 2 1 - * + │
后缀: 3 4 2 1 - * +
后缀求值过程
符号 │ 操作 │ 栈
───────┼─────────────────┼─────────
3 │ 压栈 │ [3]
4 │ 压栈 │ [3, 4]
2 │ 压栈 │ [3, 4, 2]
1 │ 压栈 │ [3, 4, 2, 1]
- │ 弹出2和1, 2-1=1 │ [3, 4, 1]
* │ 弹出4和1, 4*1=4 │ [3, 4]
+ │ 弹出3和4, 3+4=7 │ [7]
最终结果: 7
6️⃣ 各数据结构操作复杂度对比
操作 │ 栈 │ 队列 │ 堆 │ 二分查找(bisect)
──────────────┼────────┼────────┼────────┼────────────────
插入 │ O(1) │ O(1) │ O(log n)│ O(n) (insort)
删除 │ O(1) │ O(1) │ O(log n)│ —
查询最小/大 │ — │ — │ O(1) │ —
查找元素 │ — │ — │ — │ O(log n)
遍历 │ O(n) │ O(n) │ O(n) │ O(n)
空间 │ O(n) │ O(n) │ O(n) │ O(n)
7️⃣ 双堆法求中位数
数据流: [5, 3, 8, 1, 7, 9, 2, 6, 4]
最大堆 (lo) 最小堆 (hi)
┌────────┐ ┌────────┐
│ 3 │ │ 5 │
│ / \ │ │ / \ │
│ 1 2 │ │ 7 8 │
└────────┘ └────────┘
max=3 min=5
size=4 size=4
中位数 = (3 + 5) / 2 = 4.0 (偶数个)
添加后一个数:
┌────────┐ ┌────────┐
│ 5 │ │ 7 │
│ / \ │ │ / \ │
│ 3 4 │ │ 8 9 │
│ / │ │ │
│1 │ │ │
└────────┘ └────────┘
max=5 min=7
size=5 size=4
中位数 = 5 (奇数个)