Mumbai University > Information Technology > Sem 3 > Data Structure and Algorithm analysis

Marks: 10 M

Year: May 2014, May 2013, Dec 2012, May 2015

• A priority queue is a special queue where each elements in the queue are assigned a priority.
• In Queue, the insertion and deletion takes place by the FIFO policy. However, in priority queue, the insertion and deletion takes place based on the priority assigned to each element.
• It is a special type of queue where if an element needs to be taken out from the queue, we remove the highest-priority element.
• The general rule regarding evaluation of priority queue are:
  • The elements of high priority are processed before the elements of lower priority.
  • If the priority values are same, we apply FCFS principle.
• Priority queues are widely used in operating systems. The value of priority can be based on various factors like CPU time required, memory requirement etc.

Implementation:

• Priority queues can represented in two ways.
  • Array or Sequential representation.
  • Dynamic or linked representation.
• Here we will demonstrate how it is done using linked lists.
• Insertion of an element in difficult in priority queue as compared to deletion because we have to find out the exact location where the new element must be entered based on the priority.
• Every node in the list will have three value :
  • Data
  • Priority value
  • Address of next node.
• One pre-condition of a priority queue is that it should be sorted. So insertion has to happen only at the rightful position without disturbing the order.

Program:

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
    int data;
    int priority;
    struct node *next;
}
struct node *start = NULL;
struct node *insert_element(struct node *);
strcut node *delete_element(struct node *);
void display_queue(struct node *);
int main()
{ 
int choice;
    clrscr();
    do
    {
        printf("\nEnter ypur choice");
        printf("\n 1 insert");
        printf("\n 2 delete");
        printf("\n 3 display");
        printf("\n 4.exit");
        scanf("%d", &choice);
        switch (choice)
        {
        case 1:
            start = insert_element(start);
            break;
        case 2:
            start = delete_element(start);
            break;
        case 3:
            display_queue(start);
        }
        while (option != 4);
    }
    /* in this code, lesser number means higher priority*/
    struct node *insert_element(struct node *start)
    {
        int val, pri;
        struct node *ptr, *p;
        ptr = (struct node *)malloc(sizeof(struct node));
        printf("\n enter the data and priority value");
        scanf("%d %d", &val, &pri);
        ptr->data = val;
        ptr->priority = pri;
        //check if queue is empty OR
        //priority of start node is more than new node's priority
        if (start == NULL || pri < start->priority)
        {
            ptr->next = start;
            start = ptr;
        }
        //insert the element in its correct position
        else
        {
            p = start;
            while (p->next != NULL && p->next->priority <= pri)
                p = p->next;
            ptr->next = p->next;
            p->next = ptr;
        }
        return start;
    }
    struct node *delete_element(struct node *start)
    {
        struct node *ptr;
        if (start == NULL)
        {
            printf("queue not initiated");
            return;
        }
        else
        {
            ptr = start;
            printf("deleted data is %d", ptr->data);
            start = start->next;
            free(ptr);
        }
        return start;
    }
    void display_queue(struct node *start)
    {
        struct node *ptr;
        ptr = start;
        if (start == NULL)
            printf("empty queue");
        else
        {
            while (ptr != NULL)
            {
                printf("|| data=%d priority=%d", ptr->data, ptr->priority);
                ptr = ptr->next;
            }
        }
    }

Output:
Enter ypur choice
 1 insert
 2 delete
 3 display
 4.exit1
 enter the data and priority value5
3
 enter the data and priority value3
1
|| data=3 priority=1|| data=5 priority=3