Implement a priority queue capable of determining the order in which a group of
ID: 3586630 • Letter: I
Question
Implement a priority queue capable of determining the order in which a group of people should be admitted to a concert based off of the number designated on their ticket. The highest priority should be given to those individuals with the lowest ticket numbers. Your program should read a file containing ticket information and print the order in which individuals should be admitted into the concert. Be careful, the ticket numbering system sometimes prints duplicates. If this case should arise both guests will be admitted into the concert. The guest who arrived first (listed first in the file) will receive a higher priority, and so on.
Output from your program should match the example demonstrated at the end of this file.
Your priority queue should be written using a C++ class, named PQueue, and the queue itself should be implemented as a linked list similar to queues/stacks.
The following classes should be defined by your program:
class Person : Used to store information about each person (ticket # and name)
class PQueue : Priority queue used to serve people
The following public functions need to be implemented:
Person::Person( int, string ): Initialize the person
PQueue::PQueue( void ) : Initialize the priority queue
bool PQueue::empty( void ) : Test whether queue is empty
int PQueue::size( void ): Return size
Person* PQueue::front( void ): Access node at front of queue
Person* PQueue::back( void ): Access node at end of queue
void PQueue::enqueue( Person* ) : Insert node into proper location in queue
void PQueue::dequeue( void ) : Remove node from front of queue
** Do not change names.
It will need to read information from a file. The file will be structured as follows:
int string
It will contain a variable number lines and each line will consist of an integer representing the ticket number followed by one space followed by a string representing the ticketholder’s name. The ticket number should be used to designate the priority assigned to the ticketholder.
Example:
$ cat input.txt
1 Billy
4 Mary
2 Jack
3 Shawn
$ ./a.out
Admitting Billy..
Admitting Jack..
Admitting Shawn..
Admitting Mary..
Explanation / Answer
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <fstream>
using namespace std;
/*
* Node Declaration
*/
class Person
{
public:
int ticketNo;
string name;
Person *link;
Person(int ticket, string nam)
{
name = nam;
ticketNo = ticket;
}
};
/*
* Class Priority Queue
*/
class PQueue
{
private:
Person *frontP;
int sizeN;
public:
PQueue()
{
frontP = NULL;
sizeN=0;
}
/*
* Insert into Priority Queue
*/
void enqueue(Person* person)
{
Person *tmp, *q;
int ticketNo = person->ticketNo;
tmp = new Person(ticketNo, person->name);
if (frontP == NULL || ticketNo < frontP->ticketNo)
{
tmp->link = frontP;
frontP = tmp;
}
else
{
q = frontP;
while (q->link != NULL && q->link->ticketNo <= ticketNo)
q=q->link;
tmp->link = q->link;
q->link = tmp;
}
sizeN++;
}
/*
* Delete from Priority Queue
*/
void del()
{
Person *tmp;
if(frontP == NULL)
cout<<"Queue Underflow ";
else
{
tmp = frontP;
cout<<"Deleted person is: "<<tmp->name<<endl;
frontP = frontP->link;
free(tmp);
}
sizeN--;
}
/*
* Print Priority Queue
*/
void display()
{
Person *ptr;
ptr = frontP;
if (frontP == NULL)
cout<<"Queue is empty ";
else
{
while(ptr != NULL)
{
cout<<"Admitting "<<ptr->name<<" ";
ptr = ptr->link;
}
}
}
bool empty()
{
if(frontP==NULL)
return true;
else
return false;
}
int size()
{
return sizeN;
}
Person* front()
{
return frontP;
}
Person* back()
{
Person *ptr;
ptr = frontP;
while(ptr != NULL)
{
ptr = ptr->link;
}
return ptr;
}
};
/*
* Main
*/
int main()
{
PQueue* obj = new PQueue();
ifstream infile("thefile.txt");
int a;
string b;
while (infile >> a >> b)
{
Person* person = new Person(a,b);
obj->enqueue(person);
}
obj->display();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.