Write Code In C++ 5-1 Motivation: This project is to implement Priority Queue, u

Question

Write Code In C++

5-1 Motivation: This project is to implement Priority Queue, using array or a complete binary tree structure. Details about priority queue can be found from http://www.cse.cuhk.edu.hk/~taoyf/course/2100sum11/lec8.pdf

5-2 Requirements: You should name your Prority 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. No late turn in is acceptable, any late turn in will be given 0 point. Your code must be compilable on Linux/Unix, any code that cannot be compiled by g++ will automatically get ZERO point.

Use This Main File:

#include <iostream>

#include "PQ.h"

#include <stdlib.h> /* for random number generation */

#include <time.h> /* time for random seed*/

using namespace std;

int main(){

PQ pq;

/* initialize random seed: */

srand (time(NULL));

for (int i = 1; i < 10; ++i) pq.Push(rand() % 100 + 1);

Node * p = pq.tail;

while(p != pq.head){

cout << p->val << endl;

p = p->prev;

}

for (int i = 0; i < 10; i++) cout << pq.Pop() << ", ";

}

Explanation / Answer

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

/*
* PQNode Declaration
*/
struct PQNode
{
   int priority;
   int info;
   struct PQNode *nextCell;
};
/*
* Class Priority Queue
*/
class PQ
{
private:
PQNode *head;
public:
PQ()
{
head = NULL;
}
/*
* push into Priority Queue
*/
void push(int item, int priority)
{
PQNode *tmp, *q;
tmp = new PQNode;
tmp->info = item;
tmp->priority = priority;
if (head == NULL || priority < head->priority)
{
tmp->nextCell = head;
head = tmp;
}
else
{
q = head;
while (q->nextCell != NULL && q->nextCell->priority <= priority)
q=q->nextCell;
tmp->nextCell = q->nextCell;
q->nextCell = tmp;
}
}
/*
* pop from Priority Queue
*/
void pop()
{
PQNode *tmp;
if(head == NULL)
cout<<"Queue Underflow ";
else
{
tmp = head;
cout<<"popeted item is: "<<tmp->info<<endl;
head = head->nextCell;
free(tmp);
}
}
/*
* Print Priority Queue
*/
void display()
{
PQNode *ptr;
ptr = head;
if (head == NULL)
cout<<"Queue is empty ";
else
{   cout<<"Queue is : ";
cout<<"Priority Item ";
while(ptr != NULL)
{
cout<<ptr->priority<<" "<<ptr->info<<endl;
ptr = ptr->nextCell;
}
}
}

       bool isEmpty(){
           bool returntype = false;
           PQNode *ptr;
ptr = head;
if (head == NULL)
cout<<"Queue is empty ";
           returntype = true;
       }
};
/*
* Main
*/
int main()
{
int choice;
   int item, priority;
PQ pq;
do
{
cout<<"1.push ";
cout<<"2.popete ";
cout<<"3.Display ";
       cout<<"4.isEmpty ";
cout<<"5.Quit ";
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Input the item value to be added in the queue : ";
cin>>item;
cout<<"Enter its priority : ";
cin>>priority;
pq.push(item, priority);
break;
case 2:
pq.pop();
break;
case 3:
pq.display();
break;
case 4:
           pq.isEmpty(pq);
break;
       case 5:
default :
cout<<"Wrong choice ";
}
}
while(choice != 5);
return 0;
}

Description : The above given code contains following contents or file

1. PQ ( PriorityQueue class )

2. main method : you can write seperate class and put the same method just like main.cpp

3. push , pop, display mehtod implementation as per defintion given in question.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.