第十单元：栈操作 · 后进先出与物品调度

上一单元你掌握了"先进先出"的队列，这一单元将学习它的孪生兄弟——栈（stack）。在封神冰川的地牢里，农民背着一个特殊的背包：他每拾起一件物品，物品就叠在背包最上面；他也只能取出最上面那一件。三把钥匙、三扇门，收集的顺序稍有差错就会打不开门。这背后正是计算机科学又一个核心数据结构：栈（stack），以及它"后来居上、先出先取"的独特脾气。

10.1.1 什么是栈（What Is a Stack）

10.1.1.1 只能在顶部进出的集合 A collection you add to and remove from the top

栈是一种线性集合：元素总是从顶部（top）加入，也只能从顶部取出。你唯一能直接访问的，永远是"最后一个放进去"的元素。要拿到底部的东西，必须先把压在它上面的一件件取走。这与队列的"两端进出"截然不同——栈只有一个开口。

10.1.2 LIFO 后进先出（Last In, First Out）

10.1.2.1 最后进的最先出 The last one in is the first one out

栈的核心规则叫 LIFO——Last In, First Out，"后进先出"。最后一个入栈的元素，会是第一个出栈的。这与队列的"先进先出（FIFO）"正好相反。栈特别适合处理"撤销/回退""层层嵌套""最近优先"的场景：浏览器的后退按钮、编辑器的撤销、函数调用栈等，本质都是栈。

10.2.1 pickUpItem 入栈（Push to the Top）

10.2.1.1 把物品压到栈顶 Add an item onto the top

入栈（push）就是把一个新元素放到栈的顶部。关卡里农民用 pickUpItem 拾取物品——每拾一件，它就叠到背包最上面。用列表实现时，入栈就是 append（加到列表末尾，末尾即栈顶）。

# 关卡里：农民拾取物品 = 入栈
hero.command(peasant, "pickUpItem", goldKey)   # 金钥匙压到栈顶

# 用列表实现时，入栈 = append
stack = []
stack.append(3)   # PUSH 3 → [3]
stack.append(5)   # PUSH 5 → [3, 5]，5 在栈顶

10.2.2 dropItem 出栈（Pop from the Top）

10.2.2.1 只能取走栈顶那一件 Remove the item on top

出栈（pop）就是把栈顶（最后放入）的元素取出并移除。农民用 dropItem 放下物品——他只能放下最上面那一件。用列表实现时，出栈就是 pop()（不带参数，移除并返回列表最后一个元素）。

# 关卡里：农民放下栈顶物品 = 出栈
hero.command(peasant, "dropItem", {"x": 40, "y": 34})   # 放下最上面那件

# 用列表实现时，出栈 = pop()
top = stack.pop()   # POP → top=5，栈变 [3]

10.2.3 peekItem 查看栈顶（Peek at the Top）

10.2.3.1 只看栈顶，不取走 Look at the top without removing

查看栈顶（peek）是指"看一眼最上面是什么"，但不把它取走。农民用 peasant.peekItem() 返回背包顶部的物品。这在"扔掉之前先看清楚"的场景里极其有用——先 peek 判断栈顶类型，再决定该把它 dropItem 到哪里。

# peek：先看栈顶是什么，栈不变
topItem = peasant.peekItem()
hero.say(topItem.type)   # 说出栈顶物品的类型

10.3.1 append 与 pop()（The Two Core Methods）

10.3.1.1 一个列表 + 两个方法 = 栈 A list plus two methods makes a stack

和队列一样，栈也能用普通列表实现——只不过约定改成"从末尾 append 入栈、从末尾 pop() 出栈"。列表的末尾同时充当"栈顶"，进出都在这一端。

# 用列表完整演示一个栈
stack = []
stack.append(3)   # PUSH → [3]
stack.append(5)   # PUSH → [3, 5]
top = stack.pop()   # POP → top=5，栈=[3]（后进的 5 先出）

10.3.2 空栈检查（Checking for an Empty Stack）

10.3.2.1 取栈顶前先确认栈里有东西 Make sure the stack isn't empty first

从空栈 pop() 会报错。所以出栈或 peek 前要先判空。关卡里常用 while peasant.peekItem(): 作为循环条件——只要栈顶还有物品（peek 非空）就继续处理，一旦栈空 peek 返回 None（假），循环自动停止。

# 用 peek 是否为空来控制循环，处理到栈空为止
while peasant.peekItem():   # 栈顶还有东西就继续
    topItem = peasant.peekItem()
    # ...根据 topItem 决定放哪里，再 dropItem...

10.4.1 入栈顺序决定出栈顺序（Push Order Dictates Pop Order）

