16.9 homework 5a : Priority Queue using Linked Lists Linked lists are one of the
ID: 3700454 • Letter: 1
Question
16.9 homework 5a : Priority Queue using Linked Lists 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 o C+Introduction>Pointers ° Data Structures-> Linked Lists-> Insert a node at a specific position o 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 O Input will consist of a series of queries, which are one of the following: 1. add a string to the priority queue with a given priority 2. remove a string from the priority queue and print its value The word "quit" will signal the end of the input.Explanation / Answer
#include <iostream>
#include <string>
using namespace std;
//Node structure
struct prioritynode
{
string s;
int priority; // lower the value higher the priority
struct prioritynode* next;
}Node;
prioritynode* newNode(string str, int prior) //Create A New Node
{
struct prioritynode *temp = new prioritynode;
temp->s = str;
temp->priority = prior;
temp->next = NULL;
return temp;
}
string atHead(struct prioritynode** head) // return value at head
{
return (*head)->s;
}
void pop(struct prioritynode** head) // remove the highest priority node and delete it from memory
{
cout<<(*head)->s;
struct prioritynode* temp = *head;
(*head) = (*head)->next;
delete[] temp;
}
void push(struct prioritynode** head, string str, int p) // push new node
{
struct prioritynode* start = (*head);
struct prioritynode* temp = newNode(str, p);
if ((*head)->priority > p)
{
// Insert New Node before head
temp->next = *head;
(*head) = temp;
}
else
{ while (start->next != NULL && start->next->priority < p) // find the place where to put new node
{
start = start->next;
}
temp->next = start->next; // at required position
start->next = temp;
}
}
bool isEmpty(struct prioritynode** head) //check the list if empty
{
return (*head) == NULL;
}
int main()
{
struct prioritynode* Node;
string str, command;
int p;
cout<<"Enter input by writing input followed by the string and priority : write quit to quit ."<<endl;
cin>>command;
cin>>str;
cin>>p;
do
{
if(command == "input") //To input a string
{ struct prioritynode* n = newNode(str, p);
push(&n, str, p);
}
else if(command=="remove") //To remove a string
pop(&Node);
cin>>command;
}while(command!="quit");
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.