Why is dequeue not working properly for my code?

user_10870404 0
Viewed 488

I have made a code for a queue using two stacks. But the dequeue part of the code is behaving weirdly, it is removing the first element in the test properly, but second and third elements have wrong order.

This is the dequeue code, I am using:

public T dequeue() throws NoSuchElementException {

while(!s1.isEmpty()){
  T tmp = s1.pop();
  s2.push(tmp);
}

Stack<T> temp = new Stack<>();
temp = s1;
s1 = s2;
s2 = temp;

    return s1.pop();
}

This is the test case code, which is giving reverse order for 51 and 86.

@Test
public void testTwoElement() {
    Queue<Integer> q = new Queue<>();
    q.enqueue(42);
    q.enqueue(51);
    q.enqueue(86);
    assertEquals(3, q.size());
    assertEquals(new Integer(42), q.dequeue());
    assertEquals(new Integer(51), q.dequeue());
    assertEquals(new Integer(86), q.dequeue());
    assertEquals(0,q.size());
    assertEquals(true,q.isEmpty());
}

I am not able to understand the reason, why it is happening like this. I would appreciate if someone can tell me what's going wrong with the code.

stack queue java
2 Answers

Swapping s1 and s2 is unnecessary here. Remove the swapping lines of code and replace return s1.pop(); with return s2.pop();
I assume you always push enqueued element into s1 .
Also, you need to move elements from s1 to s2 only when s2 has nothing to pop. 

public T dequeue() throws NoSuchElementException {

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


    return s2.pop();
}
user_15568200

The reason is that you are re-ordering the s1 when you call dequeue the second time.

This is explained below,

Initial State:

s1 : 86 -> 51 -> 42

First Dequeue:

s1 : 86 -> 51 -> 42

s2 :

empty s1 and add elements to s2:

s1 :

s2 : 42 -> 51 -> 86

Now swap s1 and s2:

s1 : 42 -> 51 -> 86

s2 :

Now pop s1 and return 42:

s1 : 51 -> 86

Second Dequeue:

s1 : 51 -> 86

s2 :

empty s1 and add elements to s2:

s1 :

s2 : 86 -> 51

Now swap s1 and s2:

s1 : 86 -> 51

s2 :

Now pop s1 and return 86:

s1 : 51

The correct way of solving this is to not swap s1 with s2 and to wait for all elements in s2 to finish and then repopulate s2 with s1. I am not adding the implementation as it is already done in other answer by mangusta.

user_74685380
Related