#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 Node{

private:

string data;

Node* nextNodePtr;

Node* prevNodePtr;

public:

Node(){}

void setData(string d){

data = d;

}

string getData(){

return data;

}

void setNextNodePtr(Node* nodePtr){

nextNodePtr = nodePtr;

}

Node* getNextNodePtr(){

return nextNodePtr;

}

void setPrevNodePtr(Node* nodePtr){

prevNodePtr = nodePtr;

}

Node* getPrevNodePtr(){

return prevNodePtr;

}

};

class Queue{

private:

Node* headPtr;

Node* tailPtr;

public:

Queue(){

headPtr = new Node();

tailPtr = new Node();

headPtr->setNextNodePtr(0);

tailPtr->setPrevNodePtr(0);

}

Node* getHeadPtr(){

return headPtr;

}

Node* getTailPtr(){

return tailPtr;

}

bool isEmpty(){

if (headPtr->getNextNodePtr() == 0)

return true;

return false;

}

void enqueue(string data){

Node* newNodePtr = new Node();

newNodePtr->setData(data);

newNodePtr->setNextNodePtr(0);

Node* lastNodePtr = tailPtr->getPrevNodePtr();

if (lastNodePtr == 0){

headPtr->setNextNodePtr(newNodePtr);

newNodePtr->setPrevNodePtr(0);

}

else{

lastNodePtr->setNextNodePtr(newNodePtr);

newNodePtr->setPrevNodePtr(lastNodePtr);

}

tailPtr->setPrevNodePtr(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->setNextNodePtr(nextNodePtr);

}

else{

headPtr->setNextNodePtr(0);

tailPtr->setPrevNodePtr(0);

}

return poppedData;

}

string peek(){

Node* firstNodePtr = headPtr->getNextNodePtr();

if (firstNodePtr != 0)

return firstNodePtr->getData();

else

return ""; //empty queue

}

};

int getQueueLength(Queue queue){

int length = 0;

Node* headPtr = queue.getHeadPtr();

Node* currentNodePtr = headPtr->getNextNodePtr();

while (currentNodePtr != 0){

length++;

currentNodePtr = currentNodePtr->getNextNodePtr();

}

return length;

}

void Print(Queue queue){

int queueLength = getQueueLength(queue);

for (int index = 0; index

string dataDequeued = queue.dequeue();

cout

queue.enqueue(dataDequeued);

}

cout

}

int main(){

Queue queue;

int queueSize;

cout

cin >> queueSize;

cout

for (int i = 0; i

cout

cin.clear();

cin.sync();

string value;

getline(cin, value);

queue.enqueue(value);

//cout

}

cout

cout

cout

Print(queue);

int rotationNumber;

cout

cin >> rotationNumber;

// Write the code here for simulating the hot potato game

system("pause");

return 0;

}

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 getQueuelength function (that takes the Queue as the argument) provided for you to return the length of the Queue. The main function also inputs the rotationNumber, 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... Submission: (1) Your .cpp file that includes all the classes and the main function simulating the game. (2) A screenshot (jpeg or .png file) of your output starting with a queue of any size in the range of 7-10 strings and a rotation number per iteration of any value in the range of 3-5