基于双栈实现队列：出队转栈但入队不回退的逻辑疑问

我正在学习用两个栈实现队列，采用入队（enqueue）操作O(1)、出队（dequeue）操作代价较高的方案，对应的Java代码如下：

import java.util.*;
class QueueusingStacks2 {
    Stack<Integer> s1 = new Stack<>();
    Stack<Integer> s2 = new Stack<>();
    
    public void enqueue(int element){
        s1.push(element);
    }

    public int dequeue(){
        int temp;
        if(s1.isEmpty()&&s2.isEmpty()) throw new NoSuchElementException("Queue is empty");
        if(s2.isEmpty()){
            while(!s1.isEmpty()){
                temp = s1.pop();
                s2.push(temp); 
            }
        } 
        if(!s1.isEmpty()) System.out.print(s1.peek()+" "); 
        return s2.pop();
    }
}

class Solution{
    public static void main(String[] args) {
        QueueusingStacks2 q1 = new QueueusingStacks2();
        q1.enqueue(5);
        q1.enqueue(10);
        q1.enqueue(15);
        q1.enqueue(20);
        System.out.println(q1.dequeue()); //5
        q1.enqueue(25);
        System.out.println(q1.dequeue());//10
        System.out.println(q1.dequeue());//15
    }
}

执行过程中产生了困惑：初始调用enqueue将5、10、15、20推入s1后，第一次调用dequeue时，s1的元素全部弹出并推入s2，此时s1为空，s2包含20、15、10、5，弹出5完成出队；随后调用enqueue将25推入s1，再次调用dequeue时，我误以为会将s1的25转移到s2后弹出25，但实际弹出的是10，符合队列先进先出特性。想请教这段代码实际的执行逻辑是怎样的？

核心逻辑拆解 #

这个实现的核心是仅当s2为空时，才将s1的所有元素转移到s2，以此保证s2中的元素始终保持队列的先进先出顺序，以下是逐步骤的执行细节：

步骤1：初始入队操作

调用enqueue(5)、enqueue(10)、enqueue(15)、enqueue(20)后，s1中的元素从上到下为20,15,10,5（栈顶是20），s2为空。

步骤2：第一次调用dequeue

• 检查到s2为空，触发转移逻辑：将s1的元素逐个弹出并推入s2
  • 弹出20推入s2 → s2：[20]，s1：[15,10,5]
  • 弹出15推入s2 → s2：[20,15]，s1：[10,5]
  • 弹出10推入s2 → s2：[20,15,10]，s1：[5]
  • 弹出5推入s2 → s2：[20,15,10,5]，s1为空
• 此时s2的栈顶是5，弹出5并返回，对应第一个输出的5，s2中剩余20,15,10（栈顶是10）

步骤3：入队25

调用enqueue(25)，直接将元素推入s1，此时s1：[25]，s2：[20,15,10]

步骤4：第二次调用dequeue

• 检查到s2不为空，不会触发s1到s2的转移操作
• 直接弹出s2的栈顶元素10并返回，对应第二个输出的10，s2中剩余20,15（栈顶是15）

步骤5：第三次调用dequeue

• s2仍不为空，直接弹出栈顶元素15并返回，对应第三个输出的15

关键规则总结 #

• s1专门接收新入队元素，入队操作直接执行push，保证O(1)时间复杂度
• s2专门负责出队，仅当s2为空时，才将s1的所有元素倒序转移到s2，让s2的栈顶始终是队列的队首元素
• 只要s2还有元素，就不会动s1中的新元素，直到s2被取空，下一次出队时才会再次转移s1的元素，以此兼顾入队效率和队列的先进先出特性

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