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;
}
