Class PriorityQueue and Interface Queue

In Section 17.8, we introduced the queue data structure and created our own implementation of it. In this section we investigate interface Queue and class PriorityQueue in the Java utilities package (java.util). Queue, a new collection interface introduced in J2SE 5.0, extends interface Collection and provides additional operations for inserting, removing and inspecting elements in a queue. PriorityQueue, one of the classes that implements the Queue interface, orders elements by their natural ordering as specified by Comparable elements' compareTo method or by a Comparator object that is supplied through the constructor.

Class PriorityQueue provides functionality that enables insertions in sorted order into the underlying data structure and deletions from the front of the underlying data structure. When adding elements to a PriorityQueue, the elements are inserted in priority order such that the highest-priority element (i.e., the largest value) will be the first element removed from the PriorityQueue.

The common PriorityQueue operations are offer to insert an element at the appropriate location based on priority order, poll to remove the highest-priority element of the priority queue (i.e., the head of the queue), peek to get a reference to the highest-priority element of the priority queue (without removing that element), clear to remove all elements in the priority queue and size to get the number of elements in the priority queue. Figure 19.17 demonstrates the PriorityQueue class.

Figure 19.17. PriorityQueue test program.

(This item is displayed on page 939 in the print version)

 1 // Fig. 19.17: PriorityQueueTest.java
 2 // Standard library class PriorityQueue test program.
 3 import java.util.PriorityQueue;
 4
 5 public class PriorityQueueTest
 6 {
 7 public static void main( String args[] )
 8 {
 9 // queue of capacity 11 
10 PriorityQueue< Double > queue = new PriorityQueue< Double >();
11
12 // insert elements to queue
13 queue.offer( 3.2 ); 
14 queue.offer( 9.8 ); 
15 queue.offer( 5.4 ); 
16
17 System.out.print( "Polling from queue: " );
18
19 // display elements in queue
20 while ( queue.size() > 0 )
21 {
22 System.out.printf( "%.1f ", queue.peek() ); // view top element
23 queue.poll(); // remove top element
24 } // end while
25 } // end main
26 } // end class PriorityQueueTest

 

Polling from queue: 3.2 5.4 9.8

 

Line 10 creates a PriorityQueue that stores Doubles with an initial capacity of 11 elements and orders the elements according to the object's natural ordering (the defaults for a PriorityQueue). Note that PriorityQueue is a generic class and that line 10 instantiates a PriorityQueue with a type argument Double. Class PriorityQueue provides five additional constructors. One of these takes an int and a Comparator object to create a PriorityQueue with the initial capacity specified by the int and the ordering by the Comparator. Lines 1315 use method offer to add elements to the priority queue. Method offer throws a NullPointException if the program attempts to add a null object to the queue. The loop in lines 2024 use method size to determine whether the priority queue is empty (line 20). While there are more elements, line 22 uses PriorityQueue method peek to retrieve the highest-priority element in the queue for output (without actually removing the element from the queue). Line 23 removes the highest-priority element in the queue with method poll.