A queue is a first-in/first-out data structure. Elements are appended to the end of the queue and are removed from the beginning of the queue. In a priority queue, elements are assigned priorities. When accessing elements, the element with the highest priority is removed first. The design and implementation of queues and priority queues were introduced in §20.3, "Stacks and Queues"and §20.6 "Priority Queues". This section introduces queues and priority queues in the Java API.
JDK 1.5 introduced the Queue interface that extends java.util.Collection with additional insertion, extraction, and inspection operations, as shown in Figure 22.17.
The offer method is used to add an element to the queue. This method is similar to the add method in the Collection interface, but the offer method is preferred for queues. The poll and remove methods are similar except that poll() returns null if the queue is empty, whereas remove() throws an exception. The peek and element methods are similar except that peek() returns null if the queue is empty, whereas element() throws an exception.
In JDK 1.5, the LinkedList class implements the Queue interfaces, so you can use LinkedList to create a queue. Listing 22.7 shows an example of using a queue to store strings. Line 3 creates a queue using LinkedList . Four strings are added to the queue in lines 4 “7. The size () method defined in the Collection interface returns the number of elements in the queue (line 9). The remove() method retrieves and removes the element at the head of the queue (line 10). Figure 22.18 shows the output of the program.
1 public class TestQueue { 2 public static void main(String[] args) { 3 java.util.Queue<String> queue = new java.util.LinkedList<String>(); 4 queue.offer( "Oklahoma" ); 5 queue.offer( "Indiana" ); 6 queue.offer( "Georgia" ); 7 queue.offer( "Texas" ); 8 9 while ( queue.size() > ) 10 System.out.print(queue.remove() + " " ); 11 } 12 } |
The PriorityQueue class in JDK 1.5 implements a priority queue, as shown in Figure 22.19. By default, the priority queue orders its elements according to their natural ordering using Comparable . The element with the least value is assigned the highest priority, and thus is removed from the queue first. If there are several elements with the same highest priority, the tie is broken arbitrarily. You can also specify an ordering using Comparator using the constructor PriorityQueue(initialCapacity, comparator) .
Listing 22.8 shows an example of using a priority queue to store strings. Line 5 creates a priority queue for strings using its no-arg constructor. This priority queue orders the strings using their natural order, so the strings are removed from the queue in increasing order. Line 16 creates a priority queue using the comparator obtained from Collections.reverseOrder() , which orders the elements in reverse order, so the strings are removed from the queue in decreasing order. Figure 22.20 shows the output of the program.
1 import java.util.*; 2 3 public class PriorityQueueDemo { 4 public static void main(String[] args) { 5 PriorityQueue<String> queue1 = new PriorityQueue<String>(); 6 queue1.offer( "Oklahoma" ); 7 queue1.offer( "Indiana" ); 8 queue1.offer( "Georgia" ); 9 queue1.offer( "Texas" ); 10 11 System.out.println( "Priority queue using Comparable:" ); 12 while (queue1.size() > ) { 13 System.out.print(queue1.remove() + " " ); 14 } 15 16 PriorityQueue<String> queue2 = new PriorityQueue<String>( 17 4 , Collections.reverseOrder() ); 18 queue2.offer( "Oklahoma" ); 19 queue2.offer( "Indiana" ); 20 queue2.offer( "Georgia" ); 21 queue2.offer( "Texas" ); 22 23 System.out.println( "\nPriority queue using Comparator:" ); 24 while (queue2.size() > ) { 25 System.out.print(queue2.remove() + " " ); 26 } 27 } 28 } |