Java堆栈/队列问题 [英] java stack/queue problem

问题描述

Java的新手，并在下面尝试堆栈问题.如果可能的话，宁可回答我的问题，也不愿解决，因为我会一直遇到同样的问题，希望这是有意义的；

编写一个方法重新排序，该方法将整数队列作为参数，并假定整数已按绝对值排序，然后将整数按已排序(不减)的顺序放置.例如，假设一个名为q的变量存储以下值序列:

前[1、2，-2、4，-5、8，-8、12，-15、23]后

请注意，如果您忽略数字的符号，则这些值将按排序顺序显示.重新排序的调用(q)；应该重新排列值，以便队列存储以下值序列:

前[-15，-8，-5，-2、1、2、4、8、12、23]返回

请注意，现在考虑到数字的符号，这些值以已排序的顺序显示.您可以使用一个堆栈作为辅助存储来解决此问题.

这是我的代码(不是最好的，甚至不是正确的...)；

Hi,
New to java and trying a stack problem below. Rather have the answer to my question than a solution if possible because I''ll keep having the same problem, hope it makes sense;

Write a method reorder that takes a queue of integers as a parameter and that puts the integers into sorted (nondecreasing) order assuming that the queue is already sorted by absolute value. For example, suppose that a variable called q stores the following sequence of values:

front [1, 2, -2, 4, -5, 8, -8, 12, -15, 23] back

Notice that the values appear in sorted order if you ignore the sign of the numbers. The call of reorder(q); should reorder the values so that the queue stores this sequence of values:

front [-15, -8, -5, -2, 1, 2, 4, 8, 12, 23] back

Notice that the values now appear in sorted order taking into account the sign of the numbers. You may use one stack as auxiliary storage to solve this problem.

This is my code (not the best or even correct but....);

import java.util.Queue;
import java.util.Stack;

public class Reorder {
	public static void main(args[] String) {
	}

	public static void reorder2(Queue<integer> q) {

		Stack<integer> s = new Stack<integer>();

		for (int i = 0; i < q.size(); i++) {
			int smaller = q.remove();
			if (smaller < q.remove()) {
				s.push(smaller);
			}
			q.add(q.remove());
			if (smaller > q.remove()) {
				s.push(q.remove());
			}
			q.add(smaller);
		}

		while (!s.isEmpty()) {
			q.add(s.pop());
		}

	}

}

正确的结果是； [-15，-8，-5，-2、1、2、4、8、12、23]
我的结果是[1，-5，-15，-8，-2，-8]
2、4、8、12、23发生了什么?这些数字应加回到队列中，并与q.remove()比较.然后，应该将它们最终添加到堆栈中，但是它们会以某种方式消失！?
谢谢

Correct result is; [-15, -8, -5, -2, 1, 2, 4, 8, 12, 23]
My results is [1, -5, -15, -8, -2, -8]
What happened to 2, 4, 8, 12, 23? These numbers should be added back to the queue and compared with q.remove(). Then they should be added to stack eventually but they disappear somehow!?
Thanks

推荐答案

我将向您展示第一个错误；然后您将对其进行修复，然后执行其余的操作，好吗?

错误是:显然，在for (int i = 0; i < q.size(); i++) { ... }的循环中，您想重复循环，其时间等于队列的大小.这不会发生，因为条件i < q.size()在每次迭代中都会求值，但是您要删除元素.假设您有10个元素，并在每次迭代中都删除一个元素.在6次迭代后，i变为5，队列中仍有4个元素，并且由于满足条件，循环结束.您需要具备:

I''ll show your the first mistake; and you will fix it and do the rest, OK?

The mistake is: apparently, in the loop for for (int i = 0; i < q.size(); i++) { ... } you wanted to repeat the cycle the number of time equal to the size of the queue. It does not happen, because the condition i < q.size() is evaluated in each iteration, but you remove elements. Suppose you have 10 elements and remove an element in each iteration. After 6 iterations i becomes 5, 4 elements are still in the queue, and the loop ends because the condition is satisfied. You need to have:

int queueSize = q.size(); 
for (int i = 0; i < queueSize; i++) {

...

}

即使看起来等效，也不是一样–行为会大不相同.

—SA

Even though it looks equivalent, it is not — the behavior will be very different.

—SA

这篇关于Java堆栈/队列问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！