使用两个栈实现队列时调用STL swap()操作出现错误咨询

错误成因 #

问题本质是栈和队列的进出特性差异导致的，具体可以拆解为两点：

1. 双栈倒换后的顺序特性 #

栈是后进先出结构，你在pop操作中将A栈除队首外的元素转移到B栈时，B栈的元素顺序和原A栈剩余元素的顺序是完全逆序的：
以你给出的测试用例场景举例：
执行push(2)、push(3)、push(4)后，A栈从栈底到栈顶的结构为：2 -> 3 -> 4
执行pop操作时，先将4、3依次弹出A并压入B，此时B栈从栈底到栈顶的结构为：4 -> 3

• 如果你执行手动循环倒回A：会依次弹出B的栈顶元素3、4，再压入A，最终A栈结构为3 -> 4，完全符合队列剩余元素的顺序要求
• 如果你直接执行swap(A,B)：A会直接替换为B的内容，也就是结构为4 -> 3，元素顺序完全颠倒，后续操作自然会输出错误结果

2. 为什么双队列实现栈时swap可用 #

队列是先进先出结构，你在双队列实现栈的逻辑中，将元素从一个队列转移到另一个队列时，元素的先后顺序不会发生改变，直接swap交换两个队列的内容也不会破坏顺序要求，所以不会出错。

优化实现建议 #

如果想要减少倒换次数提升效率，可以不用每次操作完都把元素倒回A栈，采用分栈负责的逻辑可以把均摊时间复杂度降到O(1)，参考实现如下：

template<typename T>
class Queue{
    stack<T> in_stack; // 专门负责入队操作
    stack<T> out_stack; // 专门负责出队、取队首操作
public:
    void push(T x){
        in_stack.push(x);
    }
    void pop(){
        if(out_stack.empty()){
            // 仅当出队栈为空时才一次性倒换所有元素
            while(!in_stack.empty()){
                out_stack.push(in_stack.top());
                in_stack.pop();
            }
        }
        if(!out_stack.empty()){
            out_stack.pop();
        }
    }
    T front(){
        if(out_stack.empty()){
            while(!in_stack.empty()){
                out_stack.push(in_stack.top());
                in_stack.pop();
            }
        }
        return out_stack.top();
    }
    int size(){
        return in_stack.size() + out_stack.size();
    }
    bool empty(){
        return size() == 0;
    }
};

内容的提问来源于stack exchange，提问作者Ikshul Dureja