C++ help 16.9 homework 5a : Priority Queue using Linked Lists Linked lists are o

ID: 3700907 • Letter: C

Question

C++ help

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 oData 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

//Apr_5_pg4PrioQue.h

#include<string>

#include<iostream>

using namespace std;

struct Node

{

string str;

int priority;

Node *next;

};

class Priority_queue

{

Node *head;

public:

//constructor

Priority_queue();

//destructor

~Priority_queue();

void insert(string s,int prio);

string peek();

void remove();

void display_queue();

};

--------------------------------------------------

//Apr_5_pg4PrioQue.cpp

#include"Apr_5_pg4PrioQue.h"

Priority_queue::Priority_queue()

{

head = NULL;

}

//destructor

Priority_queue::~Priority_queue()

{

Node *cur ;

while (head != NULL)

{

cur = head->next;

free(head);

head = cur;

}

void Priority_queue::insert(string s, int prio)

{

Node *cur = head, *newNode;

newNode = new Node;

newNode->str = s;

newNode->priority = prio;

newNode->next = NULL;

if (head != NULL && head->priority < prio)

{

newNode->next = head;

head = newNode;

}

else //traverse list and find position to insert

{

if (head == NULL)

{

head = newNode;

}

else

{

if(cur->next!=NULL)

while (cur->next != NULL && cur->next->priority > prio)

{

cur = cur->next;

}

newNode->next = cur->next;

cur->next = newNode;

}

string Priority_queue::peek()

{

cout << head->str << endl;

return head->str;

}

void Priority_queue::remove()

{

Node *cur = head->next;

free(head);

head = cur;

}

void Priority_queue::display_queue()

{

Node *cur = head;

while (cur != NULL)

{

cout<< cur->str<<endl;

cur = cur->next;

}

----------------------------------------------

//main.cpp

#include"Apr_5_pg4PrioQue.h"

int main()

{

Priority_queue que;

string s1, s2;

int prio;

{

cout << "Enter commands as string insert or remove or peek or quit to exit" << endl;

cin >> s1;

if (s1.compare("insert") == 0)

{

cin >> s2 >> prio;

que.insert(s2, prio);

continue;

}

if (s1.compare("remove") == 0)

{

//chk before removing

que.peek();

que.remove();

continue;

}

if (s1.compare("peek") == 0)

{

que.peek();

continue;

}

/*if (s1.compare("display") == 0)

{

que.display_queue();

continue;

}*/

if (s1.compare("quit") == 0)

{

cout << "Exiting..." << endl;

break;

}

} while (1);

}

/*output