# 参考解 · lab 0010 · 后进先出与先进先出

**做完五个任务再打开这里。** 这里的五个 `.py` 与任务目录里的文件同名：
把它们拷进 `lab/0010-stack-and-queue/` 覆盖同名文件，再跑 `py run_tests.py`，
应当五个任务全过（本机实测十几秒，其中 `pop(0)` 那 20 万次自己就占一秒多）。

参考解是自包含的：`tools.py` 与 `run_tests.py` 这里各有一份，拷过去直接就能跑。
`task4` 与 `task5` 只 `import` 给好的 `tools`，任务之间**不互相 import**，
所以拷一个也能跑；但五个一起拷最省事。

## 逐个任务看什么

| 任务 | 参考解里补上的关键几行 | 要看的现象 |
| --- | --- | --- |
| 1 · 栈与队列 | `Stack.pop` 是 `return self._data.pop()`；`Queue.dequeue` 是 `return self._data.popleft()` | 出栈顺序是入栈顺序的反序；出队顺序与入队顺序相同；300 步随机操作里每一步的栈顶/队头都与参照模型一致；空栈 `pop` 抛 `IndexError: pop from empty list` |
| 2 · 两种出队的代价 | 一个循环里 `total_list += lst.pop(0)`，另一个 `total_deque += dq.popleft()` | 20 万次出队：`pop(0)` 约 1.4 秒、`popleft()` 约 0.014 秒（本机约 100 倍）。列表删第一个元素要把后面全部往前挪一格（$O(n)$），出 $n$ 次退化成 $O(n^2)$；deque 两端都是 $O(1)$ |
| 3 · 括号匹配 | `is_valid` 里 `if not st or st[-1] != pair[ch]: return False`，最后 `return not st`；`first_error` 把三种情形各换成 `return i` / `return st[0]` | 九个用例全对：`([)]`→2、`(]`→1、`((`→0、`)))`→0、`(()`→0、正确的→-1。**左括号没等到时交回的是栈最底下那个的下标 `st[0]`**，不是 `st[-1]` |
| 4 · 表达式求值 | 后缀：`b = st.pop()` 先弹、`a = st.pop()` 后弹，按 `a - b` / `a // b` 算；中缀：`parse` 把数字攒成 `int`，`value` 用两栈 + `PRIORITY` 表 | 后缀五组 14 / 3 / 3 / 77 / 6；中缀六组 15 / 9 / 40 / 8 / 4 / 18。`52-` 是 3（写成 `b - a` 会变 -3）、`93/` 是 3（写成 `b // a` 会变 0）；`9-3+2` 是 8（优先级比较写成 `>` 会变 4） |
| 5 · 单调队列 | 队尾：`while q and a[q[-1]] <= a[i]: q.pop()`；入队；队首：`if q[0] <= i - k: q.popleft()`；`if i >= k - 1:` 才输出 | 课件那组 `[3, 3, 5, 5, 6, 7]`；`[7, 1, 1, 1, 1]`、k=3 是 `[7, 1, 1]`，而漏掉队首检查的错版给 `[7, 7, 7]`；四档 k 上单调队列基本不动（本机 0.97–1.10 倍），暴力那一列从 k=100 到 k=2000 涨 17 倍上下 |

## 每个任务的「为什么」

- **任务 1**：栈与队列的差别只有一处——**进出是不是同一端**。列表的 `append` 与不带参数的
  `pop` 都在末尾，代价 $O(1)$（`append` 是均摊，第 2 课那层意思），所以列表天生就是栈；
  队列要在另一端出，列表的 `pop(0)` 就要挪动整个后半段，于是容器换成 `deque`。
  判分不看「结果碰巧对」，而是拿列表 `append`/`pop`、`deque` `append`/`popleft` 当参照模型
  逐步对照：结构与模型的每一步都要一样。
- **任务 2**：这条差距的量级要到 $n$ 足够大才看得清，因为每次 `pop(0)` 的 $O(n)$ 是「挪动」
  而不是「比较」——它跑在 C 层，单次很快，但 \(n\) 次加起来是 \(\frac{n(n-1)}{2}\) 次元素搬运。
  选容器时先数操作次数，再乘上第 3 课价格表里那一格的价格，这条账就出来了。
- **任务 3**：三种出错情形里，前两种在**读到的那个右括号**上就能定案（那时 `i` 就是答案），
  第三种只有读完全部才暴露，而暴露的位置是「最底下那个还没配对的左括号」——栈是自底向顶存的，
  它在 `st[0]`。为什么不是 `st[-1]`：`((` 里两个左括号都没配对，**先出错**的是最左那一个
  （它的右括号来得最晚），所以报 0。
