面试题9：用两个栈实现队列

从两次反转为何恢复原顺序开始

先预测：依次入队a、b、c后，stack1从底到顶是a、b、c。若把它们逐个弹出并压入stack2，第二个栈从底到顶会变成c、b、a。此时从stack2栈顶弹出，得到的为何恰好是最早进入的a？

栈遵守后进先出，队列遵守先进先出。一次入栈把到达顺序反过来；再把输入栈逐项搬到输出栈，相当于第二次反转，最老元素重新来到可删除的一端。

题目要求用两个栈实现队列，接口名沿用作者源码：appendTail把元素加入队尾，deleteHead删除并返回队头。核心分工可以压缩为两句话：stack1负责压入新元素，stack2负责弹出旧元素；只有stack2为空时，才把stack1中的全部元素搬过去。

两个栈共同表示一条逻辑队列

不要把两个栈理解成两条独立队列。任意时刻，逻辑队列从头到尾的顺序是：先按stack2从顶到底读取旧元素，再按stack1从底到顶读取新元素。输出栈保存等待优先离开的前缀，输入栈保存后来到达的后缀。

例如首次转移后stack2还有b、c等待弹出，此时新元素d进入stack1。正确队列顺序是b、c、d。若立即把d搬到非空输出栈，它会压在b上方并提前离开，破坏先进先出；所以“输出栈为空才搬运”不是性能技巧，而是正确性条件。

这个可以写成：stack2中的所有元素都早于stack1中的所有元素；stack2非空时，其栈顶就是队头。appendTail只在较新的后缀末端加入元素，不破坏顺序；deleteHead要么删除已有队头，要么先把整个后缀反转成新的前缀再删除。

测试不变量时，可以在调试版本中把两个栈复制出来，按“输出栈顶到底、输入栈底到顶”的顺序生成逻辑快照，并与标准库队列逐步对照。每次随机操作后两者的长度、队头和完整序列都应相同。

忠实实现接口，同时修正源码风险

作者的CQueue<T>使用两个std::stack<T>成员。appendTail直接压入stack1；deleteHead先在stack2为空时转移，再检查两个栈是否都空，最后从stack2取出队头。这是原题必须掌握的结构。

下面实现保留同一契约，但修正两个 C++ 细节：转移时先把栈顶值复制或移动到临时对象，再弹出源栈；空队列抛出异常对象而不是new exception得到的指针。

#include <stack>
#include <stdexcept>
#include <utility>
 
template <class T>
class CQueue {
public:
    void appendTail(const T& value) {
        stack1_.push(value);
    }
 
    void appendTail(T&& value) {
        stack1_.push(std::move(value));
    }
 
    T deleteHead() {
        moveIfNeeded();
        if (stack2_.empty()) {
            throw std::underflow_error("queue is empty");
        }
 
        T head = std::move(stack2_.top());
        stack2_.pop();
        return head;
    }
 
    bool empty() const noexcept {
        return stack1_.empty() && stack2_.empty();
    }
 
private:
    void moveIfNeeded() {
        if (!stack2_.empty()) return;
        while (!stack1_.empty()) {
            T value = std::move(stack1_.top());
            stack1_.pop();
            stack2_.push(std::move(value));
        }
    }
 
    std::stack<T> stack1_;
    std::stack<T> stack2_;
};

作者仓库的Queue.h先写T& data = stack1.top()，随后pop，最后才push(data)。pop之后该引用已经失效，再读取它属于未定义行为；安全顺序必须是先构造独立临时值，再删除源栈顶。源码还使用throw new exception(...)，这会抛指针、增加泄漏与捕获类型错配风险，现代 C++ 应按值抛出具体异常。

为什么单次最坏线性，摊还仍为常数

若stack2为空且stack1中有k个元素，一次deleteHead要做k次跨栈搬运，单次最坏时间是O(k)，不能声称每一次出队都严格O(1)。但观察一串操作，每个元素只经历固定生命周期：压入stack1一次，最多从stack1弹出一次、压入stack2一次，最后从stack2弹出一次。

假设一共入队m个元素。无论入队和出队如何交错，所有搬运次数加起来至多m，因为元素一旦进入stack2就不会返回stack1。所有栈操作总数至多约4m，再加每次调用的常数判断，因此任意q次合法操作的总代价是O(q)，平均到每次就是。

这不是“平均输入下大概很快”。摊还分析不需要随机分布，对最不利的合法操作序列也成立。一次昂贵搬运之所以能被支付，是因为被搬的每个元素此前只做过便宜入队，之后也不会再次搬运。

也可以用理解同一结论：把stack1中的元素个数乘以2作为势能。一次入队的实际代价为1，势能增加2，可把摊还代价记为3；搬运k个元素虽然实际代价约为2k，但势能同时下降2k，昂贵工作被此前积累的势能抵消。输出栈普通弹出实际代价为1且势能不变。势能始终非负，因此任意操作前缀的实际总代价都不会超过累计摊还预算。

