[C++] Turning a queue into a priority queue

[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;
  }
	}

[GPSnoopy]

#include <queue>

std::priority_queue

[kjordan2001]

#include <queue>

std::priority_queue

I doubt he gets to use that.

You would do it similarly to the Delete function. It goes through the queue. You use ptr->next to get the next one in the queue.

[saiz66]

thanks guys.. i got it!!!!