Priority Queues

 Priority Queues

AU: Dec.-19, Marks 15

• Definition: The priority queue is a data structure having a collection of elements which are associated with specific ordering.

• There are two types of priority queues-

 1. Ascending priority queue 2. Descending priority queue.

Application of Priority Queue

1. The typical example of priority queue is scheduling the jobs in operating system. Typically operating system allocates priority to jobs. The jobs are placed in the queue and position of the job in priority queue determines their priority. In operating system there are three kinds of jobs. These are real time jobs, foreground jobs and background jobs. The operating system always schedules the real time jobs first. If there is no real time job pending then it schedules foreground jobs. Lastly if no real time or foreground jobs are pending then operating system schedules the background jobs.

2. In network communication, to manage limited bandwidth for transmission the priority queue is used.

3. In simulation modelling, to manage the discrete events the priority queue is used.

Types of Priority Queue

The elements in the priority queue have specific ordering. There are two types of priority queues -

1. Ascending priority queue: An ascending order priority queue gives the highest priority to the lower number in that queue.

2. Descending priority queue: A descending order priority queue gives the highest priority to the highest number in that queue.

In priority queue, the elements are arranged in any order and out of which only the smallest or largest element allowed to delete each time.

The implementation of priority queue can be done using arrays or linked list. The data structure heap is used to implement the priority queue effectively.

ADT for Priority Queue

Various operations that can be performed on priority queue are

1. Insertion

2. Deletion

3. Display

Hence the ADT for priority queue is given as below -

Instances:

P_que[MAX] is a finite collection of elements associated with some priority.

Precondition :

The front and rear should be within the maximum size MAX.

Before insertion operation, whether the queue is full or not is checked.

Before any deletion operation, whether the queue is empty or not is checked.

Operations :

1. create() - The queue is created by declaring the data structure for it.

2. insert() The element can be inserted in the queue.

3. delet() - If the priority queue is ascending priority queue then only smallest element is deleted each time. And if the priority queue is descending priority queue then only largest element is deleted each time.

4. display() The elements of queue are displayed from front to rear.

The implementation of priority queue using arrays is as given below -

1. Insertion operation

While implementing the priority queue we will apply a simple logic. That is while inserting the element we will insert the element in the array at the proper position. For example, if the elements are placed in the queue as

And now if an element 8 is to be inserted in the queue then it will be at 0^th location as -

If the next element comes as 11 then the queue will be -

The C function for this operation is as given below -

int insert(int que[SIZE],int rear,int front)

{

int item,j;

printf("\nEnter the element: ");

scanf("%d", &item);

if(front ==-1)

front++;

j=rear;

while(j>=0 && item<que[j])

{

quelj+1]=que[j];

j- -;

}

que[j+1]=item;

rear=rear+1;

return rear;

}

2. Deletion operation

In the deletion operation we are simply removing the element at the front.

For example, if queue is created like this -

Then the element at que[0] will be deleted first.

and then new front will be que[1].

The deletion operation in C is as given below -

int delet(int que[SIZE],int front)

{

int item;

item=que[front];

printf(“\n The item deleted is %d”,item);

front++;

return front;

}

The complete implementation of priority queue is as given below -

 

Ex. 4.11.1: Implementation of Priority Queue

Sol. :

/******************************************************************Program for implementing the ascending priority Queue

**************************************************************/

/*Header Files*/

#include<stdio.h>

#include<conio.h>

#define SIZE 5

void main(void)

