IMPLEMENTING LISTS, STACKS, QUEUES, AND PRIORITY QUEUES - Introduction to Java Programming: Comprehensive Version - page 924

24.6 Priority Queues
Priority queues can be implemented using heaps.

Key
Point

An ordinary queue is a first-in, first-out data structure. Elements are appended to the end of
the queue and removed from the beginning. In a priority queue , elements are assigned with
priorities. When accessing elements, the element with the highest priority is removed first.
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, in which the root is the object with the
highest priority in the queue. Heaps were introduced in Section 23.6, Heap Sort. The class dia-
gram for the priority queue is shown in Figure 24.23. Its implementation is given in Listing 24.9.

MyPriorityQueue
<E extends Comparable<E>>

-heap: Heap<E>

+enqueue(element: E): void
+dequeue(): E
+getSize(): int

Adds an element to this queue.
Removes an element from this queue.
Returns the number of elements in this queue.

F IGURE 24.23

MyPriorityQueue uses a heap to provide a largest-in, first-out data structure.

L ISTING 24.9

MyPriorityQueue.java
1 public class MyPriorityQueue<E extends Comparable<E>> {
2 private Heap<E> heap = new Heap<>();

heap for priority queue

3
4 public void enqueue(E new Object) {
5 heap.add( new Object);
6 }
7
8

enqueue

public E dequeue() {

dequeue

9 return heap.remove();

10 }
11
12

public int getSize() {

getsize

13 return heap.getSize();

14 }
15 }

Listing 24.10 gives an example of using a priority queue for patients. The Patient class is
defined in lines 19-37. Four patients are created with associated priority values in lines 3-6.
Line 8 creates a priority queue. The patients are enqueued in lines 10-13. Line 16 dequeues a
patient from the queue.

L ISTING 24.10

TestPriorityQueue.java
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<Patient> priorityQueue
9 = new MyPriorityQueue<>();
10 priorityQueue.enqueue(patient1);
11 priorityQueue.enqueue(patient2);

create a patient

create a priority queue

add to queue