Error in using Stacks to implement Queue (JAVA)

Question

I encountered an strange problem when I used Stacks to implement Queue. Could anyone give me an idea? When I wrote the code like this, it was wrong. Because if I create a object of MyQueue, and then push(1) push(2) pop, it will return 1. However it should be 2.

class MyQueue {
Stack<Integer> s1=new Stack<Integer>();
Stack<Integer> s2=new Stack<Integer>();
// Push element x to the back of queue.
public void push(int x) {
    s1.push(x);
}

// Removes the element from in front of queue.
public void pop() {
    if(s2.size()!=0)
        s2.pop();
    else{
        for(int i = 0; i<s1.size(); i++){
            s2.push(s1.pop());                
        }
        s2.pop();
    }
}
}

But if I modify the code like below, it is correct, but I cannot find the difference between these two classes.

class MyQueue {
Stack<Integer> s1=new Stack<Integer>();
Stack<Integer> s2=new Stack<Integer>();
// Push element x to the back of queue.
public void push(int x) {
    s1.push(x);
}

// Removes the element from in front of queue.
public void pop() {
    if(!s2.empty())
        s2.pop();
    else{
        while(!s1.empty())
            s2.push(s1.pop());                
        s2.pop();
    }
}
}

Thanks very much!

MartinS · Accepted Answer · 2016-03-05 01:56:57Z

2

The problem is that in your for loop you increment i while at the same time s1.size() is decreasing. Imagine s1 has 5 elements at the beginning.

iteration: i = 0, s1.size() = 5
iteration: i = 1, s1.size() = 4
iteration: i = 2, s1.size() = 3
iteration: i = 3, s1.size() = 2

The loop will stop because i < s1.size() is now false even though there are still elements in s1.

answered Mar 5, 2016 at 1:56

MartinS

2,8201 gold badge17 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Darshan Mehta · Accepted Answer · 2016-03-05 01:58:03Z

1

The problem is for loop in the first example:

for(int i = 0; i<s1.size(); i++){
      s2.push(s1.pop());                
}

Let's say the size of s1 is 2 once we push two elements. Now, after first iteration, one element is popped from s1 and hence, size becomes 1. As the breaking condition is i < s1.size() (i is 1 after first iteration), it breaks out of loop and one element is left in s1.

Second example uses while loop and hence, no such condition arises.

Also, I would recommend changing return type of pop method to int.

answered Mar 5, 2016 at 1:58

Darshan Mehta

31k14 gold badges75 silver badges111 bronze badges

Comments

ale64bit · Accepted Answer · 2016-03-05 01:58:36Z

1

This

for(int i = 0; i<s1.size(); i++){
  s2.push(s1.pop());                
}

is not equivalent to

while(!s1.empty())
  s2.push(s1.pop());

Note that s1.size() changes in every iteration, so you will end up terminating the loop before all elements were pop out of s1. For example, suppose you have a stack with 4 elements (1, 2, 3 and 4). Then these are the values of i, s1.size() and the stack elements themselves at the beginning of each iteration:

i s1.size() stack
0         4 1,2,3,4
1         3 1,2,3
2         2 1,2 // here the loop stops

answered Mar 5, 2016 at 1:58

ale64bit

6,2723 gold badges27 silver badges46 bronze badges

Collectives™ on Stack Overflow

Error in using Stacks to implement Queue (JAVA)

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related