java - 为什么我的代码出队无法正常工作？

Question

我已经为使用两个堆栈的队列编写了代码。但是代码的出队部分表现得很奇怪，它正确地删除了测试中的第一个元素，但第二个和第三个元素的顺序错误。

这是出列代码，我正在使用:

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();
}

这是测试用例代码，它给出了 51 和 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());
}

我无法理解为什么会发生这样的事情。如果有人能告诉我代码出了什么问题，我将不胜感激。

Answer 1

原因是您在第二次调用 dequeue 时对 s1 进行了重新排序。

这在下面解释，

初始状态:

s1 : 86 -> 51 -> 42

第一次出列:

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

第二次出队:

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

解决此问题的正确方法是不要将 s1 与 s2 交换，而是等待 s2 中的所有元素完成，然后用 s1 重新填充 s2。我没有添加实现，因为它已经在 mangusta 的其他答案中完成了。