Write Code In C++ 5-1 Motivation: This project is to implement Priority Queue, u
ID: 3860215 • Letter: W
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
/*
* C++ Program to Implement Priority Queue
In this code item with its priority is inserted in linked list.
Randomly 10 items are inserted and displayed.
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
struct node
{
int priority;
int info;
struct node *link;
};
class Priority_Queue
{
private:
node *front;
public:
Priority_Queue()
{
front = NULL;
}
void push(int item, int priority)
{
node *tmp, *q;
tmp = new node;
tmp->info = item;
tmp->priority = priority;
if (front == NULL || priority < front->priority)
{
tmp->link = front;
front = tmp;
}
else
{
q = front;
while (q->link != NULL && q->link->priority <= priority)
q=q->link;
tmp->link = q->link;
q->link = tmp;
}
}
void del()
{
node *tmp;
if(front == NULL)
cout<<"Queue Underflow ";
else
{
tmp = front;
cout<<"Deleted item is: "<<tmp->info<<endl;
front = front->link;
free(tmp);
}
}
/*
node* pop()
{
if (front == NULL)
{
cout<<"Queue is empty ";
return NULL;
}
node *temp=front;
node *ptr=front;
front=front->link;
delete(temp);
return ptr;
}
*/ void display()
{
node *ptr;
ptr = front;
if (front == NULL)
cout<<"Queue is empty ";
else
{ cout<<"Queue is : ";
cout<<"Priority Item ";
while(ptr != NULL)
{
cout<<ptr->priority<<" "<<ptr->info<<endl;
ptr = ptr->link;
}
}
}
};
/*
* Main
*/
int main()
{
int choice, item, priority;
Priority_Queue pq;
for (int i = 1; i < 10; ++i) pq.push(rand() % 100 + 1,rand()%100+1);
cout<<"All elements with teir random priority : ";
pq.display();
// for(int i=0;i<10;i++)
// cout<<pq.pop()->info<<",";
//cout<<" ";
return 0;
}
//Output :
G580:~/codes$ g++ new_p.cpp
G580:~/codes$ ./a.out
All elements with teir random priority :
Queue is :
Priority Item
41 27
50 22
63 28
64 27
78 16
84 87
87 93
91 60
94 36
G580:~/codes$
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.