Dynamic queue problem

closed account (zAoTfSEw)

Hi everyone, I'm trying to find the solution to this problem for more than 2 hours but can't think up anything, so here's the problem:

There are X kids thinking how to split Y candies, so they play a game. They sit around in a circle (the order is increasing in clockwise). A piece of paper is given to the first kid. Whenever the kid has a piece of paper, they get 6 candies and the person next to him/her is removed from the circle. The game ends when there are no candies left or there is 1 kid left. The last kid will get the rest of the candies. Design a program that prints out the total of candies that each kid has by using a dynamic queue(singly-linked list implementation).

Example:

INPUT
Number of kids: 6
Number of candies: 100

OUTPUT
1: 12
2: 0
3: 6
4: 0
5: 82
6: 0

My approach: Using a queue, I can dequeue the first value and enqueue it again, so the second value will become the first value, then I dequeue to remove the second value. This process is repeated until the program print out the kid that has the most candies. Until now, I don't know how to print out the total candies that each kid has.

My program:

#include<iostream>

class DynamicQueue
{
private:
	struct QueueNode
	{
		int data;
		QueueNode* next;
	};
	QueueNode* front;
	QueueNode* rear;
public:
	DynamicQueue();
	void Enqueue(int);
	int Dequeue();
	int countItems();
	void printItems();
	void splitCandies(int, int);
};

DynamicQueue::DynamicQueue()
{
	front = rear = nullptr;
}

void DynamicQueue::Enqueue(int k)
{
	QueueNode* newNode;

	newNode = new QueueNode;
	newNode->data = k;
	newNode->next = nullptr;

	if (countItems() == 0)
		front = rear = newNode;
	else
	{
		rear->next = newNode;
		rear = newNode;
	}
}

int DynamicQueue::Dequeue()
{
	QueueNode* temp = front;
	front = front->next;
	return temp->data;
}

int DynamicQueue::countItems()
{
	QueueNode* temp = front;
	int numItems = 0;

	while (temp)
	{
		numItems++;
		temp = temp->next;
	}

	return numItems;
}

void DynamicQueue::printItems()
{
	QueueNode* temp = front;

	while (temp)
	{
		std::cout << temp->data << std::endl;
		temp = temp->next;
	}
}

void DynamicQueue::splitCandies(int x, int y)
{
	int i;
	for (i = 1; i <= x; i++)
		Enqueue(i);

	while (countItems() > 1)
	{
		for (i = 0; i < 1; i++)
		{
			Enqueue(Dequeue());
		}
		Dequeue();
	}
	printItems();
}

int main()
{
	DynamicQueue a;
	int b, c;

	std::cout << "Total kids: ";
	std::cin >> b;

	std::cout << "Total candies: ";
	std::cin >> c;

	a.splitCandies(b, c);
}

Total kids: 6
Total candies: 100
5 ----------> The kid that has the most candies

Last edited on

dhayden (5795)

You need a separate collection that stores the number of candies that each kid has. The queue contains the indexes of the kids.

I made a few other changes:
- replaced countItems() with the much faster isEmpty()
- moved the splitCandies() login into main() because it's part of the application, not the queue class.
- Used more descriptive names.

#include<iostream>
#include <vector>
#include <algorithm>

class DynamicQueue
{
private:
    struct QueueNode
    {
	int data;
	QueueNode *next;
    };
    QueueNode *front;
    QueueNode *rear;
public:
    DynamicQueue();
    void Enqueue(int);
    int Dequeue();
    bool isEmpty();
    void printItems();
    void splitData(int, int);
};

DynamicQueue::DynamicQueue()
{
    front = rear = nullptr;
}

void
DynamicQueue::Enqueue(int k)
{
    QueueNode *newNode;

    newNode = new QueueNode;
    newNode->data = k;
    newNode->next = nullptr;

    if (front == nullptr)
	front = rear = newNode;
    else {
	rear->next = newNode;
	rear = newNode;
    }
}

int
DynamicQueue::Dequeue()
{
    int result = front->data;
    QueueNode *temp = front;
    front = front->next;
    delete temp;
    return result;
}

bool
DynamicQueue::isEmpty()
{
    return front == nullptr;
}

void
DynamicQueue::printItems()
{
    QueueNode *temp = front;

    while (temp) {
	std::cout << temp->data << std::endl;
	temp = temp->next;
    }
}

void
DynamicQueue::splitData(int x, int y)
{
    int i;
    for (i = 1; i <= x; i++)
	Enqueue(i);

    while (!isEmpty()) {
	for (i = 0; i < 1; i++) {
	    Enqueue(Dequeue());
	}
	Dequeue();
    }
    printItems();
}

int
main()
{
    unsigned numKids, numCandies;

    std::cout << "Number of kids: ";
    std::cin >> numKids;

    std::cout << "Number of candies: ";
    std::cin >> numCandies;

    std::vector<int> kids(numKids);
    DynamicQueue que;		// values are indexes into kids vector

    for (unsigned i=0; i<numKids; ++i) {
	que.Enqueue(i);
    }
    int kid;
    while (!que.isEmpty() && numCandies) {
	kid = que.Dequeue();
	int candiesToGive = std::min(6U, numCandies);
	kids[kid] += candiesToGive;
	numCandies -= candiesToGive;
	que.Enqueue(kid);	// put this kid back at the end
	que.Dequeue();		// remove the next kid
    }
    if (numCandies) {
	kids[kid] += numCandies;
    }

    // Print the items:
    for (unsigned i=0; i< kids.size(); ++i) {
	std::cout << i << ": " << kids[i] << '\n';
    }
}

closed account (zAoTfSEw)

Thank you !

Topic archived. No new replies allowed.

C++

Forum

Dynamic queue problem