- **任务 4**：栈顶是**后**读到的那个数，也就是右操作数，所以先 `b = st.pop()` 再 `a = st.pop()`；
  减法与除法不满足交换律，这一处写反了不会报错、只会静默给错答案（这正是第 8 课说的
  「不报错的错」）。中缀那两栈的规则可以一句话记住：**运算符要入栈，必须先把比它更急的都算掉**——
  同优先级的也从左往右算，所以比较要写 `>=`。
- **任务 5**：两条弹出各自回答一个问题。队尾那条回答「谁再也当不上答案」：被弹掉的元素要么
  已经出窗口，要么还在窗口里但新元素更大、且新元素更晚离开，此后每个含它的窗口都含新元素，
  于是它一次也用不到了。队首那条回答「答案必须来自窗口里面」：留着滑出窗口的旧值，输出就会
  拿它当答案——`[7, 1, 1, 1, 1]`、k=3 那组能看见这一点（`[7, 7, 7]` 对 `[7, 1, 1]`）。
  两条都做之后，每个下标最多入队一次、出队一次，代价 $O(n)$，与 $k$ 无关。

## 常见错法（对照自己的写法）

- **`Stack.pop` 忘了 `return`**：写成了 `self._data.pop()`，取出来的元素当场丢掉，
  函数交回 `None`。判分那一段「栈顶与模型一致」立刻不一样。
- **`Stack.pop` 写成 `pop(0)`**：从另一头取，出栈顺序与入栈顺序相同——那是队列的行为。
- **`Queue.dequeue` 写成 `self._data.pop()`**：`deque.pop()` 出的是**右端**，
  于是队列变成了栈。队列的左端出队方法叫 `popleft`。
- **`deque` 建成了列表**：`self._data = []` 之后 `popleft` 会报 `AttributeError`；
  这个结构的两端进出都要 $O(1)$，容器不能换。
- **两个循环写在同一个计时里**：任务 2 的两次计时各自只包住一个循环；
  包在一起量到的是总时间，看不出差距。
- **列表那一版写成 `lst.pop()`**：顺序反了、两个 `total` 对不上，
  而且那是 $O(1)$，量出来的倍数会变成个位数——一眼能看出量错了对象。
- **`is_valid` 少了 `not st`**：文本以 `)` 开头时 `st[-1]` 在空列表上取元素，报 `IndexError`。
- **`is_valid` 少了最后的 `return not st`**：`((` 会被判成正确（左括号没等到也算对了）。
- **`first_error` 第三种情形写成 `st[-1]`**：`(((` 会报 2，正确答案是 0。
- **后缀求值弹出顺序写反**：`52-` 给 -3、`93/` 给 0。要 `b = st.pop()` 在前。
- **后缀除法用了 `/`**：得到浮点数，后面的整数比较与输出都会跟着变。用 `//`。
- **中缀优先级比较写成 `>`**：同优先级会从右往左算，`9-3+2` 从 8 变成 4。
- **中缀忘了处理最后的数字**：表达式以数字结尾时 `parse` 里那个临时字符串还留着一个数，
  忘了收进结果就会少一段。`'12+3'` 切出来应当是 `[12, '+', 3]`。
- **遇到 `)` 时忘了弹掉 `(`**：运算符栈里留着 `(`，之后 `PRIORITY['(']` 直接报 `KeyError`。
- **单调队列里队尾比较写成 `<`**：相等的元素留在队里，队首可能是一个马上就要出窗口的旧值；
  写成 `<=` 才是「后来的、更大的或相等的，都把前面的替掉」。
- **单调队列少了 `i >= k - 1` 的判断**：前 $k-1$ 个位置也开始输出，结果比正确答案长一截。
- **单调队列少了队首过期检查**：这就是任务 5 的 TODO 2 那个错版，
  `[7, 1, 1, 1, 1]` 上给 `[7, 7, 7]`。它不会报错，只是从第二个窗口起全错。
- **硬凑 `print` 后的数字**：判分读的就是那些行，硬凑等于没做。
  改完先自己跑 `py <任务文件>.py` 对一遍，再跑 `py run_tests.py`。

## 做完之后用一句话回答

单调队列里的两条弹出（弹队尾、弹队首）各自回答什么问题？说清「少了哪一条、会在哪一组数据上
立刻看出来」，就算这一课练到位了。