22.12. Chapter Summary

[Page 688 ( continued )]

20.6. Priority Queues

A regular 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 with priorities. When accessing elements, the element with the highest priority is removed first. A priority queue has a largest-in/first-out behavior. For example, the emergency room in a hospital assigns priority numbers to patients ; the patient with the highest priority is treated first.

A priority queue can be implemented using a heap, where the root is the object with the highest priority in the queue. The class diagram for the priority queue is shown in Figure 20.28. Its implementation is given in Listing 20.12.

Figure 20.28. MyPriorityQueue uses a heap to provide a largest-in/first-out data structure.

Listing 20.12. MyPriorityQueue.java

 1   public class   MyPriorityQueue { 2    private   Heap heap =   new   Heap();  3 4    public void   enqueue(Object newObject)  { 5 heap.add(newObject); 6 } 7 8   public   Object dequeue() { 9   return   heap.remove(); 10 } 11 12    public int   getSize()  { 13   return   heap.getSize(); 14 } 15 } 

Listing 20.13 gives an example of using a priority queue for patients. The Patient class is declared in lines 18 “34. Four patients are created with associated priority values in lines 3 “6. Line 8 creates a priority queue. The patients are enqueued in lines 9 “12. Line 15 dequeues a patient from the queue.

Listing 20.13. TestPriorityQueue.java

(This item is displayed on pages 688 - 689 in the print version)

 1   public class   TestPriorityQueue { 2   public static void   main(String[] args) { 3  Patient patient1 =   new   Patient(   "John"   ,   2   );  4 Patient patient2 =   new   Patient(   "Jim"   ,   1   ); 5 Patient patient3 =   new   Patient(   "Tim"   ,   5   ); 6 Patient patient4 =   new   Patient(   "Cindy"   ,   7   ); 7 

---

[Page 689]

 8  MyPriorityQueue priorityQueue =   new   MyPriorityQueue();  9  priorityQueue.enqueue(patient1);  10 priorityQueue.enqueue(patient2); 11 priorityQueue.enqueue(patient3); 12 priorityQueue.enqueue(patient4); 13 14   while   (  priorityQueue.getSize() >      ) 15 System.out.print(  priorityQueue.dequeue()  +   " "   ); 16 } 17 18   static class   Patient    implements   Comparable  { 19   private   String name ; 20   private int   priority; 21 22   public   Patient(String name,   int   priority) { 23   this   .name = name; 24   this   .priority = priority; 25 } 26 27   public   String toString() { 28   return   name +   "(priority:"   + priority +   ")"   ; 29 } 30 31    public int   compareTo(Object o)  { 32   return this   .priority - ((Patient)o).priority; 33 } 34 } 35 } 

The printout from Listing 20.13 is

   Cindy(priority:7) Tim(priority:5) John(priority:2) Jim(priority:1)