Java : PriorityQueue queue results and natural ordering

Question

I know, queue follow FIFO(First in first out) order, but I am not sure why the following output appears with below java sample program

JAVA Sample

  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() + "    ");
            }
}

OUTPUT :

1    
3    
2   

As per Java doc of java.util.PriorityQueue.PriorityQueue()

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

• Q1) Could any body please explain why the output is 1 3 2 and how the natural order works here.

• Q2) I have checked about natural ordering and its related to the Comparable/Comparor but doesn't they are for Sorting(Ascending/Descending) Order only??

Answer 1

The PriorityQueue in Java is a datastructure, that sorts the elements it contains. Excerpt from the Javadoc:

The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.

The Problem with the unordered output comes from the iterator implementation. Another excerpt, this time from the iterator() method:

Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.

So you don't java a fixed order with the iterator. If you use the poll() method in a loop you would get all given elements in ascending order.

If you are looking for a Queue in the FIFO-sense you may have a look at the LinkedList and only use the addFirst() and getLast() methods.

Answer 2

The PriorityQueue in Java is a datastructure, that sorts the elements it contains. Excerpt from the Javadoc:

The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.

The Problem with the unordered output comes from the iterator implementation. Another excerpt, this time from the iterator() method:

Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.

So you don't java a fixed order with the iterator. If you use the poll() method in a loop you would get all given elements in ascending order.

If you are looking for a Queue in the FIFO-sense you may have a look at the LinkedList and only use the addFirst() and getLast() methods.