5-1 Motivation: This project is to implement Priority Queue, using array or a co
ID: 3800015 • Letter: 5
Question
5-1 Motivation: This project is to implement Priority Queue, using array or a complete binary tree structure.
5-2 Requirements: You should name your Priority Queue class as PQ. The queue must be able to hold unlimited number of integers. It has two key operations: Push and Pop, which should have the time complexity of O(logn).
5-3 Files to turn in: You need to turn in four files: makefile, main.C, PQ.C, PQ.h. You should have a main.C that reads in or generates some integers, pushes them into the PQ one by one, and pops and prints them until the PQ is empty.
5-4 Grading The total points is 12, you will get full credit if you correctly implement it using tree structure, 6 points if you correctly implement it using array. The code must be compilable on Linux/Unix. Any code that cannot be compiled by g++ will automatically fail.
EDIT: The criteria to prioritize the queue, i.e the least element or the highest element, does not matter. As long as the perameters above are met, that is fine.
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
void push(int);
void pop(int);
void create();
void check(int);
void display_pqueue();
int pri_que[INT_MAX];
int front, rear;
void main()
{
int n, ch;
printf(" 1 - Insert an element into queue");
printf(" 2 - Delete an element from queue");
printf(" 3 - Display queue elements");
printf(" 4 - Exit");
create();
while (1)
{
printf(" Enter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf(" Enter value to be inserted : ");
scanf("%d",&n);
push(n);
break;
case 2:
printf(" Enter value to delete : ");
scanf("%d",&n);
pop(n);
break;
case 3:
display_pqueue();
break;
case 4:
exit(0);
default:
printf(" Choice is incorrect, Enter a correct choice");
}
}
}
/* Function to create an empty priority queue */
void create()
{
front = rear = -1;
}
/* Function to insert value into priority queue */
void push(int data)
{
if (rear >= MAX - 1)
{
printf(" Queue overflow no more elements can be inserted");
return;
}
if ((front == -1) && (rear == -1))
{
front++;
rear++;
pri_que[rear] = data;
return;
}
else
check(data);
rear++;
}
/* Function to check priority and place element */
void check(int data)
{
int i,j;
for (i = 0; i <= rear; i++)
{
if (data >= pri_que[i])
{
for (j = rear + 1; j > i; j--)
{
pri_que[j] = pri_que[j - 1];
}
pri_que[i] = data;
return;
}
}
pri_que[i] = data;
}
/* Function to delete an element from queue */
void pop(int data)
{
int i;
if ((front==-1) && (rear==-1))
{
printf(" Queue is empty no elements to delete");
return;
}
for (i = 0; i <= rear; i++)
{
if (data == pri_que[i])
{
for (; i < rear; i++)
{
pri_que[i] = pri_que[i + 1];
}
pri_que[i] = -99;
rear--;
if (rear == -1)
front = -1;
return;
}
}
printf(" %d not found in queue to delete", data);
}
/* Function to display queue elements */
void display_pqueue()
{
if ((front == -1) && (rear == -1))
{
printf(" Queue is empty");
return;
}
for (; front <= rear; front++)
{
printf(" %d ", pri_que[front]);
}
front = 0;
}
--------------------------------------------------------------------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.