Introduction to Java Programming-Comprehensive Version (6th Edition)
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 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)