PriorityQueue Class Implemented with a Linked List You will implement and test a

Question

PriorityQueue Class Implemented with a Linked List

You will implement and test a PriorityQueue class, where the items of the priority queue are stored on a linked list. The Node struct for this linked list must be defined in your header file for the priority queue rather than in a separate header file. All of the PriorityQueue member functions should be written by you from scratch (not using the linked list toolkit). Note: This is not a template class; you will use a typedef statement to define the underlying data type. Files that you must write: 1. pqueue1.h: The header file for this first version of the PriorityQueue class. Actually, you don't have to write much of this file. Just copy the attached version from pqueue1.h and add your name and other information at the top. If some of your member functions are implemented as inline functions, then you may put those implementations in this file too. 2. pqueue1.cxx: The implementation file for the PriorityQueue class. You will write all of this file, which will have the implementations of all the PriorityQueue's member functions. Also, remember that the PriorityQueue's linked list consists of dynamic memory, so you will need to define a copy constructor, an assignment operator, and a destructor. 3. A simple program to verify your solution. Discussion of the problem: You will store the items on a linked list, where each node contains both an item and the item's priority, as shown here: struct Node { // Note: Item is defined with a typedef in the PriorityQueue class PriorityQueue::Item data; unsigned int priority; Node *link; }; This Node definition appears in the header file pqueue1.h, immediately after the PriorityQueue class definition. Neither class needs to be a template class (instead, the Item type is defined as an int by using a typedef within the PriorityQueue class definition). All the items are stored on a single linked list. I suggest that you maintain the linked (create a radixSort function to be called when needed) list in order from highest to lowest priority. If there are several items with equal priority, then the one that came in first will be in front of the others. Because the linked list is kept in order, the get_front operation is simple. It merely gets the head item of the linked list. On the other hand, the insert operation requires some amount of work, making sure that the new entry goes at the correct spot in the linked list. A new entry must go after any existing entries with a higher or equal priority. You must also implement an insertEnd operation (function) which will insert a new entry at the end of the queue.

Explanation / Answer

/*
* Here is your program implementing Priority Queue
I have also given you another program down below for your reference. */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

/*
* Node Declaration
*/
struct node
{
   int priority;
   int info;
   struct node *link;
};
/*
* Class Priority Queue
*/
class Priority_Queue
{
private:
node *front;
public:
Priority_Queue()
{
front = NULL;
}
/*
* As you asked to the Insert into Priority Queue
*/
void insert(int item, int priority)
{
node *tmp, *q;
tmp = new node;
tmp->info = item;
tmp->priority = priority;
if (front == NULL || priority < front->priority)
{
tmp->link = front;
front = tmp;
}
else
{
q = front;
while (q->link != NULL && q->link->priority <= priority)
q=q->link;
tmp->link = q->link;
q->link = tmp;
}
}
/*
* Delete from Priority Queue
*/
void del()
{
node *tmp;
if(front == NULL)
cout<<"Queue Underflow ";
else
{
tmp = front;
cout<<"Deleted item is: "<<tmp->info<<endl;
front = front->link;
free(tmp);
}
}
/*
* Print Priority Queue
*/
void display()
{
node *ptr;
ptr = front;
if (front == NULL)
cout<<"Queue is empty ";
else
{   cout<<"Queue is : ";
cout<<"Priority Item ";
while(ptr != NULL)
{
cout<<ptr->priority<<" "<<ptr->info<<endl;
ptr = ptr->link;
}
}
}
};
/*
* Main
*/
int main()
{
int choice, item, priority;
Priority_Queue pq;
do
{
cout<<"1.Insert ";
cout<<"2.Delete ";
cout<<"3.Display ";
cout<<"4.Quit ";
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Input the item value to be added in the queue : ";
cin>>item;
cout<<"Enter its priority : ";
cin>>priority;
pq.insert(item, priority);
break;
case 2:
pq.del();
break;
case 3:
pq.display();
break;
case 4:
break;
default :
cout<<"Wrong choice ";
}
}
while(choice != 4);
return 0;
}

Output:

Enter your choice : 1
Input the item value to be added in the queue : 4
Enter its priority : 2
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Input the item value to be added in the queue : 3
Enter its priority : 3
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Input the item value to be added in the queue : 2
Enter its priority : 4
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Input the item value to be added in the queue : 1
Enter its priority : 5
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 3
Queue is :
Priority Item
1 5
2 4
3 3
4 2
5 1
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 2
Deleted item is: 5
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 3
Queue is :
Priority Item
2 4
3 3
4 2
5 1
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 4

This is another program for implementing priority queue with different logic.

// 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 fullname[50];
double salary;
};

struct NODE
{
DAT data;
Node *N;
Node *P;
Node(const int i , const char *f, const double s )
{
data.id = i;
strcpy(data.fullname,f);
data.salary = s;
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();
};

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

}
}

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

void PQueueLinkedList::destroyList()
{
while(front != NULL)
{
NODE *temp = front;
front = front->N;
delete temp;
}
}

void disp(NODE *m)
{
if( m == NULL )
{
cout << " Queue is Empty!!!" << endl;
}
else
{
cout << " Id No. : " << m->data.id;
cout << " Full Name : " << m->data.fullname;
cout << " Salary : " << setprecision(15) << m->data.salary << endl;
}
}

int main()
{
PQueueLinkedList *Queue = new PQueueLinkedList();

NODE No1( 101, "Aaaaa Nnnnnnn Mmmmm", 123456.4758 );
NODE No2( 102, "Bbbbb Ddddd Ssssss", 765432.9488 );
NODE No3( 103, "wwww nnnnn www eeee", 366667.3456 );
NODE No4( 104, "Bsrew hytre dfresw", 9876544.0432 );

Queue->enqueue(&No4);
Queue->enqueue(&No3);
Queue->enqueue(&No1);
Queue->enqueue(&No2);

disp(Queue->dequeue());

disp(Queue->dequeue());

disp(Queue->dequeue());

disp(Queue->dequeue());

disp(Queue->dequeue());

delete Queue;
return 0;
}

Program's output
**********************
Id No. : 101
Full Name : Aaaaa Nnnnnnn Mmmmm
Salary : 123456.4758

Id No. : 102
Full Name : Bbbbb Ddddd Ssssss
Salary : 765432.9488

Id No. : 103
Full Name : wwww nnnnn www eeee
Salary : 366667.3456

Id No. : 104
Full Name : Bsrew hytre dfresw
Salary : 9876544.0432

Queue is Empty!!!

Process returned 0 (0x0) execution time : 0.015 s
Press any key to continue.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.