C++ 第49题：双栈实现一个先进先出（FIFO）模拟队列

题目

编写程序，使用两个后进先出（LIFO）的 std::stack：输入栈 inStack 与输出栈 outStack，模拟设计一个功能完备的先进先出（FIFO）队列 MyQueue。实现 push、pop、peek 与 empty 接口，并采用严格的摊还分析（Amortized Analysis）证明每个入队和出队操作的均摊时间复杂度为 O(1)。

输入格式：无需外部输入。

输出格式：输出入队、出队、偷窥栈顶及判空的执行日志。

数据范围与约定：经典数据结构模拟与均摊复杂度分析。

思路与算法

1. 负负得正的拓扑逆转
将元素压入一个栈会使其倒序，再弹出并压入第二个栈则恢复正序！通过两次 LIFO 的翻转，成功合成 FIFO 队列。

2. 惰性搬迁策略
切忌每次 pop 都把数据在两栈之间来回倒腾！正确做法：push 时永远直接压入 inStack；pop/peek 时只检查 outStack：若 outStack 非空直接出栈；唯有当 outStack 为空时，才一次性把 inStack 中的所有元素倾倒倒入 outStack。

3. 均摊 O(1) 证明
每个元素一生中：在 inStack 进出各 1 次，在 outStack 进出各 1 次，总共最多经历 4 次常数级操作，因此均摊耗时严格为 O(1)。

完整程序

#include <iostream>
#include <stack>
#include <stdexcept>

class MyQueue {
private:
    std::stack<int> inStack;
    std::stack<int> outStack;

    // 内部私有辅助：按需将 inStack 倾倒至 outStack
    void transferIfEmpty() {
        if (outStack.empty()) {
            while (!inStack.empty()) {
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
    }

public:
    void push(int x) {
        inStack.push(x);
    }

    int pop() {
        if (empty()) throw std::runtime_error("队列为空，无法执行出队！");
        transferIfEmpty();
        int frontVal = outStack.top();
        outStack.pop();
        return frontVal;
    }

    int peek() {
        if (empty()) throw std::runtime_error("队列为空，无头部元素！");
        transferIfEmpty();
        return outStack.top();
    }

    bool empty() const {
        return inStack.empty() && outStack.empty();
    }
};

int main() {
    MyQueue q;

    std::cout << "入队: 10, 20, 30\n";
    q.push(10);
    q.push(20);
    q.push(30);

    std::cout << "队首元素 (peek): " << q.peek() << "\n";
    std::cout << "出队元素 (pop) : " << q.pop() << "\n";

    std::cout << "追加新元素入队: 40\n";
    q.push(40);

    std::cout << "连续出队剩余全部元素:\n";
    while (!q.empty()) {
        std::cout << q.pop() << " ";
    }
    std::cout << "\n";

    return 0;
}

运行示例

输出：

入队: 10, 20, 30
队首元素 (peek): 10
出队元素 (pop) : 10
追加新元素入队: 40
连续出队剩余全部元素:
20 30 40