Queue Using Stacks: Transferring Elements Between Stacks for Dequeue, but Not Reverting for Enqueue

Question

I'm learning how to implement queues using two stacks. This is the method where the dequeue operation is costly and enqueue is O(1). Below is the code:-

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
    }
}

Now, when enqueue is called, 5,10,15,20 are pushed to Stack s1. Now, when I call dequeue for the first time, 20,15,10,5 are popped from s1 and pushed to s2. So, at this point,

contents of s1: Empty ,

contents of s2: 20,15,10,5

Now , after pop from s2, 5 is dequeued. But, I never pushed 20,15,10 back to s1. So, I assume that Stack s1 should stay empty after dequeue returns control to main function. Now, when 25 is enqueued, it is pushed to s1.
So, now when I call dequeue, 25 is popped from s1 and pushed to s2. So, at this point,

contents of s1: Empty ,

contents of s2: 25,20,15,10,5

Now, after pop from s2, 25 should be dequeued(according to this incorrect interpretation). But, 10 is dequeued, which is how actually queues should work.

Could you please tell me how is it actually working?

Apologies, if it's a silly doubt.

Answer 1

So, now when I call dequeue, 25 is popped from s1 and pushed to s2.

No. Your mistake is there. When calling dequeue, DO NOT put the elements of s1 onto s2, unless s2 is empty. If s2 is nonempty, then just pop one element from s2.

In fact, in the java code that you've shown, notice this big if inside the code of function dequeue:

if(s2.isEmpty()){
    while(!s1.isEmpty()){
        temp = s1.pop();
        s2.push(temp); 
    }
} 

The while-loop is responsible for popping the elements from s1 and pushing them onto s2, but this while-loop is enclosed inside a big if(s2.isEmpty()): the code that pops the elements from s1 and pushes them to s2 is only executed if s2 is empty. If s1 is nonempty, we jump directly to return s2.pop(); without touching the elements from s1.

This is the method where the dequeue operation is costly and enqueue is O(1).

Actually, the dequeue operation is not always costly. It's only costly when s2 is empty. In fact we say that this operation is amortized O(1) if the queue is used in a context where amortized complexity makes sense.