使用两个队列实现栈时push方法异常问题排查

背景 #

已有功能正常的queueUsingLL队列类，提供以下方法：

• isEmpty()：返回队列是否为空
• size()：返回队列长度
• enqueue(int element)：在队尾添加元素
• dequeue()：移除并返回队头元素

基于该类实现栈时，push方法存在逻辑错误，导致输出不符合预期。

问题现象 #

执行以下驱动代码时，预期输出为1 2 3 4 5，实际输出为1 2 1 2 1：

int main(){
    int arr[] = {1,2,3,4,5};
    StackUsingTwoQueues s;

    for(int i = 0; i < 5; i++){
        s.push(arr[i]);
        cout<<s.top()<<" ";
    }cout<<endl;
}

有问题的push方法 #

void push(int element){
    if(q.isEmpty()){
        q.enqueue(element);
    }
    else{
        for(int i = 0; i < q.size(); i++){
            tempQ.enqueue(q.dequeue());
        }
        q.enqueue(element);
        for(int i = 0; i < tempQ.size(); i++){
            q.enqueue(tempQ.dequeue());
        }
    }
}

可正常运行的push方法（while循环实现） #

void push(int element){
    while(!q.isEmpty()){
        tempQ.enqueue(q.dequeue());
    }
    q.enqueue(element);
    while(!tempQ.isEmpty()){
        q.enqueue(tempQ.dequeue());
    }
}

问题原因 #

问题出在for循环的终止条件依赖q.size()：
每次调用q.dequeue()时，队列q的长度会实时减少。以第三次push元素3为例：

1. 此时q中已有元素[2, 1]，q.size()初始为2
2. 第一次循环i=0：执行q.dequeue()取出2放入tempQ，q的size变为1
3. i自增到1，此时i < q.size()即1 < 1不成立，循环直接终止
4. 这导致q中剩余的元素1并未被移到tempQ中，后续加入新元素3后，再把tempQ中的2移回q，最终q中的元素顺序为[1, 3, 2]，栈的top元素变为1，与预期的3不符

而while循环通过!q.isEmpty()作为终止条件，只要队列不为空就持续转移元素，能确保q中的所有元素都被移到tempQ，不会出现遗漏，因此逻辑正确。

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