CODEWITHSUNDEEP
javascjp
kittu
kittu

Reputation: 7018

peek() method in Queue interface

From Java documentation:

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.

From the second point it says method peek() returns head element of queue then how come its not returning head element of queue in the following program?

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
}
}

Once the first element(carrot) is removed, apple becomes the head of queue(according to FIFO in queue) so peek()method should return apple right?

Example2:

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
}
}

Upvotes: 1

Views: 23671

Answers (5)

dinesh kandpal
dinesh kandpal

Reputation: 775

The Queue interface defines some methods for acting on the first element of the list, which differ in the way they behave. These methods are:

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

The peek() This method retrieves the value of the first element of the queue without removing it from the queue. For each invocation of the method we always get the same value and its execution does not affect the size of the queue. If the queue is empty the peek() method returns null.

The element() This method behaves like peek(), so it again retrieves the value of the first element without removing it. Unlike peek ), however, if the list is empty element() throws a NoSuchElementException.

The poll() This method retrieves the value of the first element of the queue by removing it from the queue. . At each invocation it removes the first element of the list and if the list is already empty it returns null but does not throw any exception.

The remove() This method behaves as the poll() method, so it removes the first element of the list and if the list is empty it throws a NoSuchElementException

Upvotes: 2

Aniket Thakur
Aniket Thakur

Reputation: 68975

Because you are polling first

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

As it is a priority queue elements are stored as

carrot -> banana -> apple

When you poll() you get apple and is removed from queue. After which head of queue is banana which is exactly what you get when you peek().

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

It's just what you don't expect. You can see the 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()).

You will understand this better if you read priority heap data structure which java priority queue use. You should use poll(), peek() methods to get ordered data.

Upvotes: 8

nisarg109
nisarg109

Reputation: 204

POLL() method will remove that element from queue and return element to calling method. PEEK() method will only return that element. refer this implementation code of POLL() and PEEK() method:

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]);
}

Upvotes: 2

APD
APD

Reputation: 1519

You have answered the question yourself by quoting the documentation.

Your priority queue contains

apple, banana, carrot

poll returns "apple" then removes it. So the queue is now

banana, carrot

peek then returns "banana"

Upvotes: 2

Balaji Katika
Balaji Katika

Reputation: 3015

You are using PriorityQueue and not java.util.Queue (Regular Queue) PriorityQueue sorts the elements depending on the implementation of the Comparable::compareTo() method which is a natural ordering (alphabetical order) for String.class.

Hence, the elements in your queue would be apple-banana-carrot. The output is as expected

Upvotes: 2

Related Questions