Tree data structure tutorial 9. Priority Queue

In this chapter we shall have a look at:

9.1. Priority Queue introduction
9.2. Usage of Priority Queue
9.3. Operations that can be performed on Priority Queue
9.4. Implementation of Priority Queue
9.5 Output

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

9.1. Priority Queue introduction

A priority queue is a collection of elements, where each element is assigned a priority. Based on 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.

9.2 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.

9.3 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.

9.4 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;
}

9.5 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