CODE MUST BE WRITTEN IN C++!!!!!!!! Implement a priority queue, using array or a
ID: 3863258 • Letter: C
Question
CODE MUST BE WRITTEN IN C++!!!!!!!!
Implement a priority queue, using array or a complete binary tree structure.
You should name your priority queue class PQ
The queue must be able to hold an unlimited number of integers.
It must have two key operations:
Push and pop with the time complexity of O(logn)
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.
Code must be compliable on linux/unix.
Explanation / Answer
main file::
#include<iostream>
#include<cstdlib>
using namespace std;
struct node{
int info;
struct node *next;
};
class PQ{
private:
node *rear;
node *front;
public:
PQ();
void enqueue();
void dequeue();
void display();
};
PQ::PQ(){
rear = NULL;
front = NULL;
}
void PQ::enqueue(){
int data;
node *temp = new node;
cout<<"Enter the data to enqueue: ";
cin>>data;
temp->info = data;
temp->next = NULL;
if(front == NULL){
front = temp;
}else{
rear->next = temp;
}
rear = temp;
}
void PQ::dequeue(){
node *temp = new node;
if(front == NULL){
cout<<" Queue is Emtpty ";
}else{
temp = front;
front = front->next;
cout<<"The data Dequeued is "<<temp->info;
delete temp;
}
}
void PQ::display(){
node *p = new node;
p = front;
if(front == NULL){
cout<<" Nothing to Display ";
}else{
while(p!=NULL){
cout<<endl<<p->info;
p = p->next;
}
}
}
int main(){
PQ queue;
int a[100],n;
cout<<"enter limit";cin>>n;
cout<<"enter integers";
for(int i=0;i<n;i++)
{cin>>a[i];
int choice;
while(true){
cout<<" 1.Enqueue 2. Dequeue 3. Display 4.Quit";
cout<<" Enter your choice: ";
cin>>choice;
switch(choice){
case 1:
queue.enqueue(a[i]);
//here if poping also reguired then give ...goto dequeue functn here
break;
case 2:
queue.dequeue(a[i]);
break;
case 3:
queue.display(a[i]);
break;
case 4:
exit(0);
break;
default:
cout<<" Invalid Input. Try again! ";
break;
}
}
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.