Priority Queue using Linked Lists(c++) Linked lists are one of the many \"linked
ID: 3722116 • Letter: P
Question
Priority Queue using Linked Lists(c++)
Linked lists are one of the many "linked" data structures that are used to store information. In this assignments, you will write a simple linked list class, and then use it to keep track of allocations and deallocations in a "heap" of memory. This homework has 2 problems.
Related HackerRank Problems
C++ -> Introduction -> Pointers
Data Structures -> Linked Lists -> Insert a node at a specific position
Data Structures -> Linked Lists -> Delete a node
Problem 5a : Priority Queue
A priority queue is a data structure in which objects can be inserted or removed. When an object is placed in the priority queue, it is added with a given priority value. When an object is removed, the object in the queue with the highest priority is removed. One simple way to implement a priority queue is to use a linked list.
Implement a priority queue for Strings using a linked list. Each string will have a priority associated with it. Note that you are required to implement a linked list to implement the priority queue. Submissions that do not use a linked list will get a score of 0.
Input will consist of a series of queries, which are one of the following:
add a string to the priority queue with a given priority
remove a string from the priority queue and print its value
The word "quit" will signal the end of the input.
Sample program run
Explanation / Answer
/*
* C++ Program to Implement Priority Queue
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int priority;
string info;
struct node *next;
};
/*
* Class Priority Queue
*/
class Priority_Queue
{
private:
node *front;
public:
Priority_Queue()
{
front = NULL;
}
/*
* Insert into Priority Queue
*/
void insert(string item, int priority)
{
node *tmp, *q;
tmp = new node;
tmp->info = item;
tmp->priority = priority;
if (front == NULL || priority < front->priority)
{
tmp->next = front;
front = tmp;
}
else
{
q = front;
while (q->next != NULL && q->next->priority <= priority)
q=q->next;
tmp->next = q->next;
q->next = 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->next;
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->next;
}
}
}
};
/*
* Main
*/
int main()
{
int choice, priority;
string item;
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 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;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.