## CreationAnd Implementation ofa Queue inData Structure

Create and implement a Queue Data Structure. Implement the following methods.

Implement your Data Structure in queue.cpp.

If correct, the next line should say "Queue Empty"

Queue Empty

Adding 0 to the end of the queue.

FRONT -> 0 -> END

Adding 1 to the end of the queue.

FRONT -> 0 -> 1 -> END

Adding 2 to the end of the queue.

FRONT -> 0 -> 1 -> 2 -> END

Adding 3 to the end of the queue.

FRONT -> 0 -> 1 -> 2 -> 3 -> END

Adding 4 to the end of the queue.

FRONT -> 0 -> 1 -> 2 -> 3 -> 4 -> END

Adding 5 to the end of the queue.

FRONT -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> END

Adding 6 to the end of the queue.

FRONT -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> END

Adding 7 to the end of the queue.

FRONT -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> END

Adding 8 to the end of the queue.

FRONT -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> END

Adding 9 to the end of the queue.

FRONT -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> END

We expect Front and Dequeue to return 0

The current front of the Queue is 0

Dequeue returned 0

FRONT -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> END

We expect Front and Dequeue to return 1

The current front of the Queue is 1

Dequeue returned 1

FRONT -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> END

We expect Front and Dequeue to return 2

The current front of the Queue is 2

Dequeue returned 2

FRONT -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> END

We expect Front and Dequeue to return 3

The current front of the Queue is 3

Dequeue returned 3

FRONT -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> END

We expect Front and Dequeue to return 4

The current front of the Queue is 4

Dequeue returned 4

FRONT -> 5 -> 6 -> 7 -> 8 -> 9 -> END

We expect Front and Dequeue to return 5

The current front of the Queue is 5

Dequeue returned 5

FRONT -> 6 -> 7 -> 8 -> 9 -> END

We expect Front and Dequeue to return 6

The current front of the Queue is 6

Dequeue returned 6

FRONT -> 7 -> 8 -> 9 -> END

We expect Front and Dequeue to return 7

The current front of the Queue is 7

Dequeue returned 7

FRONT -> 8 -> 9 -> END

We expect Front and Dequeue to return 8

The current front of the Queue is 8

Dequeue returned 8

FRONT -> 9 -> END

We expect Front and Dequeue to return 9

The current front of the Queue is 9

Dequeue returned 9

Queue Empty

##### Solution

#include "queue.h"

#include

/**

* Create a new empty queue

*/

struct Queue* make_queue()

{

Queue* queue = new Queue();

queue->front = nullptr;

queue->back = nullptr;

return queue;

}

void print(struct Queue* queue)

{

if(queue->front==nullptr)

{

std::cout<< "Queue Empty" << std::endl;

}else

{

std::cout<< "FRONT -> ";

struct Node* current = queue->front;

while(current!=nullptr)

{

std::cout<< current->value << " -> ";

current=current->next;

}

std::cout<< "END" << std::endl;

}

}

int front(struct Queue* queue)

{

if(queue->front == nullptr)

return 0;

return queue->front->value;

}

char empty(struct Queue* queue)

{

if(queue->front == nullptr)

return 1;

return 0;

}

/**

* Add a new element to back of queue

*/

void enqueue(struct Queue* queue, int x)

{

Node* newNode = new Node();

newNode->value = x;

newNode->next = nullptr;

if(queue->front == nullptr) {

// If queue is empty. Just add this node to front and back

queue->front = newNode;

queue->back = newNode;

}

else {

// If queue have element. Just add to the back

queue->back->next = newNode;

queue->back = newNode;

}

}

int dequeue(struct Queue* queue)

{

if(!queue || !queue->front)

return 0;

Node *current_front = queue->front;

int value = current_front->value;

// Move forward 1 space

queue->front = queue->front->next;

// We just erased the tail

if(queue->front == nullptr)

queue->back = nullptr;

delete current_front;

// j o h n n y t u o t - g m a i l - c o m

return value;

}

##### Writing a Queue Program That Takes To Command Line Arguments

In the Josephus problem, N people agree to using the following strategy to lower the population. They sit in a circle (at positions numbered 0 to N-1) and go round the circle, removing every M-th person until just one person remains. A guy called Josephus figured out a strategic sitting position to avoid being eliminated.

Use your Queue to solve this problem. Write a program josephus.cpp that takes to command line argument N and M. Your program needs to print out the order in which people are eliminated (thus showing Josephus where to sit in the circle). You must use your Queue from the previous part to solve this problem.

Here are some example executions.

$ ./josephus

Enter Number of People (N):

7

Enter Person to Eliminate (M):

2

Order Eliminated:

1 3 5 0 4 2 6

$ ./josephus

Enter Number of People (N):

100

Enter Person to Eliminate (M):

7

Order Eliminated:

6 13 20 27 34 41 48 55 62 69 76 83 90 97 4 12 21 29 37 45 53 61 70 78 86 94 2 11 22 31 40 50 59 68 79 88 98 8 18 30 42 52 64 74 85 96 9 23 35 47 60 73 87 0 15 28 44 58 75 91 5 24 39 57 77 93 14 33 54 72 95 17 43 66 89 16 46 71 1 32 65 99 36 80 10 56 3 51 7 67 26 92 82 81 84 25 63 19 38 49

/*

* josephus.cpp

*

* Created on: Mar 2, 2021

* Author: thanh

*/

#include

#include "queue.h"

int main(int argc, char **argv) {

//Create a new Queue

struct Queue *Q = make_queue();

int N, M;

std::cout<< "Enter Number of People (N):" << std::endl;

std::cin>> N;

std::cout<< "Enter Person to Eliminate (M):" << std::endl;

std::cin>> M;

// Put all people to the queue

for (int i = 0; i< N; i++) {

enqueue(Q, i);

}

std::cout<< "Order Eliminated:" << std::endl;

// Loop until queue is empty

while (empty(Q) != 1) {

for (int i = 1; i< M; i++) {

// dequeue eliminate people

int next_people = dequeue(Q);

// store their again

enqueue(Q, next_people);

}

// Then dequeue and print out

std::cout<< dequeue(Q) << " ";

}

std::cout<< std::endl;

return 0;

}