24.17. Synchronized Collections

 
[Page 731]

22.8. Queues and Priority Queues

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.

Figure 22.17. The Queue interface extends Collection to provide additional insertion, extraction, and inspection operations.

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.

Figure 22.18. The program adds string elements to a queue and removes the elements from the queue.
(This item is displayed on page 732 in the print version)


Listing 22.7. TestQueue.java
(This item is displayed on pages 731 - 732 in the print version)
 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 

[Page 732]
 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) .

Figure 22.19. The PriorityQueue class implements a priority queue.

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.

Figure 22.20. The program creates priority queues using Comparable and Comparator .
(This item is displayed on page 733 in the print version)


Listing 22.8. PriorityQueueDemo.java
(This item is displayed on pages 732 - 733 in the print version)
 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 

[Page 733]
 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 } 

 


Introduction to Java Programming-Comprehensive Version
Introduction to Java Programming-Comprehensive Version (6th Edition)
ISBN: B000ONFLUM
EAN: N/A
Year: 2004
Pages: 503

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net