ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Tree data structure tutorial 9. Priority Queue

prodevelopertutorial June 15, 2019

In this chapter we shall learn about priority queue and it’s implementation using Linked list using C language.

A priority queue is a collection of elements, where each element is assigned a priority. Based o the priority the elements are inserted or deleted from the priority queue data structure.

One of the easiest way to implement PQ is by using Linked List.

Where do we use PQ?

There are number of real world scenarios where we use PQ.

For example:
1. A process with higher priority needs to be executed first than the process with lower priority.
2. During printing job of 100 pages, if there is priority for a particular document, then the printer has to pause the ongoing job and start printing the high priority job.

Below are the operations performed on PQ:

1. Enqueue: adds an element with given priority
2. Dequeue: Deletes an element with highest priority
3. Peek(): returns highest priority element.

Implementation of Priority Queue using Linked List using C:

#include "stdio.h"
#include "stdlib.h"

//strucure to hold priority queue data structure
struct Node
{
    int data;
    int priority;
    struct Node* next;
};

//head node
struct Node* head = NULL;

// traverse element by element
void traverse()
{
    //take temp node to traverse.
    struct Node* temp = head;
    while(temp != NULL)
    {
        printf("\n Data = %d  and it's priority is = %d ",temp->data,temp->priority);
        temp = temp->next;
    }
}

//check if the list is empty
int isempty()
{
    if(head == NULL)
        return 1;
    else
        return 0;
}

// insert element with priority in it's correct place
void enqueue(int priority, int data)
{
    //create a temp node and then copy the data and priority
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    struct Node* p = head;
    temp->data = data;
    temp->priority = priority;

    if(isempty() || priority < head->priority)
    {
        temp->next = head;
        head = temp;
    }

    else
    {
        while(p->next!=NULL && p->next->priority <= priority)
            p = p->next;

        temp->next = p->next;
        p->next = temp;
    }
}

int dequeue()
{
    struct Node *tmp;
    int item;
    if( isempty() )
    {
        printf("\nQueue Underflow\n");
        return -1;
    }
    else
    {
        tmp=head;
        item=tmp->data;
        head=head->next;
        free(tmp);
    }
    return item;
}


int main()
{
    //lower the priority value, higher the priority
    enqueue(4,34);
    enqueue(1,25);
    enqueue(6,98);
    enqueue(2,87);
    enqueue(3,67);
    enqueue(5,23);
    
    traverse();

    printf("\nhighest priority element is = %d\n",dequeue()); 
    return 0;
}

 

Output:

 

Data = 25 and it's priority is = 1
Data = 87 and it's priority is = 2
Data = 67 and it's priority is = 3
Data = 34 and it's priority is = 4
Data = 23 and it's priority is = 5
Data = 98 and it's priority is = 6
highest priority element is = 25

Further Reading:

AJ’s definitive guide for DS and Algorithms. Click here to study the complete list of algorithm and data structure tutorial. 85+ chapters to study from.

 

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2020 ProDeveloperTutorial.com
Get top courses from: Educative.io