The Blog

What is Priority Queue? Priority Queue in Java

What is Priority Queue? Priority Queue in Java

Do you know what is Priority Queue? Have you ever thought about what will be the process to implement Priority Queue? Let’s have an experience of how we can implement a Priority Queue.

But before we start the programming aspect of Priority Queue, let us first think about what is called a Priority Queue in daily life.

Let’s assume one scenario:

Suppose, you & your friends are standing in a queue for train tickets. Suddenly, you saw a very old man there. What will be your duty at that moment? Your duty to first let the old man book his ticket. That means the old man has the priority to book the ticket. Again a disabled person came to book a ticket there. Then what will you do at that point? Who will book the ticket first? The old man or the disabled person?

So, in such cases, there will be a relative priority consideration happen. Generally, a Disabled person has the top priority. After that, the old man will book the ticket. At last, you & your friends can collect the ticket.

The same thing happens to Priority Queue in Java. Several elements will make a queue along with a special value. Among them, whoever has the highest special value will first come out from the queue.

But before we implement the Priority Queue Java, let us first know briefly what do you mean by this.

 

What Is Priority Queue in Java? Read More

 

Priority Queue in Java

Not only in Java but Priority Queue can also be implemented in any programming language. It is a special type of Queue. The Queue is a type of Data Structure. Priority Queue is quite different from that. In such cases, there is a special value available called ‘Priority’. Based on the priority insertion or deletion can happen.

Priority Queue has some properties. Depending upon the properties the operations are performed. They are:

  1. Each element is associated with a priority value. And, elements are inserted based on their priority. That is, higher priority elements are served first.
  2. An element with high priority is dequeued before an element with low priority.
  3. However, if elements with the same priority occur, they are served according to their order in the queue.

 

Priority Queue in Java 

 

Get to Know Types Of Priority Queue:

 

Priority Queue Java mainly can be differentiated into two types. According to the Priority with the number, the divisions are following two types:

  • Minimum Priority Queue or Ascending Order Priority Queue:

 

In this type , the minimum number gets the highest priority. On the other hand, the maximum number in the queue gets the minimum priority. That is why this type of Priority Queue appears in the Ascending Order. That is why sometimes it is called an Ascending Order Priority Queue.

 

Suppose, in a queue, the number 1 gets the priority 10 & number 10 gets the priority 1. Same number 2 gets priority 9 & number 9 gets priority 2. So, what will be the structure of the queue? It will be in ascending order like 1,2,3,4….,10. The number with the highest priority appears at the beginning.

 

  • Maximum Priority Queue or Descending Order Priority Queue:

 

It is just the opposite of the Minimum Priority Queue. In this type of Priority Queue, the minimum number gets the lowest priority. On the other hand, the maximum number in the queue gets the highest priority. That is why this type of Priority Queue appears in the Descending Order. This is the reason it is called a Descending Order Priority Queue.

 

Suppose, in a queue, the number 10 gets the priority 10 & number 1 gets the priority 1. Same number 9 gets priority 9 & number 2 gets priority 2. So, what will be the structure of the queue? It will be in descending order like 10,9,8,7….,1. The number with the highest priority appears at the beginning.

 

Ways To Implement Priority Queue:

 

Though there are many ways to implement . But it is the nature of humans to follow the relatively easier rule. So, mainly there are two ways to implement a Priority Queue. Generally, a normal Queue can also be implemented using such Data Structures.

The proposed ways to implement  are:

  1. Using Linked List
  2. Using Array

Both above are types of Data Structures. Both are linear. But in between them, using Linked List to develop the Priority Queue is the easiest process. Just we need to have the basic knowledge of the Linked List.

 

What are the Operations in Priority Queue?

 

Not only Priority Queue, but Normal Queue also has only the following two operations. Other than these, there will not be any possible operation performed on Queue. Though developers can add any operations made by themselves. The proposed operations  are:

  1. En-Queue or Insertion
  2. De-Queue or Deletion

Let us know briefly about the processes.

 

En-Queue Operation in Priority Queue:

 

En-Queue is a simple operation. In the normal queue, a number will be added to the last of the Queue.  But in the case of Priority Queue, the operation is quite different.

En-Queue operation inserts an item into it. The item can be inserted at the end of the queue or the front of the queue or in the middle based on the priority value.

 

De-Queue Operation in Priority Queue: 

 

De-Queue is another operation performed in the Queue. In a normal queue also, there is a De-Queue operation. But there every number was removed from a certain side of the Queue. Whereas in Priority Queue the operation is quite different.

The De-Queue operation deletes the item with the highest priority from the queue. This means it will track the priority of the numbers. And then the number with the highest priority will get removed. Same as we have given in our daily life example.

 

