DATA STRUCTURES AND ALGORTHIMS

ANSWER ASAP

LET FINAL CODE BE INSERT IN GIVEN CODE

In this assignment, you will simulate the children's game of "Hot Potato" using a Queue. The game is simulated as follows: To begin with, you can enqueue a total of 'n' names (strings) to the Queue and then subject the Queue to n-1 iterations. In each iteration, you rotate the Queue 'm' number of times. In one rotation: you dequeue the string at the front of the Queue and enqueue at the end of the Queue. After 'm' rotations, the string at the front of the Queue is permanently dequeued and is considered out of the game. The Queue will now have n-1 stringsames. You continue the above process of subjecting the Queue to 'm' rotations and dequeue the string at the front of the Queue after the mth rotation, leaving the Queue with n-2 strings. The process is repeated until the Queue has just one string. The name corresponding to that string is declared as the winner of the game. Below, I illustrate the game by starting with a total of n = 5 strings and subjecting them m = 3 rotations before permanently dequeuing a string from the Queue. Initialization: John ---- Peter ---- Kyra ---- Thomas ---- Rena Iteration 1: Rotation 1: Peter ---- Kyra ---- Thomas ---- Rena ---- John Rotation 2: Kyra ---- Thomas ---- Rena ---- John ---- Peter Rotation 3 : Thomas ---- Rena ---- John ---- Peter ---- Kyra Permanent Dequeue: Thomas is out of the game Queue (after the permanent Dequeue): Rena ---- John ---- Peter ---- Kyra Iteration 2: Rotation 1: John ---- Peter ---- Kyra ---- Rena Rotation 2: Peter ---- Kyra ---- Rena ---- John Rotation 3: Kyra - ---- Rena ---- John ---- Peter Permanent Dequeue: Kyra is out of the game Queue (after the permanent Dequeue): Rena ---- John ---- Peter Iteration 3: Rotation 1: John ---- Peter ---- Rena Rotation 2: Peter ---- Rena - John Rotation 3: Rena ---- John ---- Peter Permanent Dequeue: Rena is out of the game Queue (after the permanent Dequeue): John ----Peter Iteration 4: Rotation 1: Peter ---- John Rotation 2: John --- Peter Rotation 3: Peter ---- John Permanent Dequeue: Peter is out of the game Queue (after the permanent Dequeue): John Winner: John You are provided a doubly linked list-based implementation of the Queue ADT that can enqueue and dequeue strings. The main function is written to setup the Queue with a total of queue Size' number (n) of strings input by the user, one string at a time. The main function then calls the Print function and passes the Queue as the argument to print the contents of the Queue. Likewise, there is a getQueuel.ength function (that takes the Queue as the argument) provided for you to return the length of the Queue. The main function also inputs the rotation Number, which is the number of rotations (m) per iteration You will extend the code for the main function from now on by simulating the Hot Potato game, as illustrated above. After the permanent dequeue operation at the end of each iteration, your code should print who is out of the game and print the latest contents of the queue. A sample screenshot of the Queue with the five names illustrated in the above example is shown below. Enter the number of elements you want to enqueue: 5 Elements enqueued Enter string 1 : John Enter string 2 : Peter Enter string 3: Kyra Enter string 4: Thomas Enter string 5: Rena Queue length: 5 Printing the contents of the queue John Peter Kyra Thomas Rena Enter the number of rotations per iteration: 3 Person out of the queue: Thomas Current Queue Rena John Peter Kyra Person out of the queue: Kyra Current Queue Rena John Peter Person out of the queue: Rena Current Queue John Peter Person out of the queue: Peter Current Queue John Winner is: John Press any key to continue... #include #include //srand, rand #include //clock_t, clock, CLOCKS_PER_SEC #include #include // to get the character array of a string using namespace std; // implementing a doubly linked list-based queue class Nodet private: string data; Node* nextNodePtr; Node* prevNodePtr; public: Node() () void setData(string d) { > data-d; string getData(){ } return data; void setNextNodePtr (Node nodeptr){ next NodePtr- node Ptr; } Node* getNextNodePtr() { return nextNodePtr; > void setPreviodePtr (Node* nodePtr){ prevNodePtr - nodePtr; ) Node* getPrevNodePtr() { return prevodePtr; ) ); class Queue private: Node* headptr: Node" tailPtr; public: Queue() { headPtr = new Node(): tailPtr - new Node(): headPtr->set NextNodePtr(0); tailPtr->setPrevNodePte(0); > Node* getHeadptro! return headPtr; } Node* gettailPro return tailPtr; ) bool isEmpty if (headPtr- >getNextNodePtr() -- 0) return true; return false; ) void enqueue(string data) Node* newNodePtr = new Node(); newNodePtr->setData(data); newNode Ptr- >set NextNodePtr(0); Node. lastNodePtr- tailPtr->get PrevNodePtr(); if (lastNodePtr == 0){ headPtr- >set NextNodePtr(newNodeptr); newNodePtr- >set PrevNodePtr(0); > else{ lastNodePtr- >setNextNodePtr(newNodeptr); newNodePtr- >setPrevNodePtr(lastNodeptr); > tailPtr- >set Prev NodePtr (newNodeptr); } string dequeue () { Node. firstNodePtr- headPtr->getNextNodePtr(); Node* nextNodePtr = 0; string poppedData - **: //empty queue if (firstNodePtr != 0){ nextNodePtr firstNodePtr->getNextNodePtr(); poppedData = firstNodePtr->getData(); } else return poppedData; if (nextNodePtr - 0){ nextNodePtr- >setPrevNodePtr(0); headPtr- >set NextNodePtr (nextNodeptr); else >setNextNodePtr(0); >setPrevNodePtr(0); headPtr- tailPtr- } return poppedData; } string peeko Node* firstNodePtr = headPtr->getNextNodeptro; if (firstNodePtr !=0) return firstNodePtr->getData(); else return **; //empty queue int getQueue Length (Queue queue) { int length = 0; NodeheadPtr - queue.getHeadPtr(); Node* currentNodePtr = headPtr- >getNextNodePtr(); while (currentNodePtr != 0){ length++; currentNodePtr = currentNodePtr- >getNextNodePtr(); } return length; void Print(Queue queue) { int queueLength - getQueue Length (queue); for (int index = 0; index int main() { Queue queue; int queueSize; cout > queueSize; cout > rotation Number; // Write the code here for simulating the hot potato game system("pause"); return 0; }