Queue 接口中的 peek() 方法

Question

The remove() and poll() methods remove and return the head of the queue.

The element() and peek() methods return, but do not remove, the head of the queue.

从第二点开始，它说方法 peek() returns 队列的头元素那么为什么在下面的程序中它没有 returning 队列的头元素？

public class PQ {

public static void main(String[] args) {
    PriorityQueue<String> pq = new PriorityQueue<String>();
    pq.add("carrot"); 
    pq.add("apple"); 
    pq.add("banana");
    System.out.println(pq.poll() + ":" + pq.peek()); // prints apple and banana rather than apple and apple
}
}

一旦第一个元素（胡萝卜）被移除，苹果就成为队列的头部（根据队列中的 FIFO）所以 peek() 方法应该 return 苹果对吗？

示例 2：

public class PQ {

public static void main(String[] args) {
    PriorityQueue<String> pq = new PriorityQueue<String>();
    pq.add("carrot"); 
    pq.add("apple"); 
    pq.add("banana");
    System.out.println(pq); // prints [apple, carrot, banana] -> it should be [apple, banana, carrot] right? if it is following natural sorting order
}
}

Answer 1

因为你先轮询

System.out.println(pq.poll() + ":" + pq.peek());

因为它是一个优先队列元素存储为

carrot -> banana -> apple

当您 poll() 时，您会得到 apple 并从队列中移除。在哪个队列头之后是 banana 这正是你在 peek().

时得到的

please look at the example 2 in updated question. Sorting is strange

出乎你的意料。你可以看到 documentation

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

如果你阅读 java 优先级队列使用的优先级堆数据结构，你会更好地理解这一点。您应该使用 poll(), peek() 方法来获取有序数据。

Answer 2

您使用的是 PriorityQueue 而不是 java.util.Queue（常规队列） PriorityQueue 根据 Comparable::compareTo() 方法的实现对元素进行排序，这是 String.class 的自然排序（字母顺序）。

因此，队列中的元素将是 apple-banana-carrot。输出符合预期

Answer 3

你已经通过引用文档自己回答了这个问题。

您的优先队列包含

apple, banana, carrot

poll returns "apple" 然后删除它。所以队列现在

banana, carrot

peek 然后 returns "banana"

Answer 4

POLL() 方法将从队列中删除该元素，并将 return 元素移至调用方法。 PEEK() 方法只会 return 该元素。参考这个POLL()和PEEK()方法的实现代码：

public E poll() {
        if (this.size == 0)
            return null;
        int i = --this.size;
        this.modCount += 1;
        Object localObject1 = this.queue[0];
        Object localObject2 = this.queue[i];
        this.queue[i] = null; 
        if (i != 0)
            siftDown(0, localObject2);
        return localObject1;
}

public E peek() {
        return ((this.size == 0) ? null : this.queue[0]);
}

Answer 5

Queue 接口定义了一些作用于列表第一个元素的方法，它们的行为方式不同。这些方法是：

peek()
element()
poll()
remove()

peek() 此方法检索队列第一个元素的值，而不将其从队列中移除。对于方法的每次调用，我们总是得到相同的值，并且它的执行不会影响队列的大小。如果队列为空，则 peek() 方法 returns null.

element() 此方法的行为类似于 peek()，因此它再次检索第一个元素的值而不删除它。然而，与 peek 不同的是，如果列表为空，则 element() 会抛出 NoSuchElementException。

poll() 此方法通过从队列中移除队列的第一个元素来检索它的值。 .在每次调用时，它都会删除列表的第一个元素，如果列表已经为空，它会 returns null 但不会抛出任何异常。

remove() 此方法的行为与 poll() 方法相同，因此它删除列表的第一个元素，如果列表为空，则抛出 NoSuchElementException

Queue 接口中的 peek() 方法

peek() method in Queue interface

java

scjp