Can someone write a C++ program that implements a priority queue of maximum leng
ID: 3667817 • Letter: C
Question
Can someone write a C++ program that implements a priority queue of maximum length 25. Use priorities ranging from 0 to 10 with the highest priority a 0. Prompt the user for a priority and a job name (a string), and allow the user to enter a -1 priority to quit entering jobs.
This exercise requires that you implement a function to insert a job anywhere in the queue, which must be implemented as a linked list. Do not remove any duplicates; that is, the same job can be entered multiple times with the same or different priorities.
After the user has quit entering priorities and jobs, print out the resulting queue from head to tail.
If you could add comments, explaining whats going on, it would be appreciated!
Explanation / Answer
// An example of simple priority queue using linked lists.
// Priority depends on identity number. Small identity number has greater priority.
// If identity numbers are equal. Then FIFO rules are used.
#include <iostream>
#include <cstring>
#include <iomanip>
using namespace std;
struct DAT
{
int id;
char jobname[50];
};
struct NODE
{
DAT data;
Node *N;
Node *P;
Node(const int i , const char *f)
{
data.id = i;
strcpy(data.jobname,f);
N = NULL;
P = NULL;
}
};
class PQueueLinkedList
{
private:
NODE *front;
NODE *back;
public:
PQueueLinkedList(){front = NULL;back = NULL;}
~PQueueLinkedList(){destroyList();}
void enqueue(NODE *);
NODE* dequeue();
void destroyList();
};
//adding elements into Prirorityhe Queue in the m of linked list
void PQueueLinkedList::enqueue(NODE *n)
{
if(front == NULL)//queue has one node.
{
front = n;
back = n;
}
else//queue has more than one node.
{
NODE* temp = front;
if( n->data.id > temp->data.id)//New node id's is greater than all others.
{
front->P = n;
n->N = front;
front = n;
}
else
{
//Search for the position for the new node.
while( n->data.id < temp->data.id)
{
if(temp->N == NULL)
break;
temp = temp->N;
}
//New node id's smallest than all others
if(temp->N == NULL && n->data.id < temp->data.id)
{
back->N = n;
n->P = back;
back = n;
}
else//New node id's is in the medium range.
{
temp->P->N = n;
n->P = temp->P;
n->N = temp;
temp->P = n;
}
}
}
}
//Based on user interest data will be deleted from Priority Queue
NODE* PQueueLinkedList::dequeue()
{
NODE *temp;
if( back == NULL )//no nodes
return NULL;
else if(back->P == NULL)//there is only one node
{
NODE * temp2 = back;
temp = temp2;
front = NULL;
back = NULL;
delete temp2;
return temp;
}
else//there are more than one node
{
NODE * temp2 = back;
temp = temp2;
back = back->P;
back->N = NULL;
delete temp2;
return temp;
}
}
//Here Priority list will be destroyed
void PQueueLinkedList::destroyList()
{
while(front != NULL)
{
NODE *temp = front;
front = front->N;
delete temp;
}
}
// display the what are the contents are there in Priority Queue
void disp(NODE *m)
{
if( m == NULL )
{
cout << " Queue is Empty!!!" << endl;
}
else
{
cout << " Id No. : " << m->data.id;
cout << " Job Name : " << m->data.jobname;
}
}
int main()
{
//Queue Intilization as in the form of Linked List
PQueueLinkedList *Queue = new PQueueLinkedList();
// add the each node with id and job name
NODE No1( 101, "Clerk" );
NODE No2( 102, "Manager");
NODE No3( 103, "Supervisor");
NODE No4( 104, "Attender");
NODE No5(105,"Assist Manager");
// simiilarly you can add up to 25 members
// add nodes into Priority Queue
Queue->enqueue(&No5);
Queue->enqueue(&No4);
Queue->enqueue(&No3);
Queue->enqueue(&No1);
Queue->enqueue(&No2);
// display nodes from Prirorty Queue
disp(Queue->dequeue());
disp(Queue->dequeue());
disp(Queue->dequeue());
disp(Queue->dequeue());
disp(Queue->dequeue());
delete Queue;
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.