C++ Codes
C++ > Games sample source codes

To solve josephus problem using circular queue and templates

To solve josephus problem using circular queue and templates

Code :
//////////////////Header file

#include<iostream.h>
template <class T>
class ex
{
	private:
		struct node
		{
			T data;
			struct node *next;
		};
		struct node *head,*front,*rear;
	public:
		ex()
		{
			head=new node;
			head->next=NULL;
			front=rear=head;
		}
		void enqueue(T x);
		T dequeue();
		void print();
		void move_next();
};



//////////////////Implementation file
#include "ex.h"
template <class T>
void ex<T>::enqueue(T x)
{
	node *p;
	p=new node;
	p->data=x;
	if(head->next==NULL)
	{
		front=rear=p;
		head->next=p;
		p->next=p;
	}
	else
	{
		rear->next=p;
		p->next=front;
		rear=rear->next;
	}
}

template<class T>
T ex<T>::dequeue()
{
	node *t;
	T x;
	t=front;
	x=t->data;
	front=front->next;
	rear->next=front;
	delete(t);
	return x;
}

template<class T>
void ex<T>::print()
{
	node *p=front;
	do
	{
		cout<<p->data<<endl;
		p=p->next;
	}while(p!=rear->next);
}

template<class T>
void ex<T>::move_next()
{
	front=front->next;
	rear=rear->next;
}



/////////////////Application file
#include "ex.cpp"
void main()
{
	ex<int> e;
	int m,n,i,d;
	cout<<"Enter the number of people
";
	cin>>n;
	cout<<"Enter the number of passes
";
	cin>>m;
	for(i=1;i<=n;i++)
		e.enqueue(i);
	cout<<"The players are
";
	e.print();
	cout<<"Eliminated in order
";
	while(n>1)
	{
		for(i=1;i<=m;i++)
			e.move_next();
		d=e.dequeue();
		cout<<d<<endl;
		n--;
	}
	d=e.dequeue();
	cout<<"Winning player:	"<<d<<endl;
}
Privacy Policy | Link to Us | Links