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');
}}
advertisement
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
Sanfoundry Global Education & Learning Series – 1000 Java Programs.
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.
