Priority Queue using Linked list

A priority queue is a type of queue in which each element in a queue is associated with some priority, and they are served based on their priorities. If the elements have the same priority, they are served based on their order in a queue.

Mainly, the value of the element can be considered for assigning the priority. For example, the highest value element can be used as the highest priority element. We can also assume the lowest value element to be the highest priority element. In other cases, we can also set the priority based on our needs.

The following are the functions used to implement priority queue using linked list:

push(): It is used to insert a new element into the Queue.
pop(): It removes the highest priority element from the Queue.
peep(): This function is used to retrieve the highest priority element from the queue without removing it from the queue.

The linked list of priority queue is created in such a way that the highest priority element is always added at the head of the queue. The elements are arranged in a descending order based on their priority so that it takes O(1) time in deletion. In case of insertion, we need to traverse the whole list in order to find out the suitable position based on their priority; so, this process takes O(N) time.

Let’s understand through an example.

Consider the below-linked list that consists of elements 2, 7, 13, 15.

Suppose we want to add the node that contains the value 1. Since the value 1 has more priority than the other nodes so we will insert the node at the beginning of the list shown as below:

Now we have to add 7 element to the linked list. We will traverse the list to insert element 7. First, we will compare element 7 with 1; since 7 has lower priority than 1, so it will not be inserted before 7. Element 7 will be compared with the next node, i.e., 2; since element 7 has a lower priority than 2, it will not be inserted before 2.. Now, the element 7 is compared with a next element, i.e., since both the elements have the same priority so they will be served based on the first come first serve. The new element 7 will be added after the element 7 shown as below:

Implementation in C

  # include  # include    typedef struct node  {  int priority;  int info;  struct node *link;  }NODE;  NODE *front = NULL;    // insert method  void insert(int data,int priority)  {  NODE *temp,*q;    temp = (NODE *)malloc(sizeof(NODE));  temp->info = data;  temp->priority = priority;  // condition to check whether the first element is empty or the element to be inserted has more priority than the first element  if( front == NULL || priority < front->priority )  {  temp->link = front;  front = temp;  }  else  {  q = front;  while( q->link != NULL && q->link->priority <= priority )  q=q->link;  temp->link = q->link;  q->link = temp;  }  }    // delete method    void del()  {  NODE *temp;          // condition to check whether the Queue is empty or not  if(front == NULL)  printf(“Queue Underflown”);  else  {  temp = front;  printf(“Deleted item is %dn”, temp->info);  front = front->link;  free(temp);  }    // display method  void display()  {  NODE *ptr;  ptr = front;  if(front == NULL)  printf(“Queue is emptyn”);  else  {  printf(“Queue is :n”);  printf(“Priority       Itemn”);  while(ptr != NULL)  {  printf(“%5d        %5dn”,ptr->priority,ptr->info);  ptr = ptr->link;  }  }  }  /*End of display*/    // main method  int main()  {  int choice, data, priority;  do  {  printf(“1.Insertn”);  printf(“2.Deleten”);  printf(“3.Displayn”);  printf(“4.Quitn”);  printf(“Enter your choice : “);  scanf(“%d”, &choice);  switch(choice)  {  case 1:  printf(“Enter the data which is to be added in the queue : “);  scanf(“%d”,&data);  printf(“Enter its priority : “);  scanf(“%d”,&priority);  insert(data,priority);  break;  case 2:  del();  break;  case 3:  display();  break;  case 4:  break;  default :  printf(“Wrong choicen”);  }  }while(choice!=4);    return 0;  }  

Output

Next TopicBalanced Binary Search Tree

Priority Queue using Linked list

Priority Queue using Linked list

Cycle Sort

Characteristics of OLAP

You may also like