Question

Complete the following TODO: parts of the code in C++

#include <iostream>

#include <string>

#include <limits>

#include <vector>

using namespace std;

//

// CLASS: NODE

//

class Node{

public:

int value = 0; // our node holds an integer

Node *next = nullptr; // our node has a pointer to the next Node

Node(int i){ // contructor for our Node class

value = i; // store a copy of argument "i" in "value"

next = nullptr; // be sure next Node is null

}

}; // end class definition for Node

//

// CLASS: MAX PRIORITY QUEUE

//

class MaxPriorityQueueLinkedList{

private:

Node *head = nullptr;

int currentSize = 0; // # of items in the heap, also next avaialble stack position

public:

MaxPriorityQueueLinkedList(){ // constructor

//cout << "Created new Max Priority Queue." << endl;

currentSize = 0;

head = nullptr;

}

//

// PUSH - push a new Node instance into the Priority Queue

//

void push(int i){

Node *temp = new Node(i); // create a node with i as the value

// TODO: write your implementation of push here

void push(int i){

// don't forget to manage the "currentSize" value

} // end push()

//

// POP - remove an existing Node instance with the largest value from the Priority Queue

//

int pop(){ // remove the Node with the largest value from the PQ

// TODO:

// Write your implementation of pop here

// You will need to search the queue rooted at "head" to find the largest value

// Don't forget to manage the "currentSize" value when you pop the Node

// Don't forget to return -1 if your queue is empty

// Otherwise you must return the value of the item you just popped (don't return the Node)

// Don't forget to delete the Node you pop before returning, like:

// Node *temp; // declaration of a pointer to the node that you be deleting

// delete temp; // deletes the Node pointed to by "temp"

Answer 1

Program:

#include <iostream>
#include <string>
#include <limits>
#include <vector>

using namespace std;

//
// CLASS: NODE
//
class Node{
public:
int value = 0; // our node holds an integer
Node *next = nullptr; // our node has a pointer to the next Node
Node(int i){ // contructor for our Node class
value = i; // store a copy of argument "i" in "value"
next = nullptr; // be sure next Node is null
}
}; // end class definition for Node

//
// CLASS: MAX PRIORITY QUEUE
//
class MaxPriorityQueueLinkedList{
private:
Node *head = nullptr;
int currentSize = 0; // # of items in the heap, also next available stack position
public:
MaxPriorityQueueLinkedList(){ // constructor
cout << "Created new Max Priority Queue." << endl;
currentSize = 0;
head = nullptr;
}
//
// PUSH - push a new Node instance into the Priority Queue
//
void push(int i){
Node *temp = new Node(i); // create a node with i as the value
// check if your queue is empty
if(currentSize==0)
head = temp;
else{
temp->next=head;
head = temp;
}
//increase currentSize
currentSize++;
} // end push()

//
// POP - remove an existing Node instance with the largest value from the Priority Queue
//
int pop(){ // remove the Node with the largest value from the PQ
// check if your queue is empty
if(currentSize==0)
return -1;

// declaration of a pointer to the node
Node *temp = head;

//search the queue to find the largest value
int maxm = temp->value;
while(temp!=nullptr){
if(temp->value > maxm)
maxm = temp->value;
temp = temp->next;
}

temp = head;
//if the largest value found at head
if(head->value==maxm)
{
head = head->next;
}
//if the largest value found other than head
else
{
Node *p=nullptr;
while(temp->value!=maxm){
p = temp;
temp = temp->next;
}
p->next = temp->next;
}
//decrease currentSize
currentSize--;
// deletes the Node pointed to by "temp"
delete temp;
//return the largest value
return maxm;
} // end pop()
}; // end class definition for MaxPriorityQueueLinkedList

//main function
int main()
{
//create object of MaxPriorityQueueLinkedList
MaxPriorityQueueLinkedList pq;

//insert to the PQ
pq.push(7);
pq.push(4);
pq.push(2);
pq.push(3);
pq.push(8);

//remove from PQ
cout<<"Remove largest value from the PQ : " << pq.pop() << endl;
cout<<"Remove largest value from the PQ : " << pq.pop() << endl;
cout<<"Remove largest value from the PQ : " << pq.pop() << endl;
cout<<"Remove largest value from the PQ : " << pq.pop() << endl;
cout<<"Remove largest value from the PQ : " << pq.pop() << endl;
cout<<"Remove largest value from the PQ : " << pq.pop() << endl;

return 0;
}

Output:

Solving your question and helping you to well understand it is my focus. So if you face any difficulties regarding this please let me know through the comments. I will try my best to assist you. However if you are satisfied with the answer please don't forget to give your feedback. Your feedback is very precious to us, so don't give negative feedback without showing proper reason.
Always avoid copying from existing answers to avoid plagiarism.
Thank you.