队列反转的渐近分析：时间复杂度求解问询

嘿，别担心，你的初步猜测有点偏差，我们来一步步拆解这个问题！

首先先看你给出的反转队列的代码：

void reverseQueue(queue<int>& Queue) {
    stack<int> Stack;
    while (!Queue.empty()) {
        Stack.push(Queue.front());
        Queue.pop();
    }
    while (!Stack.empty()) {
        Queue.push(Stack.top());
        Stack.pop();
    }
}

核心复杂度分析 #

这个函数的时间复杂度是Θ(n)（同时也是O(n)），绝对不是O(n²)，原因如下：

• 第一个while循环：我们把队列里的n个元素逐个取出（Queue.front() + Queue.pop()），再压入栈（Stack.push()）。每个队列/栈的基本操作（出队、入队、压栈、弹栈）都是**O(1)**的常数时间操作，这个循环总共执行n次，所以总时间是O(n)。
• 第二个while循环：把栈里的n个元素逐个弹出（Stack.top() + Stack.pop()），再放回队列（Queue.push()）。同样，每个操作都是O(1)，循环执行n次，总时间也是O(n)。

把两个循环的时间加起来，就是O(n) + O(n) = O(n)。因为我们能确定这个操作的上下界都是线性的，所以用Θ(n)来描述更准确——它的运行时间和元素数量n是严格线性相关的。

为什么你会误以为是O(n²)？ #

可能是混淆了“两次遍历”和“嵌套遍历”的区别：O(n²)通常出现在嵌套循环（比如一个循环里套另一个循环，总共执行n*n次操作）的场景，但这里是两个独立的线性循环，并没有嵌套，所以总操作次数是2n，属于线性复杂度范畴。

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