Hi. I need help turning a queue into a priority queue. There is the customer and queue classes. Basically I need to change either the add_to_queue or the *take_off_queue in order to make it a priority queue. I am supposed to use the CPUburst time as the priority, as in shortest CPUburst gets highest priority. I am not very good with linked lists, since I have not had many experiences with them. This is what I was thinking: i would change the add_to_queue to make it traverse the list to find where to put the new value in order. How do I traverse the list? Could some people give me suggestions? Thanks in advance!
// Constructor
Cust::Cust()
{
arrive_time = 0;
CPUburst = 0;
cust_num = num;
num += 1;
}
Cust::Cust(long int time1, long int time2)
{
arrive_time = time1;
CPUburst = time2;
cust_num = num;
num += 1;
}
// Return the customer number
long int Cust::getnum() const {return cust_num;}
// Return the arrival time
long int Cust::getarrive() const {return arrive_time;}
// set the arrival time
void Cust::setarrive(long int time)
{
arrive_time = time;
}
// Return the CPUburst time
long int Cust::getCPUburst() const {return CPUburst;}
void Cust::setCPUburst(long int time)
{
CPUburst = time;
}
// Qnode Class definitions
//Constructor
Qnode::Qnode()
{
next = NULL;
custptr = NULL;
}
Qnode::Qnode(Cust *cp, Qnode *np)
{
custptr = cp;
next = np;
}
// return customer pointer of node
Cust *Qnode::getcust() const { return custptr; }
// Queue Class definitions
//Constructor
Queue::Queue()
{
head = NULL;
tail = NULL;
}
// Destructor
Queue::~Queue()
{
Cust *custptr;
Qnode *save, *ptr;
// traverse the queue and delete the customers and qnodes
ptr = head;
while(ptr != NULL)
{
custptr = ptr->getcust();
delete custptr;
save = ptr;
delete save;
ptr = ptr->next;
}
}
// returns true if queue is empty and false otherwise
int Queue::isempty() const {return (head == NULL);}
// add an element of type Cust to queue
void Queue::add_to_queue(Cust *ptr)
{
Qnode *newnode;
// get an new node
newnode = new Qnode(ptr, NULL);
// check to see if the queue is initially empty
if(tail == NULL)
{
head = newnode;
tail = newnode;
return;
}
// otherwise add it to the end of the queue and relink
tail->next = newnode;
tail = newnode;
return;
}
//return the top element from the queue
Cust *Queue::take_off_queue()
{
Qnode *ptr;
Cust *val;
// check if the queue is empty
if(head == NULL)
{
cout << " ***Error - queue underflow***\n";
return(NULL);
}
// remove top element from queue
ptr = head;
// get customer index
val = ptr->getcust();
// check if queue now empty and relink
if(head == tail)
{
tail = NULL;
head = NULL;
delete ptr;
return(val);
}
// otherwise just relink
head = ptr->next;
delete ptr;
return(val);
}
// print out the elements in the queue
void Queue::print()
{
Qnode *ptr;
ptr = head;
cout << "\nQueue contents ... ";
while (ptr != NULL) {
cout << "\nCust " << ptr->custptr->getnum();
cout << " => " << ptr->custptr->getarrive();
ptr = ptr->next;
}
}
Question
saiz66
Hi. I need help turning a queue into a priority queue. There is the customer and queue classes. Basically I need to change either the add_to_queue or the *take_off_queue in order to make it a priority queue. I am supposed to use the CPUburst time as the priority, as in shortest CPUburst gets highest priority. I am not very good with linked lists, since I have not had many experiences with them. This is what I was thinking: i would change the add_to_queue to make it traverse the list to find where to put the new value in order. How do I traverse the list? Could some people give me suggestions? Thanks in advance!
// Constructor Cust::Cust() { arrive_time = 0; CPUburst = 0; cust_num = num; num += 1; } Cust::Cust(long int time1, long int time2) { arrive_time = time1; CPUburst = time2; cust_num = num; num += 1; } // Return the customer number long int Cust::getnum() const {return cust_num;} // Return the arrival time long int Cust::getarrive() const {return arrive_time;} // set the arrival time void Cust::setarrive(long int time) { arrive_time = time; } // Return the CPUburst time long int Cust::getCPUburst() const {return CPUburst;} void Cust::setCPUburst(long int time) { CPUburst = time; } // Qnode Class definitions //Constructor Qnode::Qnode() { next = NULL; custptr = NULL; } Qnode::Qnode(Cust *cp, Qnode *np) { custptr = cp; next = np; } // return customer pointer of node Cust *Qnode::getcust() const { return custptr; } // Queue Class definitions //Constructor Queue::Queue() { head = NULL; tail = NULL; } // Destructor Queue::~Queue() { Cust *custptr; Qnode *save, *ptr; // traverse the queue and delete the customers and qnodes ptr = head; while(ptr != NULL) { custptr = ptr->getcust(); delete custptr; save = ptr; delete save; ptr = ptr->next; } } // returns true if queue is empty and false otherwise int Queue::isempty() const {return (head == NULL);} // add an element of type Cust to queue void Queue::add_to_queue(Cust *ptr) { Qnode *newnode; // get an new node newnode = new Qnode(ptr, NULL); // check to see if the queue is initially empty if(tail == NULL) { head = newnode; tail = newnode; return; } // otherwise add it to the end of the queue and relink tail->next = newnode; tail = newnode; return; } //return the top element from the queue Cust *Queue::take_off_queue() { Qnode *ptr; Cust *val; // check if the queue is empty if(head == NULL) { cout << " ***Error - queue underflow***\n"; return(NULL); } // remove top element from queue ptr = head; // get customer index val = ptr->getcust(); // check if queue now empty and relink if(head == tail) { tail = NULL; head = NULL; delete ptr; return(val); } // otherwise just relink head = ptr->next; delete ptr; return(val); } // print out the elements in the queue void Queue::print() { Qnode *ptr; ptr = head; cout << "\nQueue contents ... "; while (ptr != NULL) { cout << "\nCust " << ptr->custptr->getnum(); cout << " => " << ptr->custptr->getarrive(); ptr = ptr->next; } }Link to comment
Share on other sites
3 answers to this question
Recommended Posts