Implement a priority queue using a doublyLinked.cpp where the node with the highest priority (key) is the right-most node. The remove (de-queue) operation returns the node with the highest priority (key). If displayForward() displays List (first-->last) : 10 30 40 55 remove() would return the node with key 55.

please only code in c++ not anything else. keep it simple and thank you!!

Demonstrate by inserting keys at random, displayForward(), call remove then displayForward() again. int main() { DoublyLinkedList pqList; pqList.priorityInsert(50); pqList.priorityInsert(40); pqList.priorityInsert(30); pqList.priorityInsert(20); pqList.priorityInsert(10); cout<<"-------------- PriorityQueue -------------"<Sample output" -------------- PriorityQueue ------------- List (first-->last): 10 20 30 40 50 calling priorityRemove() Removed node with key 50 List (first-->last): 10 20 30 40 Removed node with key 40 List (first-->last): 10 20 30 I may change numbers when grading.

doublyLinked.cpp

//doublyLinked.cpp //demonstrates doubly-linked list

#include

using namespace std;

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

class Link {

public: double dData; //data item

Link * pNext; //next link in list Link * pPrevious; //previous link in list public: //------------------------------------------------------------- Link(double dd): //constructor dData(dd), pNext(NULL), pPrevious(NULL) {} //------------------------------------------------------------- void displayLink() //display this link { cout << dData << " "; } //------------------------------------------------------------- }; //end class Link //////////////////////////////////////////////////////////////// class DoublyLinkedList { private: Link * pFirst; //pointer to first item Link * pLast; //pointer to last item public: //------------------------------------------------------------- DoublyLinkedList(): //constructor pFirst(NULL), pLast(NULL) {} //------------------------------------------------------------- ~DoublyLinkedList() //destructor (deletes links) { Link * pCurrent = pFirst; //start at beginning of list while (pCurrent != NULL) //until end of list, { Link * pOldCur = pCurrent; //save current link pCurrent = pCurrent -> pNext; //move to next link delete pOldCur; //delete old current } } //------------------------------------------------------------- bool isEmpty() //true if no links { return pFirst == NULL; } //------------------------------------------------------------- void insertFirst(double dd) //insert at front of list { Link * pNewLink = new Link(dd); //make new link if (isEmpty()) //if empty list, pLast = pNewLink; //newLink <-- last else pFirst -> pPrevious = pNewLink; //newLink <-- old first pNewLink -> pNext = pFirst; //newLink --> old first pFirst = pNewLink; //first --> newLink } //------------------------------------------------------------- void insertLast(double dd) //insert at end of list {

Link * pNewLink = new Link(dd); //make new link

if (isEmpty()) //if empty list, pFirst = pNewLink; //first --> newLink else {

pLast -> pNext = pNewLink; //old last --> newLink

pNewLink -> pPrevious = pLast; //old last <-- newLink

} pLast = pNewLink; //newLink <-- last

} //------------------------------------------------------------- void removeFirst() //remove first link { //(assumes non-empty list)

Link * pTemp = pFirst;

if (pFirst -> pNext == NULL) //if only one item pLast = NULL; //null <-- last else pFirst -> pNext -> pPrevious = NULL; //null <-- old next pFirst = pFirst -> pNext; //first --> old next

delete pTemp; //delete old first

} //------------------------------------------------------------- void removeLast() //remove last link { //(assumes non-empty list)

Link * pTemp = pLast;

if (pFirst -> pNext == NULL) //if only one item pFirst = NULL; //first --> null else pLast -> pPrevious -> pNext = NULL; //old previous --> null pLast = pLast -> pPrevious; //old previous <-- last

delete pTemp; //delete old last

} //------------------------------------------------------------- //insert dd just after key bool insertAfter(double key, double dd) { //(assumes non-empty list)

Link * pCurrent = pFirst; //start at beginning

while (pCurrent -> dData != key) //until match is found, {

pCurrent = pCurrent -> pNext; //move to next link

if (pCurrent == NULL) return false; //didnt find it } Link * pNewLink = new Link(dd); //make new link if (pCurrent == pLast) //if last link, { pNewLink -> pNext = NULL; //newLink --> null pLast = pNewLink; //newLink <-- last } else //not last link, { //newLink --> old next pNewLink -> pNext = pCurrent -> pNext; //newLink <-- old next pCurrent -> pNext -> pPrevious = pNewLink; } pNewLink -> pPrevious = pCurrent; //old current <-- newLink pCurrent -> pNext = pNewLink; //old current --> newLink return true; //found it, did insertion } //------------------------------------------------------------- bool removeKey(double key) //remove item w/ given key { //(assumes non-empty list) Link * pCurrent = pFirst; //start at beginning while (pCurrent -> dData != key) //until match is found, { pCurrent = pCurrent -> pNext; //move to next link if (pCurrent == NULL) return false; //didnt find it } if (pCurrent == pFirst) //found it; first item? pFirst = pCurrent -> pNext; //first --> old next else //not first //old previous --> old next pCurrent -> pPrevious -> pNext = pCurrent -> pNext; if (pCurrent == pLast) //last item? pLast = pCurrent -> pPrevious; //old previous <-- last else //not last //old previous <-- old next pCurrent -> pNext -> pPrevious = pCurrent -> pPrevious; delete pCurrent; //delete item return true; //successful deletion } //------------------------------------------------------------- void displayForward() { cout << "List (first-->last): "; Link * pCurrent = pFirst; //start at beginning while (pCurrent != NULL) //until end of list, { pCurrent -> displayLink(); //display data pCurrent = pCurrent -> pNext; //move to next link } cout << endl; } //------------------------------------------------------------- void displayBackward() {

cout << "List (last-->first): ";

Link * pCurrent = pLast; //start at end

while (pCurrent != NULL) //until start of list, {

pCurrent -> displayLink(); //display data

pCurrent = pCurrent -> pPrevious; //go to previous link

} cout << endl;

} //------------------------------------------------------------- }; //end class DoublyLinkedList ////////////////////////////////////////////////////////////////

int main() {

DoublyLinkedList theList; //make a new list theList.insertFirst(22); //insert at front theList.insertFirst(44);

theList.insertFirst(66); theList.insertLast(11); //insert at rear theList.insertLast(33);

theList.insertLast(55); theList.displayForward(); //display list forward theList.displayBackward(); //display list backward cout << "Deleting first, last, and 11" << endl; theList.removeFirst(); //remove first item

theList.removeLast(); //remove last item

theList.removeKey(11); //remove item with key 11 theList.displayForward(); //display list forward

cout << "Inserting 77 after 22, and 88 after 33" << endl; theList.insertAfter(22, 77); //insert 77 after 22

theList.insertAfter(33, 88); //insert 88 after 33 theList.displayForward(); //display list forward return 0; } //end main()

Program 5 to test the code and call it.

#include "doublyLinked2.cpp" #include using namespace std;

int main() {

DoublyLinkedList pqList;

pqList.priorityInsert(50); pqList.displayForward();

pqList.priorityInsert(80); pqList.displayForward();

pqList.priorityInsert(40); pqList.displayForward();

pqList.priorityInsert(30); pqList.priorityInsert(20); pqList.priorityInsert(10); pqList.priorityInsert(70); pqList.priorityInsert(24); cout<<"-------------- PriorityQueue -------------"<

cout<<" calling priorityRemove()"<

return 0; }