This is a Java Program to implement Priority Queue. A priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a “priority” associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue. Here priority queue is implemented using a max heap.
Here is the source code of the Java Program to implement Priority Queue. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/** ** Java Program to implement Priority Queue **/ import java.util.Scanner; /** class Task **/ class Task { String job; int priority; /** Constructor **/ public Task(String job, int priority) { this.job = job; this.priority = priority; } /** toString() **/ public String toString() { return "Job Name : "+ job +"\nPriority : "+ priority; } } /** Class PriorityQueue **/ class PriorityQueue { private Task[] heap; private int heapSize, capacity; /** Constructor **/ public PriorityQueue(int capacity) { this.capacity = capacity + 1; heap = new Task[this.capacity]; heapSize = 0; } /** function to clear **/ public void clear() { heap = new Task[capacity]; heapSize = 0; } /** function to check if empty **/ public boolean isEmpty() { return heapSize == 0; } /** function to check if full **/ public boolean isFull() { return heapSize == capacity - 1; } /** function to get Size **/ public int size() { return heapSize; } /** function to insert task **/ public void insert(String job, int priority) { Task newJob = new Task(job, priority); heap[++heapSize] = newJob; int pos = heapSize; while (pos != 1 && newJob.priority > heap[pos/2].priority) { heap[pos] = heap[pos/2]; pos /=2; } heap[pos] = newJob; } /** function to remove task **/ public Task remove() { int parent, child; Task item, temp; if (isEmpty() ) { System.out.println("Heap is empty"); return null; } item = heap[1]; temp = heap[heapSize--]; parent = 1; child = 2; while (child <= heapSize) { if (child < heapSize && heap[child].priority < heap[child + 1].priority) child++; if (temp.priority >= heap[child].priority) break; heap[parent] = heap[child]; parent = child; child *= 2; } heap[parent] = temp; return item; } } /** Class PriorityQueueTest **/ public class PriorityQueueTest { public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Priority Queue Test\n"); System.out.println("Enter size of priority queue "); PriorityQueue pq = new PriorityQueue(scan.nextInt() ); char ch; /* Perform Priority Queue operations */ do { System.out.println("\nPriority Queue Operations\n"); System.out.println("1. insert"); System.out.println("2. remove"); System.out.println("3. check empty"); System.out.println("4. check full"); System.out.println("5. clear"); System.out.println("6. size"); int choice = scan.nextInt(); switch (choice) { case 1 : System.out.println("Enter job name and priority"); pq.insert(scan.next(), scan.nextInt() ); break; case 2 : System.out.println("\nJob removed \n\n"+ pq.remove()); break; case 3 : System.out.println("\nEmpty Status : "+ pq.isEmpty() ); break; case 4 : System.out.println("\nFull Status : "+ pq.isFull() ); break; case 5 : System.out.println("\nPriority Queue Cleared"); pq.clear(); break; case 6 : System.out.println("\nSize = "+ pq.size() ); break; default : System.out.println("Wrong Entry \n "); break; } System.out.println("\nDo you want to continue (Type y or n) \n"); ch = scan.next().charAt(0); } while (ch == 'Y'|| ch == 'y'); } }
Priority Queue Test Enter size of priority queue 7 Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 1 Enter job name and priority job1 24 Do you want to continue (Type y or n) y Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 1 Enter job name and priority job2 6 Do you want to continue (Type y or n) y Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 1 Enter job name and priority job3 28 Do you want to continue (Type y or n) y Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 1 Enter job name and priority job4 63 Do you want to continue (Type y or n) y Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 1 Enter job name and priority job5 5 Do you want to continue (Type y or n) y Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 1 Enter job name and priority job6 94 Do you want to continue (Type y or n) y Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 1 Enter job name and priority job7 14 Do you want to continue (Type y or n) y Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 6 Size = 7 Do you want to continue (Type y or n) y Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 4 Full Status : true Do you want to continue (Type y or n) y Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 2 Job removed Job Name : job6 Priority : 94 Do you want to continue (Type y or n) y Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 2 Job removed Job Name : job4 Priority : 63 Do you want to continue (Type y or n) y Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 2 Job removed Job Name : job3 Priority : 28 Do you want to continue (Type y or n) y Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 2 Job removed Job Name : job1 Priority : 24 Do you want to continue (Type y or n) y Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 2 Job removed Job Name : job7 Priority : 14 Do you want to continue (Type y or n) y Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 2 Job removed Job Name : job2 Priority : 6 Do you want to continue (Type y or n) y Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 2 Job removed Job Name : job5 Priority : 5 Do you want to continue (Type y or n) y Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 2 Heap is empty Job removed null Do you want to continue (Type y or n) y Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 3 Empty Status : true Do you want to continue (Type y or n) y Priority Queue Operations 1. insert 2. remove 3. check empty 4. check full 5. clear 6. size 6 Size = 0 Do you want to continue (Type y or n) n
Related posts:
Java Program to Implement Sorted Doubly Linked List
Java Program to Implement LinkedTransferQueue API
Validate email address exists or not by Java Code
Java Program to Generate a Graph for a Given Fixed Degree Sequence
Hướng dẫn sử dụng Java Reflection
Java Program to Describe the Representation of Graph using Adjacency Matrix
Java Program to Implement WeakHashMap API
OAuth2 for a Spring REST API – Handle the Refresh Token in Angular
Hướng dẫn Java Design Pattern – Intercepting Filter
Java Program to Implement LinkedBlockingDeque API
wait() and notify() Methods in Java
Comparing Strings in Java
Java Program to Create a Random Linear Extension for a DAG
Biến trong java
Java Program to Implement Selection Sort
Java Program to Generate All Possible Combinations Out of a, b, c, d, e
Java Program to Perform Right Rotation on a Binary Search Tree
Java Program to Implement the Vigenere Cypher
Tránh lỗi NullPointerException trong Java như thế nào?
Đồng bộ hóa các luồng trong Java
Format ZonedDateTime to String
Java IO vs NIO
How to Read HTTP Headers in Spring REST Controllers
Java Program to Implement Quick Hull Algorithm to Find Convex Hull
Java Program to Solve a Matching Problem for a Given Specific Case
Java Program to find the maximum subarray sum O(n^2) time(naive method)
Get and Post Lists of Objects with RestTemplate
Anonymous Classes in Java
Hashing a Password in Java
Java Program to Implement Gauss Seidel Method
Cachable Static Assets with Spring MVC
Guide to Java Instrumentation