我已经使用两个堆栈为队列编写了代码.但是代码的出队部分表现得很怪异,它正确地删除了测试中的第一个元素,但是第二个和第三个元素的顺序错误.
这是出队代码,我正在使用：
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());
}
我不明白原因,为什么会这样发生.如果有人可以告诉我代码出了什么问题,我将不胜感激.
最佳答案
原因是您在第二次调用出队时正在对s1重新排序.
原文链接：https://www.f2er.com/java/532809.html这在下面解释,
初始状态：
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的其他答案中已经完成了.