10.4.1.1 想最先取谁，就最后放谁 To pop it first, push it last

栈最烧脑也最精妙的一点：你入栈的顺序，反过来就是出栈的顺序。在"密钥栈"关卡里，三把钥匙要按门的顺序放下。因为最后拾起的钥匙在栈顶、会最先被放下，所以——想让某把钥匙最先用，就要最后才拾起它。这需要"倒着想"：先规划好放下的顺序，再反推拾起的顺序。

10.4.2 按栈顶类型决定放置位置（Route by Top Item's Type）

10.4.2.1 先 peek 看类型，再 drop 到对应位置 Peek the type, then drop to the right place

在"堆栈分类"和"炼金堆"里，物品要按类型送到不同地方（蘑菇给雪人、药水给英雄/牦牛、发光石给骷髅）。做法是：循环中先 peekItem() 读出栈顶物品，用 if / elif 判断它的 type，再 dropItem 把它放到对应目标的位置。这样每次都根据"最上面是什么"来决定"该丢到哪"。

# 先 peek 看栈顶类型，再决定放到哪个位置
while peasant.peekItem():
    topItem = peasant.peekItem()
    if topItem.type == "potion":
        hero.command(peasant, "dropItem", yakPos)       # 药水给牦牛
    elif topItem.type == "mushroom":
        hero.command(peasant, "dropItem", yetiPos)      # 蘑菇给雪人
    elif topItem.type == "lightstone":
        hero.command(peasant, "dropItem", skeletonPos)  # 发光石给骷髅

10.5.1 两种结构对比（Comparing the Two Structures）

10.5.1.1 一个先进先出，一个后进先出 FIFO versus LIFO

队列和栈是一对经典的"孪生数据结构"，都用列表实现、都只在特定位置进出，区别只在出的方向。理解它们的对照，能帮你在遇到问题时选对工具：需要"公平排队、先来先服务"用队列；需要"回退、撤销、最近优先"用栈。

这一节聚焦每一关的策略、思路与算法设计，只展示用于说明的关键片段，完整通关程序请你自己动手完成。

第 21 关 · 密钥栈

🧊 密钥栈 —— 用入栈顺序规划开门

图2：密钥栈——农民背包是个栈，最后拾起的钥匙在栈顶最先放下，须倒推拾取顺序才能依次开三扇门

策略：倒着规划——想先放的钥匙最后拾

三把钥匙对应三扇门，钥匙必须放在对应门边才能开门（扔远了会碎、门还会自动关）。核心难点在于：农民只能放下栈顶（最后拾起）的钥匙。所以策略是倒推——先确定放钥匙的先后（第一扇门先开、就要第一个放），再反过来安排拾取顺序：第一个要放的钥匙，最后一个拾起（让它待在栈顶）。

思路拆解：拾取与放下顺序相反

假设三扇门从近到远要依次用钥匙 A、B、C 打开。因为栈是 LIFO，拾取顺序要写成 C、B、A（A 最后拾、在栈顶）。这样第一次 dropItem 放下的就是栈顶的 A，正好开第一扇门；接着 B、再 C。拾取和放下，方向恰好相反——这正是栈"顺序即命运"的直接体现。

# 关键片段：按倒序拾取（最后拾的钥匙将最先放下）
hero.command(peasant, "pickUpItem", goldKey)     # 先拾，压栈底
hero.command(peasant, "pickUpItem", silverKey)
hero.command(peasant, "pickUpItem", bronzeKey)   # 最后拾，在栈顶

# 放下顺序 = 拾取的逆序：栈顶(铜)先放
hero.command(peasant, "dropItem", {"x": 40, "y": 34})   # 第一扇门
hero.command(peasant, "dropItem", {"x": 31, "y": 34})   # 第二扇门
hero.command(peasant, "dropItem", {"x": 22, "y": 34})   # 第三扇门

钥匙别扔远、动作要快：关卡提示——钥匙扔离门口会碎，且门开后短时间会关。所以要先在门边就位再放，放完钥匙后立刻让农民/英雄冲进去收集宝藏，别磨蹭。

这一关的意义：密钥栈让你亲身体会栈"只能操作栈顶"的约束，以及由此带来的"倒序思维"。这种"要先用的东西最后放"的规划，在很多实际问题（如撤销操作、递归回溯）中都会遇到。

第 22 关 · 堆栈分类

❄️ 堆栈分类 —— peek 栈顶再按类型分发

图3：堆栈分类——先把物品全部入栈，再循环 peekItem 看栈顶类型，蘑菇给雪人、药水给牦牛、发光石给骷髅