{

int rear,front,que[SIZE], choice;

int Qfull(int rear), Qempty(int rear,int front);

 int insert(int que[SIZE], int rear,int front);

 int delet(int que [SIZE], int front);

void display(int que[SIZE], int rear,int front);

char ans;

clrscr();

front=0;

rear=-1;

do

{

clrscr();

printf("\n\t\t Priority Queue\n");

printf("\n Main Menu");

printf("\n1.Insert\n2.Delete\n3.Display");

printf("\n Enter Your Choice: ");

scanf("%d", &choice);

switch(choice)

{

case 1:if(Qfull(rear))

printf("\n Queue IS full");

else

rear=insert(que,rear, front);

break;

case 2:if(Qempty(rear, front))

printf("\n Cannot delete element");

else

front=delet(que, front);

break;

case 3:if(Qempty(rear, front))

printf("\n Queue is empty");

else

display(que,rear, front);

break;

default:printf("\n Wrong choice");

break;

}

printf("\n Do You Want To continue?");

ans =getche();

} while(ans == 'Y' || ans =='y');

getch();

}

int insert(int que [SIZE], int rear,int front)

{

int item,j;

printf("\nEnter the element: ");

scanf("%d", &item);

if(front = = -1)

front++;

j=rear;

while(j>=0 && item<que[j])

{

que[j+1]=que[j];

j- -;

}

que[j+1]=item;

rear=rear+1;

return rear;

}

int Qfull(int rear)

{

if(rear==SIZE-1)

return 1;

else

return 0;

}

int delet(int que[SIZE], int front)

{

int item;

item=que[front];

printf("\n The item deleted is %d",item);

front++;

return front;

}

Qempty(int rear,int front)

{

if((front==-1) | | (front>rear))

return 1;

else

return 0;

}

void display(int que[SIZE], int rear,int front)

{

int i;

printf("\n The queue is:");

for(i=front;i<=rear;i++)

printf("%d",que[i]);

}

Output

Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Output

Enter Your Choice: 1

  

Enter the element: 30

Do You Want TO continue?

Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 1 

Enter the element: 10

Do You Want TO continue?

Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 1 

Enter the element: 20

Do You Want TO continue?

Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 1 

Enter the element: 50

Do You Want TO continue?

Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 1 

Enter the element: 40

Do You Want TO continue?

Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 3 

The queue is: 10 20 30 40 50

Do You Want TO continue?

Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 2 

The item deleted is 10

Do You Want TO continue?

Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 2 

The item deleted is 20

Do You Want TO continue?

Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 2

The item deleted is 30

Do You Want TO continue?

Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 2 

The item deleted is 40

Do You Want TO continue?

Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 2

The item deleted is 50

Do You Want TO continue?

Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 2

Cannot delete element

Do You Want TO continue?

Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice: 3

Queue is empty

Do You Want TO continue?n

 

Ex. 4.11.2: Write program for implementing the linked priority queue.

Sol. :

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

/*Declaration of Linked Queue data structure*/

typedef struct node

{

int data;

struct node *next;

}Q;

Q *front, *rear;

/*

The main Function

*/

void main(void)

{

char ans;

int choice;

void insert();

Q *delet();

void display(Q *);

front= NULL;

rear= NULL;

do

{

printf("\n\tProgram For Linked priority Queue\n");

printf("\n Main Menu");

printf("\n1.Insert\n2.Delete \n3.Display");

printf("\n Enter Your Choice");

scanf("%d", &choice);

switch(choice)

{

case 1 : insert();

break;

case 2:front = delet();

break;

case 3 :display(front);

break;

default:printf("\nYou have entered Wrong Choice\n");

break;

}

printf("\nDo you want to continue?\n");

flushall();

ans = getch();

} while(ans=='y' || ans == 'Y');

getch();

clrscr();

}

/*

The get_node function

*/

Q *get_node(Q *temp)

{

temp =(Q*)malloc(sizeof(Q));

temp->next = NULL;

return temp;

}

/*

The insert Function

*/

void insert()

