3.2 综合题：用两个栈实现一个队列

设置输入栈 in 和输出栈 out。入队只压入 in；出队时若 out 非空直接弹出，否则把 in 中所有元素逐个搬到 out，顺序被反转，最早进入者来到 out 顶。两栈都空才是真正队空。

void enqueue(int x){ in.push(x); }
bool dequeue(int& x){
  if(out.empty()) while(!in.empty()){out.push(in.top());in.pop();}
  if(out.empty()) return false;
  x=out.top();out.pop();return true;
}

关键是不在 out 尚有元素时搬运，否则新元素可能跑到旧元素前面，破坏 FIFO。

手工推演：入 1、2、3，第一次出队时搬运后 out 从顶到底为 1、2、3，弹 1；再入 4，此时 in=[4]、out 顶仍是 2，下一次必须弹 2，不能先搬 4。

单次出队最坏 $O(n)$，但一串操作的均摊成本为 $O(1)$：每个元素至多进入 in 一次、从 in 搬到 out 一次、从 out 弹出一次，总工作与元素数成正比。空间 $O(n)$。

错解反馈：每次出队都来回倒两遍虽能工作却导致反复搬运；只用“最坏 $O(n)$”否认均摊 $O(1)$，混淆两种度量；判空只看一个栈会漏掉另一个栈中的元素。

迁移练习：操作 入1,入2,出,入3,出,出 的返回顺序是什么？答案 1、2、3。独立验收：能逐步列出两个栈，并用“每元素最多搬一次”证明均摊复杂度。