队列没有自然排序

Question

可能重复:
为什么这个奇怪的顺序发生在java的PriorityQueue中？

请看下面的代码:

public static void main(String[] args) {
    Queue<String> q = new PriorityQueue<String>();
    q.offer("car");
    q.offer("airplane");
    q.offer("bicycle");
    Iterator<String> i = q.iterator();
    while(i.hasNext())
        System.out.print(i.next() + " ");
}

有人可以解释为什么输出

airplane car bicycle

代替

airplane bicycle car

？

因为在API中它表示优先级队列的元素是根据它们的自然顺序排序的.

Answer 1

根据迭代器的javadoc:

迭代器不会以任何特定顺序返回元素.

但是,第一项(头部)保证是最小的.所以这应该打印你期望的:

public static void main(String[] args) throws Exception {
    Queue<String> q = new PriorityQueue<String>();
    q.offer("car");
    q.offer("airplane");
    q.offer("bicycle");
    String e = null;
    while ((e = q.poll()) != null) {
        System.out.println(e);
    }
}

如果要对迭代进行排序,则需要使用不同的结构,例如,TreeSet如果没有重复项,则需要使用不同的结构.