{

char ch;

Q *temp, *current, *prev; clrscr();

temp =get_node(temp); /* allocates memory for temp node*/

printf("\n\n\n\tInsert the element in the Queue\n");

scanf("%d",&temp->data);

/*The new node which is to be inserted is temp */

if(front == NULL)/* creating first node*/

{

front= temp;

rear=temp;

}

else/*first node is created and next node is to be attached*/

{

current=front;

/*current node is to be compared with every node from beginnning*/

prev=current;

/*if temp node is attached as a first node to remaining list*/

if(current->data>temp->data)

{

temp->next=current;

front=temp;/*update front*/

}

/*if temp node is to be inserted in between*/

else

{

while((current->data <temp->data)&&(current!= NULL))

{

/*prev is previous to current node */

prev=current;

current=current->next;

}/*end of while*/

/*if temp->data>current->data and current node!= NULL*/

if(current)

{

prev->next=temp;

temp->next = current;

}

/*attaching temp as a last node when temp has greaest among all the nodes in the list and we have reached at the end of the list*/

else

{

prev->next=temp;

rear=temp;/*as temp is appended, rear is changed,temp becomes rear*/

}

}

}/*closing the outermost else*/

}

/*

The delet Function

*/

Q *delet()

{

Q *temp;

int Qempty(Q *front);

temp=front;

if(Qempty(front))

{

printf("\n\n\t\tSorry!The Queue Is Empty\n");

printf("\n Can not delete the element");

}

else

{

printf("\n\tThe deleted Element Is %d ",temp->data);

front=front->next;/*deleting the front node*/

temp->next = NULL;

free(temp);

}

return front;

}

/*

The QEmpty Function

*/

int Qempty(Q *front)

{

if(front== NULL)

return 1;

else

return 0;

}

/*

The display Function

Input: front pointer

Called By:main

Calls:QEmpty

*/

void display(Q *front)

{

if(Qempty(front))

printf("\n The Queue Is Empty\n");

else

{

printf("\n\t The Display Of Queue Is \n");

/*queue is displayed from front to rear*/

for(;front!=rear->next;front=front->next)

printf("\t%d ",front->data);

}

getch();

}

Output

Program For Linked Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice 1

Insert the element in the Queue

9

Do you want to continue?

Program For Linked Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice 1

Insert the element in the Queue

11

Do you want to continue?

Program For Linked Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice 1

Insert the element in the Queue

15

Do you want to continue?

Program For Linked Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice 1

Insert the element in the Queue

7

Do you want to continue?

Program For Linked Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice 1

Insert the element in the Queue

12

Do you want to continue?

Program For Linked Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice 3

The Display Of Queue Is

7 9 11 12 15

Do you want to continue?

Program For Linked Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice 2

The deleted Element Is 7

Do you want to continue?

Program For Linked Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice 2

The deleted Element Is 9

Do you want to continue?

Program For Linked Priority Queue

Main Menu

1.Insert

2.Delete

3.Display

Enter Your Choice

The Display Of Queue Is

11 12 15

Do you want to continue?

Logic Explanation of Linked Priority Queue

Refer above program while understanding this section.

1. Insertion of a node

Initially queue will be empty and if we want to insert the first node. Then first memory will get allocated for temp node as :

If we want to insert 9 then

temp = get_node();

As it is our first node in queue

if (front== NULL)

{

front = temp;

rear = temp;

 }

 Now, if want to insert next item say 11 then we will create temp node as

Then we will start scanning the queue from beginning because we want to insert node with '11' at proper place.

While((current → data < temp → data)&&(current != NULL))

{

prev = current;

current = current →next;

current = NULL;

}

else

{

prev →next = temp;

rear = temp;

}

Now if we want to insert temp node with value '7' in the linked queue then we will find the position for temp node in linked queue.

if (current → data > temp → data)

{

temp → next = current;

 front = temp;

}

Continuing in this fashion we create a linked list in an ascending order.

2. Deletion of a node

The deletion operation is simple. We always delete a node which is at front.

Consider that the priority queue is

temp=front;

printf("\n\t The deleted element is%d", temp → data);

front =front → next;

temp → next =NULL;

Review Question

1. Implement a priority queue using linked list. AU: Dec.-19, Marks 15