#include<iostream>
#include<string>
using namespace std;

struct dancer
{   string name;
    char sex;
};

struct Node
{   dancer data;
	Node* next;
}*front,*rear;

struct LinkQueue
{    Node *front;
     Node *rear;
}Gentleman, Lady;

void InitialLinkQueue(LinkQueue& queue)
{	queue.front=new Node;
    queue.front->next=NULL;
	queue.rear=queue.front;
}

void DeleteLinkQueue(LinkQueue& queue)
{   Node *p;
    while(queue.front!=NULL)
    {	p=queue.front;
	    queue.front=queue.front->next;
	    delete p;
    }
}

void EnQueue(LinkQueue& queue,dancer& value)
{
	Node* s=new Node;
    s->data=value;
    s->next=queue.rear->next;
    queue.rear->next=s;
    queue.rear=s;
}

int IsEmpty(LinkQueue queue)
{
	if (queue.front==queue.rear) return 1;
	else return 0;
}

dancer DeQueue(LinkQueue &queue)
{  dancer x;
   Node *p;
   if (IsEmpty(queue))  throw "队列为空，无法出队列！";
   p=queue.front->next;
   x=p->data;
   queue.front->next=p->next;
   if (p==queue.rear) queue.rear=queue.front;
   delete p;
   return x;
}

dancer GetHead(LinkQueue queue)
{   if (IsEmpty(queue)) throw "队列为空，无法取得队首元素！";
    return queue.front->next->data;
}

void QueueTranverse(LinkQueue queue)
{	Node *p;
    p=queue.front->next;
    while(p!=NULL)
    {	cout<<(p->data).name<<" ";
	    p=p->next;
    }
    cout<<endl;
}

int main()
{    cout<<"请输入舞伴总数量:"<<endl;
     int num;
	 cin>>num;

	 InitialLinkQueue(Gentleman);
	 InitialLinkQueue(Lady);

     for(int i=0;i<num;i++)
     {    cout<<"请输入舞者性别(F(女) or M(男))及姓名:"<<endl;
          char sex;
		  cin>>sex;
          string name;
		  cin>>name;
          dancer newdancer;
          newdancer.name=name;
		  newdancer.sex=sex;
          if(sex=='F')
            EnQueue(Lady,newdancer);
          if(sex=='M')
            EnQueue(Gentleman,newdancer);
	 }

	 while ( (!IsEmpty(Gentleman)) && (!IsEmpty(Lady)) )
         cout<<DeQueue(Gentleman).name<<"<---配对--->"<<DeQueue(Lady).name<<endl;
     if (!IsEmpty(Gentleman))
        cout<<GetHead(Gentleman).name<<"先生还在等着呢!"<<endl;
     else
        if (!IsEmpty(Lady))
            cout<<GetHead(Lady).name<<"女士还在等着呢!"<<endl;
        else
            cout<<"配对完美结束!"<<endl;

	 DeleteLinkQueue(Gentleman);
	 DeleteLinkQueue(Lady);

	 system("pause");

	 return 0;
}