Implementation Of Priority Queue:

 

Here, we are mainly using the Linked List method. according to the Linked List, we have taken one structure. The structure will have the info, and priority of that number. Also, it will have the pointer to store the address of the next node.

Let us implement some code snippets of important operations:

 

 

  • De-Queue Operation or Deletion Operation:

 

Here, we need to first check whether the Priority Queue is empty or not. If it is empty then the Deletion can’t happen. But if it has the elements in the Queue, then the element which has the highest priority will get removed first along with the priority. Then the Starting Pointer will point to the next address.

// Function To Delete To Node From Queue

void delete(){

    // Condition To Checks If Queue Is Already Empty

    struct node *p;

    if(start==NULL)

        printf("List is Empty\n");

    // Deleting The Node

    else {

        p=start;

        start=start->next;

        printf("The deleted node is %d\n",p->info);

        free(p); }}

 

  • En-Queue Operation or Insertion Operation:

 

If the start pointer is equal to null then Queue is empty. Then we have to create a node and make the node at the front of the queue. Else if the front is not equal to null then iterate over the queue till its reaches a node with a priority less than the new node.

There we need to insert the data in the queue before at the position where the new node priority is greater than the priority of the element in the queue. If the priority of the new node is greater than the start node. Then the new node will be inserted in the beginning & the start node will become the next node.

// Function To Add Node In Queue According To Priority

void insert(int x,int n){

    struct node *p,*prev;

    struct node *newnode;

    // This Will Create Node In Dynamic Manner.

    newnode=(struct node *)malloc(sizeof(struct node));

    prev=(struct node *)malloc(sizeof(struct node));

    newnode->info=x;   // Storing Given Input Info In New Node

    newnode->priority=n;  // Storing Priority Of Node

    newnode->next=NULL;  // Storing Address Of Next Node

    // Condition To Check If Queue Is Empty If It Is Then It Will Allot Newnode as Start/First Node

    if(start==NULL)

        start=newnode;

    //Condition To Check If Incoming Node Priority Is Lower Than Start Node

    else if(newnode->priority>start->priority){

        prev=start;   // This Will Store Start Node To Temporary Node Called As Prev

        p=start;

        // Iterate Over Nodes Till It Finds Node With Less Priority

        while(p!=NULL && p->priority<=newnode->priority){

            prev=p;

            p=p->next;}

        newnode->next=p;

        prev->next=newnode;}

    // If Incoming Node Has Highest Priority Then Make As Start Node And Start Node As Next Node

    else{

        newnode->next=start;

        start=newnode; }}


  • Display Of the Queue:

 

In this function, first, it will be checked whether the queue has elements or not. If it has elements then the pointer will iterate to every node. And it will print the data stored there. Also, it will print the priority of the numbers.

// Function To Display The Queue With Priority

void display(){

    struct node *p;

    // Condition To Check if Queue is Already Empty

    if(start==NULL)

        printf("List is Empty\n");

    // Iterate Over All Node & Simultaneously Print Its Data

    else{

        p=start;

        printf("The elements in the link list are\n");

        printf("PRIORITY  INFO\n");

        while(p!=NULL) {

            printf("%d %d\n",p->priority,p->info);

            p=p->next;}}


  • Main Function:

In this function, we will ask the users to choose their input. After that, they will provide the inputs there. The inputs will be transferred to a certain function for further process. According to the input of the user, proper action will be performed.

void main(){

    struct node *p; int x,choice,n;

    while(1){  // User Input Choice

        printf("Enter your choice:\n1.insert as per priority\n2.delete \n3.display\n4.exit\n");

        scanf("%d",&choice);

        switch(choice){ case 1:

                printf("Enter value to be entered into queue :"); scanf("%d",&x);

                printf("Enter priority of the node :"); scanf("%d",&n); insert(x,n); break;

            case 2: delete(); break; case 3: display(); break;

            case 4: printf("Thank you\n"); exit(0); break;

            default: printf("Invalid input\n");}}}

Above are the code snippets. If needed, you can go through the full source code provided here. The probable output of the  will be the following.

Output:

Main Function

Main Function

Conclusion:

As we saw Priority Queue is very important.

We should clear the basics of recursion & function calling for learning the Priority Queue.

We should clear the Linked List concept also. That is very important to implement the same.

So, hope you have liked this piece of article. Share your thoughts in the comments section and let us know if we can improve more.

Also, if you guys are looking to get help with Java Assignments or Programming then you can use our Java Homework Help Services.

If you are looking for Final Year Java Project Ideas then you can contact us as well.

Sanjana Grover
Sanjana Grover

Leave a Comment