I need help with implementing the priority queue data structure with a linked list implementation and with modifying my code with a template. Make sure that the code has the required methods to get the given test code in driver.cpp to work properly. I will provide the main cpp file and what I have so far below. The code is in C++. Add comments to where you modified the code, so I know what you did to change it. Thank you.

//////////////////////// driver.cpp /////////////////////////////

#include #include #include "stackLL.h" #include "queueLL.h" #include "priorityQueueLL.h" using namespace std;

int main() { /////////////Test code for stack /////////////// stackLL stk;

stk.push(5); stk.push(13); stk.push(7); stk.push(3); stk.push(2); stk.push(11);

cout << "Popping: " << stk.pop() << endl; cout << "Popping: " << stk.pop() << endl;

stk.push(17); stk.push(19); stk.push(23);

while (!stk.empty()) { cout << "Popping: " << stk.pop() << endl; }

// output order: 11,2,23,19,17,3,7,13,5

stackLL stkx;

stkx.push(5); stkx.push(10); stkx.push(15); stkx.push(20); stkx.push(25); stkx.push(30);

stkx.insertAt(-100, 3); stkx.insertAt(-200, 7); stkx.insertAt(-300, 0);

//output order: -300,30,25,20,-100,15,10,5,-200 while (!stkx.empty()) cout << "Popping: " << stkx.pop() << endl;

///////////////////////////////////////

//////////Test code for queue ///////////

queueLL Q;

Q.enqueue(1); Q.enqueue(2); Q.enqueue(3); cout << "Dequeuing: " << Q.dequeue() << endl; //1 cout << "Dequeuing: " << Q.dequeue() << endl; //2 Q.enqueue(4); Q.enqueue(5);

//3 4 5 while (!Q.empty()) { cout << "Dequeuing: " << Q.dequeue() << endl; }

/////////////////////////////////////////

//////////Test code for priority queue/////

priorityQueueLL pQueue;

const int SIZE = 20;

//insert a bunch of random numbers for (int i = 0; i < SIZE; i++) { pQueue.insert(rand()); }

//pull them back out.. //They must come out in order from smallest to largest while (!pQueue.empty()) { cout << pQueue.extractMin() << endl; }

priorityQueueLL pqs;

pqs.insert("whale"); pqs.insert("snake"); pqs.insert("buffalo"); pqs.insert("elmo"); pqs.insert("fire"); pqs.insert("waffle");

//buffalo elmo fire snake waffle whale while (!pqs.empty()) { cout << pqs.extractMin() << endl; }

/////////////////////////////////////////// //1) Template your queue class //2) Add a decimate method to your queue class queueLL qx;

for (int i = 1; i <= 100; i++) qx.enqueue(i);

//Eliminate every 10th item from list //https://en.wikipedia.org/wiki/Decimation_(punishment) qx.decimate();

//1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 21 22... 98 99 while (!qx.empty()) cout << qx.dequeue() << endl;

queueLL qy; qy.enqueue("sparticus"); qy.enqueue("maximus"); qy.enqueue("killicus"); qy.enqueue("awesomeicus"); qy.enqueue("gannicus"); qy.enqueue("varro"); qy.enqueue("oenomous"); qy.enqueue("slayicus"); qy.enqueue("bladeicus"); qy.enqueue("ted"); qy.enqueue("smashicus"); qy.enqueue("mallicus"); qy.enqueue("wussicus"); qy.enqueue("wimpicus"); qy.enqueue("crixus");

qy.decimate();

//Everyone but Ted. while (!qy.empty()) cout << qy.dequeue() << endl;

return 0; } //////////////////////// queueLL.h ///////////////////////////

#ifndef QUEUELL_H #define QUEUELL_H

class queueLL { private: //put what you need here...

public: queueLL() {}

~queueLL() {}

//return true if empty, false if not bool empty() {}

//add item to back of queue void enqueue(int x) {}

//remove and return first item from queue int dequeue() {}

//For the final part of the test program, template this class //and add a decimate method.

}; #endif ///////////////////////// queueLL.cpp //////////////////////////

#include "queueLL.h" #include

using namespace std;

class queueLL { private: class node { public: int data; node* next; node(int d, node* n = nullptr) : data(d), next(n) {} }; node* head; node* tail; public: queueLL() : head(nullptr), tail(nullptr) {} ~queueLL() { while (!empty()) { dequeue(); } }

bool empty() { return head == nullptr; }

void enqueue(int x) { node* new_tail = new node(x); if (empty()) { head = new_tail; } else { tail->next = new_tail; } tail = new_tail; }

int dequeue() { if (empty()) { throw std::out_of_range("Queue is empty"); } int ret = head->data; node* old_head = head; head = head->next; if (head == nullptr) { tail = nullptr; } delete old_head; return ret; }

void decimate() { node* current = head; node* prev = nullptr; int i = 1; while (current != nullptr) { if (i % 10 == 0) { if (prev == nullptr) { head = current->next; } else { prev->next = current->next; } node* next = current->next; delete current; current = next; } else { prev = current; current = current->next; } ++i; } tail = prev; } }; //////////////////////////// priorityQueueLL.h /////////////////////////////////

#ifndef PRIORITYQUEUELL_H #define PRIORITYQUEUELL_H

template class priorityQueueLL { private: class node { public: //put what you need here.. }

//add what you wish here

public:

priorityQueueLL() {}

~priorityQueueLL() {}

//return true if empty, false if not bool empty() {}

//add item void insert(T x) {}

//remove and return smallest item T extractMin() {}

}; #endif ///////////////////////////// priorityQueueLL.cpp ////////////////////////////////////

#include "priorityQueueLL.h" #include

using namespace std;

template class PriorityQueueLL { private: struct Node { T data; int priority; Node* next; Node(T d, int p) : data(d), priority(p), next(nullptr) {} }; Node* head; public: PriorityQueueLL() : head(nullptr) {} ~PriorityQueueLL() { while (head) { Node* temp = head; head = head->next; delete temp; } } void push(T data, int priority) { Node* newNode = new Node(data, priority); if (!head || priority > head->priority) { newNode->next = head; head = newNode; } else { Node* curr = head; while (curr->next && priority <= curr->next->priority) { curr = curr->next; } newNode->next = curr->next; curr->next = newNode; } }

void pop() { if (!head) { throw std::out_of_range("Priority queue is empty"); } Node* temp = head; head = head->next; delete temp; }

T top() const { if (!head) { throw std::out_of_range("Priority queue is empty"); } return head->data; }

bool empty() const { return head == nullptr; } };