LeetCode 225：双队列实现栈的代码问题排查与疑问解答

问题场景 #

LeetCode第225题要求仅用两个队列实现后进先出（LIFO）的栈，支持push、top、pop、empty四个核心方法。你编写的C#代码在测试用例["MyStack","push","push","top","pop","pop","empty"]（参数[[],[1],[2],[],[],[],[]]）下，实际输出为[null,null,null,2,2,1,false]，与预期的[null,null,null,2,2,1,true]不符，且对连续pop的执行逻辑存在疑问。

你的代码 #

public class MyStack {

    Queue<int> firstQ = new Queue<int>();
    Queue<int> secondQ = new Queue<int>();
    public MyStack() {
        
    }
    
    public void Push(int x) {
        firstQ.Enqueue(x);
    }
    
    public int Pop() {
        if (firstQ.Count > 0)
        {
            MakeTopAlone();
            return firstQ.Dequeue();
        }
        return 1;
        
    }
    
    public int Top() {
        if (firstQ.Count > 0)
        {
            MakeTopAlone();
            return firstQ.Peek();
        }
        return 1;
    }
    
    public bool Empty() {
        bool firstEmpty = firstQ.Count() == 0;
        bool secondEmpty = secondQ.Count() == 0;
        return firstEmpty && secondEmpty;
    }

    public void MakeTopAlone(){
        int length = firstQ.Count;

        for (int i = length; i > 1; i--)
        {
            secondQ.Enqueue(firstQ.Dequeue());
        }
    }
}

问题分析 #

1. empty返回false的原因 #

测试用例的执行流程暴露了核心问题：

• 执行top()时，MakeTopAlone把firstQ中的1移到secondQ，此时firstQ剩[2]，secondQ为[1]；
• 第一次pop()取出2后，firstQ为空，但secondQ仍保留[1]，且代码没有将secondQ的元素移回firstQ；
• 第二次pop()时，firstQ为空，代码直接返回1，但secondQ里的1从未被处理，一直留在队列中；
• 最后调用empty()时，secondQ不为空，因此返回false，与预期的true不符。

2. 连续pop的逻辑错误 #

第二次pop时，firstQ已经为空，但secondQ中存储着之前移过去的元素，代码只检查firstQ.Count > 0，完全忽略了secondQ的存在，导致既没有正确取出1，也没有清理secondQ的元素，最终影响empty的判断。

修复方案 #

核心思路是每次执行pop或top后，保证所有元素回到同一个队列中，避免两个队列同时存有元素。同时，处理firstQ为空但secondQ有元素的情况：

public class MyStack {

    Queue<int> firstQ = new Queue<int>();
    Queue<int> secondQ = new Queue<int>();
    
    public MyStack() { }
    
    public void Push(int x) {
        firstQ.Enqueue(x);
    }
    
    public int Pop() {
        // 如果firstQ为空，交换两个队列的角色
        if (firstQ.Count == 0) {
            (firstQ, secondQ) = (secondQ, firstQ);
        }
        MakeTopAlone();
        int val = firstQ.Dequeue();
        // 将secondQ的元素移回firstQ
        while (secondQ.Count > 0) {
            firstQ.Enqueue(secondQ.Dequeue());
        }
        return val;
    }
    
    public int Top() {
        if (firstQ.Count == 0) {
            (firstQ, secondQ) = (secondQ, firstQ);
        }
        MakeTopAlone();
        int val = firstQ.Peek();
        // 将secondQ的元素移回firstQ
        while (secondQ.Count > 0) {
            firstQ.Enqueue(secondQ.Dequeue());
        }
        return val;
    }
    
    public bool Empty() {
        // 直接用队列的Count属性，比LINQ的Count()更高效
        return firstQ.Count == 0 && secondQ.Count == 0;
    }

    public void MakeTopAlone(){
        int length = firstQ.Count;
        for (int i = length; i > 1; i--)
        {
            secondQ.Enqueue(firstQ.Dequeue());
        }
    }
}

修复后，测试用例的执行流程会变为：

1. push(1) → firstQ: [1]
2. push(2) → firstQ: [1,2]
3. top() → MakeTopAlone把1移到secondQ，取2后，将secondQ的1移回firstQ，最终firstQ: [1]，secondQ: []
4. pop() → MakeTopAlone无循环（firstQ只有1），取出1后，firstQ为空，secondQ也为空
5. pop() → 此时firstQ为空，交换队列（secondQ也为空），符合题目假设栈非空时调用pop的场景
6. empty() → 两个队列都为空，返回true

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