Understanding Pop and Push Operation logic of a stack implemented by two queues

Question

I am trying to understand the following method from here explained by Mahmood Akhtar. Please find the code snippet below:

public void push(int data) {

        if (q1.peek() == null) {
            q1.add(data);
        } else {
            for (int i = q1.size(); i > 0; i--) {
                q2.add(q1.remove());
            }
            q1.add(data);
            for (int j = q2.size(); j > 0; j--) {
                q1.add(q2.remove());
            }

        }
    }

Here is what I have understood :

Step 1: The first if statement checks whether queue q1 is null or not and if it's null, then a data is added.

Step 2: Otherwise, since q1 is full, we will have to move the data from q1 to q2. So, the first for loop in the else statement is basically starting from the size of the q1 and runs until the last element is encountered. All the elements are moved into q2. A new data is added into q1.

Step 3: Same process like Step 2 is repeated for q2.

Please correct me if my explanation is correct or not?

SECOND QUESTION:

In the pop method :

public int pop() {
        if (q1.peek() == null) {
            System.out.println("The stack is empty, nothing to return");
            int i = 0;
            return i;
        } else {
            int pop = q1.remove();
            return pop;
        }
    }

How come they are deleting the first element from the queue q1? Because the first element in the queue q1 will be according to the FIFO principle and for stack it should be the last element?

What according to me should he be doing is that , he should be transferring all the elements into q2 from q1 until last element is left and then remove that element from the queue. Please correct me if I am wrong.

Thanks

@DanielImms Do you have an article for stack implementation using queues? I saw the queue implementation using stack in the link. Also, if you can throw some light on my questions, that would be great. Thanks — John, Oct 11 '15 at 03:18

YoungHobbit · Accepted Answer · 2015-10-11T03:26:46.013

Step 2: Otherwise, since q1 is full,

This assumption is wrong. The queue is not full. It just checks that does it contains at least one element. If it contains then, first store them into a separate queue, store the element, store back all the other elements. So it is storing the elements in the revers order.

How come they are deleting the first element from the queue q1?

Because the elements are stored in the reverse order. That is the whole logic in push method.

he should be transferring all the elements into q2 from q1 until last element is left and then remove that element from the queue.

He is doing that only, it is just that you are expecting this to happen in the pop() method, but the code is doing it in push() method.

score -1 · Answer 2 · answered Oct 11 '15 at 03:30

What according to me should he be doing is that , he should be transferring all the elements into q2 from q1 until last element is left and then remove that element from the queue. Please correct me if I am wrong.

And also at the end of pop operation, the role for q1 and q2 are exchanged, so the solution stated would make the algorithm most efficient on popping item

Understanding Pop and Push Operation logic of a stack implemented by two queues

2 Answers2