Assignment 10:Priority Queue and Doubly Ended Queue (Dqueue)
Set A
a) Implement a priority queue library (PriorityQ.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.
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
void create_queue();
void insert_element(int);
void delete_element(int);
void check_priority(int);
void display_priorityqueue();
int pqueue[MAX];
int front, rear;
void main()
{
int n, choice;
printf("\nEnter 1 to insert element by priority ");
printf("\nEnter 2 to delete element by priority ");
printf("\nEnter 3 to display priority queue ");
printf("\nEnter 4 to exit");
create_queue();
while (1)
{
printf("\nEnter your choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("\nEnter element to insert : ");
scanf("%d",&n);
insert_element(n);
break;
case 2:
printf("\nEnter element to delete : ");
scanf("%d",&n);
delete_element(n);
break;
case 3:
display_priorityqueue();
break;
case 4:
exit(0);
default:
printf("\n Please enter valid choice");
}
}
}
void create_queue()
{
front = rear = -1;
}
void insert_element(int data)
{
if (rear >= MAX - 1)
{
printf("\nQUEUE OVERFLOW");
return;
}
if ((front == -1) && (rear == -1))
{
front++;
rear++;
pqueue[rear] = data;
return;
}
else
check_priority(data);
rear++;
}
void check_priority(int data)
{
int i,j;
for (i = 0; i <= rear; i++)
{
if (data >= pqueue[i])
{
for (j = rear + 1; j > i; j--)
{
pqueue[j] = pqueue[j - 1];
}
pqueue[i] = data;
return;
}
}
pqueue[i] = data;
}
void delete_element(int data)
{
int i;
if ((front==-1) && (rear==-1))
{
printf("\nEmpty Queue");
return;
}
for (i = 0; i <= rear; i++)
{
if (data == pqueue[i])
{
for (; i < rear; i++)
{
pqueue[i] = pqueue[i + 1];
}
pqueue[i] = -99;
rear--;
if (rear == -1)
front = -1;
return;
}
}
printf("\n%d element not found in queue", data);
}
void display_priorityqueue()
{
if ((front == -1) && (rear == -1))
{
printf("\nEmpty Queue ");
return;
}
for (; front <= rear; front++)
{
printf(" %d ", pqueue[front]);
}
front = 0;
}
b) A doubly ended queue allows additions and deletions from both the ends that is front and rear. Initially additions from the front will not be possible. To avoid this situation, the array can be treated as if it were circular. Implement a queue library (dstqueue.h) of integers using a static implementation of the circular queue and implementing the nine operations :
1)init(Q), 2) isempty(Q) 3) isFull(Q) 4)getFront(Q), 5)getRear(Q), 6)addFront(Q,x),
7)deleteFront(Q) 8) addRear(Q,x) 9)deleteRear(Q) .
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define size 5
int main()
{
int arr[size],R=-1,F=0,te=0,ch,n,i,x;
for(;;) // An infinite loop
{
system("cls"); // for clearing the screen
printf("F=%d R=%d\n\n",F,R);
printf("1. Add Rear\n");
printf("2. Delete Rear\n");
printf("3. Add Front\n");
printf("4. Delete Front\n");
printf("5. Display\n");
printf("6. Exit\n");
printf("Enter Choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
if(te==size)
{
printf("Queue is full");
getch(); // pause the loop to see the message
}
else
{
printf("Enter a number ");
scanf("%d",&n);
R=(R+1)%size;
arr[R]=n;
te=te+1;
}
break;
case 2:
if(te==0)
{
printf("Queue is empty");
getch(); // pause the loop to see the message
}
else
{
if(R==-1)
{
R=size-1;
}
printf("Number Deleted From Rear End = %d",arr[R]);
R=R-1;
te=te-1;
getch(); // pause the loop to see the number
}
break;
case 3:
if(te==size)
{
printf("Queue is full");
getch(); // pause the loop to see the message
}
else
{
printf("Enter a number ");
scanf("%d",&n);
if(F==0)
{
F=size-1;
}
else
{
F=F-1;
}
arr[F]=n;
te=te+1;
}
break;
case 4:
if(te==0)
{
printf("Queue is empty");
getch(); // pause the loop to see the message
}
else
{
printf("Number Deleted From Front End = %d",arr[F]);
F=(F+1)%size;
te=te-1;
getch(); // pause the loop to see the number
}
break;
case 5:
if(te==0)
{
printf("Queue is empty");
getch(); // pause the loop to see the message
}
else
{
x=F;
for(i=1; i<=te; i++)
{
printf("%d ",arr[x]);
x=(x+1)%size;
}
getch(); // pause the loop to see the numbers
}
break;
case 6:
exit(0);
break;
default:
printf("Wrong Choice");
getch(); // pause the loop to see the message
}
}
return 0;
}
No comments:
Post a Comment