策略：先全部入栈，再逐个 peek 分发

这一关要把物品按类型送给三个对象。策略分两阶段：收集阶段——用 for 循环把所有物品 pickUpItem 全部入栈；分发阶段——用 while peasant.peekItem(): 循环，每次先 peek 看栈顶是什么类型，再 dropItem 到对应目标位置，直到栈空。"扔之前先看一眼"是本关的点题之笔。

思路拆解：peek 判断 + 分类 drop

分发时用 peekItem() 拿到栈顶物品（不移除），判断 type：potion → 牦牛、mushroom → 雪人、lightstone → 骷髅，用 if / elif 分派，再 dropItem 到对应坐标。dropItem 会把栈顶那件放下（即移除），于是下次循环 peek 到的就是新栈顶。循环条件 while peasant.peekItem() 保证栈空自动停止。

# 关键片段：收集阶段——全部入栈
for item in items:
    hero.command(peasant, "pickUpItem", item)

# 关键片段：分发阶段——peek 栈顶，按类型 drop
while peasant.peekItem():
    topItem = peasant.peekItem()
    if topItem.type == "potion":
        hero.command(peasant, "dropItem", yakPos)
    elif topItem.type == "mushroom":
        hero.command(peasant, "dropItem", yetiPos)
    elif topItem.type == "lightstone":
        hero.command(peasant, "dropItem", skeletonPos)

为什么先 peek 再 drop：因为你必须先知道栈顶是什么类型，才能决定把它送到哪里。peek 让你"只看不动"地读取类型，判断好目标后再 drop。如果不先 peek 就盲目 drop，物品就可能被送错对象。

别忘了循环判空：用 while peasant.peekItem(): 而不是 while True:——栈空时 peek 返回 None，循环才能正常结束。若用死循环又不判空，栈空后再 peek/drop 就会出错。

第 23 关 · 炼金堆

🏔️ 炼金堆 —— 栈的综合运用击败雪人

图4：炼金堆——先用钥匙开门（钥匙留到最后拾放栈顶），再把蘑菇喂雪人削弱、药水治英雄，最后击败雪人

策略：先开门取物，再按类型分发治敌

这是栈单元的综合关，融合了前两关的技巧。目标是削弱并击败古代雪人：蘑菇喂雪人削弱它、药水献给英雄治愈自己，最后攻击取胜。难点在于还有一把金钥匙要开门——它必须最后拾起好留在栈顶最先放下开门，其余物品先入栈。

思路拆解一：钥匙留到最后拾（放栈顶）

先用 for 循环把除钥匙外的物品都入栈（用 if item.type != "gold-key" 过滤掉钥匙），然后单独把钥匙 pickUpItem——这样钥匙就在栈顶。先 dropItem 放下钥匙开门，再处理下面的蘑菇和药水。这正是"要先用的最后放"的应用。

# 关键片段：先入其他物品，钥匙最后拾放栈顶
for item in items:
    if item.type != "gold-key":       # 钥匙先不拾
        hero.command(peasant, "pickUpItem", item)
key = peasant.findNearestByType("gold-key")
hero.command(peasant, "pickUpItem", key)     # 钥匙最后拾 → 栈顶
hero.command(peasant, "dropItem", {"x": 38, "y": 34})  # 先放钥匙开门

思路拆解二：peek 分发蘑菇与药水，再攻击

开门后，用 while peasant.peekItem(): 循环处理剩下的物品：peek 栈顶，若是 potion 就 dropItem 到英雄脚下（hero.pos）治疗，否则（蘑菇）就丢到雪人位置削弱它。全部分发完，再用一个循环持续 hero.attack(yeti) 直到击败它。

# 关键片段：药水给英雄，蘑菇给雪人
while peasant.peekItem():
    if peasant.peekItem().type == "potion":
        hero.command(peasant, "dropItem", hero.pos)   # 药水治英雄
    else:
        hero.command(peasant, "dropItem", yeti.pos)   # 蘑菇削弱雪人
# 削弱并治愈后，攻击直到击败雪人
while yeti.health > 0:
    hero.attack(yeti)

卡关就回顾前两关：关卡官方建议——如果炼金堆卡住了，重玩"密钥栈"和"堆栈分类"能帮你复习。开门难点在于"拿钥匙前先检查物品类型、把钥匙留到最后拾"，这样它就在栈顶、能第一个放下开门。

10.7.1 新手最容易踩的坑（Pitfalls for Beginners）

10.7.1.1 栈操作的典型问题 Typical issues with stack operations

图5：拾取顺序搞反、pop 用错、不先 peek、忘判空，是本单元最常见的失误