C++中队列与栈的std::swap：复制元素还是交换底层地址？

我正在学习队列和栈，现在做练习用其中一种实现另一种（比如用队列实现栈、用栈实现队列）。目前我用两个容器来实现，写push()函数时，每次操作后一个容器有元素另一个为空，所以需要在push()末尾交换两者，统一后续操作的容器。

我现在是通过指针p1、p2的指向交换来实现的，但全程用指针有点麻烦。想知道用std::swap()函数交换队列/栈时，是复制每个元素，还是仅交换底层地址？如果std::swap是交换地址的话，我就可以改用它简化代码，尤其是大型项目里能提升效率。

我的相关代码如下：

private:
    queue<int> q1, q2;
    queue<int>* p1 = &q1;
    queue<int>* p2 = &q2;
public:
    MyStack() {
        //constructor
    }
    
    void push(int x) {
        (*p2).push(x);
        while(!(*p1).empty())
        {
            (*p2).push((*p1).front());
            (*p1).pop();
        }

        //swap
        queue<int>* temp = p1;
        p1 = p2;
        p2 = temp;

    }

解答 #

首先明确：std::swap对于STL容器（包括std::queue、std::stack）的实现是O(1)时间复杂度的，仅交换容器底层的内部数据结构指针/句柄，不会复制任何元素。

原因是STL标准要求所有容器的swap操作必须高效，以std::queue为例，它默认底层容器是std::deque，而std::deque的swap仅交换内部缓冲区指针、大小和容量等元数据，不会移动或复制元素。std::queue作为适配器，其swap会直接调用底层容器的swap，因此整个过程是O(1)的，没有元素复制开销。

回到你的代码，完全可以用std::swap替代指针交换逻辑，不用维护额外指针变量，代码更简洁：

修改后的代码示例：

private:
    queue<int> q1, q2;
public:
    MyStack() {
        //constructor
    }
    
    void push(int x) {
        q2.push(x);
        while(!q1.empty())
        {
            q2.push(q1.front());
            q1.pop();
        }

        // 直接交换两个队列，O(1)操作
        std::swap(q1, q2);
    }

这样每次push后，q1始终是存储所有元素的队列，q2为空，后续的pop、top等操作直接操作q1即可，完全不需要指针，代码可读性和维护性更好，效率和你用指针交换的方式一致，都是O(1)的交换开销。

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