Java Program to implement Priority Queue

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