Java：优先队列队列结果和自然排序

Question

我知道，队列按照先进先出（FIFO）的顺序进行操作，但我不确定为什么以下Java示例程序会产生以下输出：

Java示例代码

  public static void main(String args[]) {
            Queue<String> q = new PriorityQueue<String>();
            q.add("3");
            q.add("1");
            q.add("2");

            Iterator<String> itr = q.iterator();
            while (itr.hasNext()) {
                System.out.println(itr.next() + "    ");
            }
}

输出：

1    
3    
2   

根据Java文档中java.util.PriorityQueue.PriorityQueue()的说明：

Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.

• Q1) 请问有人能解释一下为什么输出是1 3 2，以及自然顺序是如何起作用的吗？

• Q2) 我已经查过自然排序以及它与Comparable/Comparor的关系，但它们不仅仅是用于升序或降序排列吗？

- Arun Kumar

---

我无法再现。 - awksp

抱歉！最初的示例是使用 LinkedList。现在已经更新了Java示例，改用 PriorityQueue。 - Arun Kumar

Answer 1

Java中的PriorityQueue是一种数据结构，可以对其包含的元素进行排序。摘自Javadoc：

“优先级队列的元素按照它们的自然顺序排序，或者根据提供给队列构造函数的比较器进行排序，具体取决于使用哪个构造函数。”

无序输出的问题来自于迭代器实现。另一段摘自iterator()方法的代码：

“返回一个迭代器，该迭代器遍历此队列中的元素。该迭代器不以任何特定顺序返回元素。”

因此，迭代器不会按固定顺序返回元素。如果您在循环中使用poll()方法，则会按升序获取所有给定的元素。

如果您需要FIFO方面的队列，可以查看LinkedList并仅使用addFirst()和getLast()方法。

- Christoph Schubert

---

有点奇怪！Iterator在遍历ArrayList时返回相同的顺序，但对于PriorityQueue却不是这样 :( - Arun Kumar

是的，非常不直观。JavaDoc 中的另一个提示：您可以使用 Arrays.sort(q.toArray()) 来获得一个带有元素的有序数组。 - Christoph Schubert

在这里更新一下，即使您使用了 q.toArray() ，它也会返回具有自然顺序的 Object[]。因此，在这里不需要额外使用 Arrays.sort 方法。 - Arun Kumar

保证吗？JavaDoc指出“返回一个包含此队列中所有元素的数组。这些元素没有特定的顺序。”也许你的值是“偶然”排列正确的？ - Christoph Schubert

是的！我刚刚执行了以下测试并遍历了对象数组，它以排序方式返回元素 Object[] ob=(Object[]) q.toArray(); for(int i=0;i<q.size();i++) System.out.println(ob[i]); - Arun Kumar

嗯，看起来这个例子可以工作。根据内部实现，这可能会因为其他值或者在同一次运行中使用相同的值而发生变化。我怀疑他们是否忘记更新JavaDoc。我不会依赖于toArray()方法的顺序。 - Christoph Schubert