SYBSc (CS) Sem III : Data Structure Slip 11 Que - 2

   SAVITIBAI PHULE UNIVERSITY OF PUNE

S. Y. B.Sc. (Computer Science) Semester III

Practical Examination

      SUBJECT: CS-233 Practical course based on CS231 

/* Q. 2 Implement a priority queue library (Priority.h) of integers using a static implementation of the queue and implementing the below two operations. Write a driver program that includes queue library and calls different queue operations.

1) Add an element with its priority into the queue.

2) Delete an element from queue according to its priority. */

// File name : "PriorityQ.c"

#include"PriorityQ.h"

int initPQ(struct PriorityQueue *pq)

{

    pq->front = pq->rear = -1;

    return 0;

}

int isFullPQ(struct PriorityQueue *pq)

{

    if(pq->rear == MAX-1)

        return 1;

    else

        return 0;

}

int isEmptyPQ(struct PriorityQueue *pq)

{

    if(pq->front == -1)

        return 1;

    else

        return 0;

}

void InsertPQ(struct PriorityQueue *pq, struct data dt)

{

    struct data temp;

    int i, j;    

    pq->rear++;

    pq->d[pq->rear] = dt;

    

    if(pq->front == -1)

            pq->front = 0;    

    for( i = pq->front; i <= pq->rear; i++)

    {

          for( j = i+1; j <= pq->rear; j++ )

          {

               if( pq->d[i].priority > pq->d[j].priority )

               {

                   temp = pq->d[i];

                   pq->d[i] = pq->d[j];

                   pq->d[j] = temp;

               }

               else

               {

                   if( pq->d[i].priority == pq->d[j].priority )

                   {

                       if( pq->d[i].order > pq->d[j].order )

                       {

                            temp = pq->d[i];

                            pq->d[i] = pq->d[j];

                            pq->d[j] = temp;

                       }

                   }

               }

          }

    }    

}

struct data DeletePQ(struct PriorityQueue *pq)

{

    struct data t = pq->d[pq->front];   

    if( pq->front == pq->rear )

        pq->front = pq->rear = -1;

    else

        pq->front++;        

    return t;

}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// File name : "PriorityQ.h"

#include<stdio.h>

#include<stdlib.h>

#define MAX 10

struct data

{

       int item;

       int priority;

       int order;

};

struct PriorityQueue

{

       struct data d[MAX];

       int front;

       int rear;

};

int initPQ(struct PriorityQueue *pq);

int isFullPQ(struct PriorityQueue *pq);

int isEmptyPQ(struct PriorityQueue *pq);

void InsertPQ(struct PriorityQueue *pq, struct data dt);

struct data DeletePQ(struct PriorityQueue *pq);

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// File name : "main.c"

#include"PriorityQ.h"

int main(int argc, char *argv[])

{

    struct PriorityQueue q;

    struct data temp;

    

    int i = 0, ch;

        

    initPQ(&q);

    

    do{

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

       scanf("%d", &ch);

       

       switch(ch)

       {

            case 1:

                 if(isFullPQ(&q))

                     printf("\n Queue is full.");

                 else

                 {

                     printf("Enter the data and Priority : ");

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

                     scanf("%d%d", &(temp.item), &(temp.priority));

                     temp.order = i++;             

                     InsertPQ(&q, temp);

                 } 

                 break;

                 

            case 2:

                 if(isEmptyPQ(&q))

                    printf("\n Queue is Empty");

                 else

                 {

                     temp = DeletePQ(&q);

                     printf("Data = %d \t Priority  = %d \n", temp.item, temp.priority);

                 }

                 break;

            default:

                 printf("Thank you visit again ....\n\n");

                 break;          

       }

    

    }while(ch>0 && ch<3);

    

    system("PAUSE");

    return 0;

}