#include "stdio.h"
#define MAX_DANCERS 100//最多跳舞人數
#define QueueSize 100 //假定預分配的隊列空間最多為100個元素  	
typedef struct{
	char name[20];
	char sex;  //性別，'F'表示女性，'M'表示男性
}Person;
typedef Person DataType;  //將隊列中元素的數據類型改為Person
typedef struct{
	DataType data[QueueSize];
	int front;//頭指針
	int rear;//尾指針
	int count; //計數器，記錄隊中元素總數           
}CirQueue;   

// 置隊列空
void Initial(CirQueue *Q)
{//將順序隊列置空
	Q->front=Q->rear=0;
	Q->count=0;     //計數器置0       
} 

//判隊列空
int IsEmpty(CirQueue *Q)
{
	return Q->front==Q->rear;
}

//判隊列滿
int IsFull(CirQueue *Q)
{
	return Q->rear==QueueSize-1+Q->front;
}

//進隊列
void EnQueue(CirQueue *Q,DataType x)
{
	if (IsFull(Q))
	{
		printf("隊列上溢"); //上溢,退出運行
		exit(1);
	}
	Q->count ++;                        //隊列元素個數加1
	Q->data[Q->rear]=x;                 //新元素插入隊尾
	Q->rear=(Q->rear+1)%QueueSize;      //循環意義下將尾指針加1
}

//出隊列
DataType DeQueue(CirQueue *Q)
{
	DataType temp;
	if(IsEmpty(Q))
	{
		printf("隊列為空"); //下溢,退出運行
		exit(1);
	}
	temp=Q->data[Q->front];
	Q->count--;                        //隊列元素個數減1
	Q->front=(Q->front+1)&QueueSize;   //循環意義下的頭指針加1
	return temp; 
	
}

// 取隊列頂元素
DataType Front(CirQueue *Q)
{
	if(IsEmpty(Q))
	{
		printf("隊列為空"); //下溢,退出運行
		exit(1);
	}
	return Q->data[Q->front];
}

void DancePartner(Person dancer[],int num)
{//結構數組dancer中存放跳舞的男女，num是跳舞的人數。
	int i;
	Person p;
	CirQueue Mdancers,Fdancers;
	Initial(&Mdancers);//男士隊列初始化
	Initial(&Fdancers);//女士隊列初始化
	for(i=0;i<num;i++){//依次將跳舞者依其性別入隊
		p=dancer[i];       
		if(p.sex=='F')
			EnQueue(&Fdancers,p);   //排入女隊
		else
			EnQueue(&Mdancers,p);   //排入男隊
	}
	printf("舞隊是: \n \n");
	while(!IsEmpty(&Fdancers)&&!IsEmpty(&Mdancers)){
		//依次輸入男女舞伴名
		p=DeQueue(&Fdancers);     //女士出隊
		printf("%s        ",p.name);//打印出隊女士名
		p=DeQueue(&Mdancers);     //男士出隊
		printf("%s\n",p.name);    //打印出隊男士名
	}
	if(!IsEmpty(&Fdancers)){ //輸出女士剩余人數及隊頭女士的名字
		printf("\n 還有 %d 個女士等下一輪.\n",Fdancers.count);
		p=Front(&Fdancers);  //取隊頭
		printf("%s will be the first to get a partner. \n",p.name);
	}
	else if(!IsEmpty(&Mdancers)){//輸出男隊剩余人數及隊頭者名字
		printf("\n 還有%d 個男士等下一輪.\n",Mdancers.count);
		p=Front(&Mdancers);
		printf("%s will be the first to get a partner.\n",p.name);
	}
}

void InitialDancer(Person dancer[])
{
	//跳舞報名
}

void main()
{
	Person dancer[MAX_DANCERS];
	int n=93;
	InitialDancer(dancer);
	DancePartner(dancer,93);
}