聚合法按元素数总账，势能法按状态余额记账，两者证明的是同一个最坏序列保证。面试中任选一种讲清即可；若只说“多数出队很快”，没有说明一个元素不会被反复搬运，就还没有完成摊还证明。

空间方面，两个栈合计恰好保存当前队列中的n个元素，辅助存储为O(n)；搬运期间临时值只占O(1)额外空间。不能把两个栈分别写成O(n)后误算成更高数量级，常数2在渐进复杂度中仍是O(n)。

官方交错序列验证了什么

作者测试先入队a、b、c，连续删除得到a、b；接着入队d，删除必须仍得到旧元素c；再入队e，最后依次得到d、e。输出总序列是a、b、c、d、e。

关键断言是“入队d后仍先返回c”。此时stack2还保存c，d只在stack1中等待。它直接覆盖了最常见错误：每次出队都无条件转移，或新入队就转移到非空输出栈。

#include <cassert>
 
void testOfficialSequence() {
    CQueue<char> queue;
    queue.appendTail('a');
    queue.appendTail('b');
    queue.appendTail('c');
 
    assert(queue.deleteHead() == 'a');
    assert(queue.deleteHead() == 'b');
 
    queue.appendTail('d');
    assert(queue.deleteHead() == 'c');
 
    queue.appendTail('e');
    assert(queue.deleteHead() == 'd');
    assert(queue.deleteHead() == 'e');
    assert(queue.empty());
}
 
void testEmptyQueue() {
    CQueue<int> queue;
    try {
        (void)queue.deleteHead();
        assert(false);
    } catch (const std::underflow_error&) {
        assert(true);
    }
}

官方序列没有调用空队列删除，工程测试必须补上；还应覆盖只入队不出队、单元素反复进出、大批量搬运、可移动但不可复制类型，以及异常路径后队列是否仍可使用。测试不仅比较输出值，也要检查empty与元素数量等可观察状态。

异常安全与只可移动类型

appendTail若在分配内存或构造元素时抛异常，标准容器通常保持原状态，队列仍有效。跨栈搬运更复杂：若T的移动构造可能抛异常，已有若干元素可能已进入stack2，而当前元素是否仍留在stack1取决于类型保证。面试基本题通常忽略这层，但通用库要明确类型约束或设计恢复策略。

最简单的稳健契约是要求T可无异常移动，或在移动可能抛出且复制可用时优先复制。若必须给任意用户类型提供强异常保证，可以先搬到临时容器，全部成功后再提交状态，但实现和额外空间都会增加。算法正确性与泛型异常安全是两个层次，不能因为字符测试通过就默认模板适用于所有T。

TypeScript 数组版没有悬空引用问题，但仍要区分“空数组”与“元素值为undefined”。若泛型允许undefined，不能用pop() === undefined判定空队列；应先检查length。

class TwoStackQueue<T> {
  private readonly stack1: T[] = [];
  private readonly stack2: T[] = [];
 
  appendTail(value: T): void {
    this.stack1.push(value);
  }
 
  deleteHead(): T {
    if (this.stack2.length === 0) {
      while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop() as T);
      }
    }
    if (this.stack2.length === 0) {
      throw new RangeError("queue is empty");
    }
    return this.stack2.pop() as T;
  }
}

接口语义要先于微优化

空队列删除可以抛异常、返回optional<T>，或提供bool tryDeleteHead(T&)；关键是接口必须区分“没有元素”和“元素本身等于某个默认值”。返回0或空字符串会把合法数据与失败混为一谈。

若增加front操作，它应复用“输出栈为空才搬运”的准备逻辑，但只读stack2.top()而不弹出。size等于两个栈大小之和。clear要同时清空两个栈。每个扩展操作都必须维护同一表示不变量，不能绕开状态规则直接操作其中一个容器。

实时系统还要注意摊还O(1)不代表延迟上界为常数；第一次出队可能搬运大量元素。若单次延迟必须稳定，可以采用链式队列、环形缓冲区，或把反转工作增量化。面试答案应准确说“总吞吐有摊还保证”，不要把它扩大成硬实时保证。

本章练习

本章回顾

1. 用两个栈实现队列依靠两次后进先出反转恢复先进先出顺序。
2. stack1负责压入新元素，stack2负责弹出旧元素。
3. stack2非空时绝不能搬运stack1，否则新元素会越过仍待删除的旧元素。
4. 单次出队最坏可能为O(n)，但每个元素最多搬运一次，所以摊还O(1)。
5. 两个栈合计保存n个元素，空间复杂度为O(n)。
6. 空队列必须通过异常或显式结果表达，不能读取空栈顶。
7. C++ 转移要先保存值再pop，异常应按值抛出而不是抛裸指针。
8. 双栈结构本身不提供线程安全或严格常数延迟，这些都需要额外设计。

名词解释