struct Queue{
  ElemType *queue;
  int front,rear,len;
  int MaxSize;
};

void InitQueue(Queue &Q)
{
  Q.MaxSize=10;
  Q.len=0;
  Q.queue=new ElemType[Q.MaxSize];
  Q.front=Q.rear=0;
}

int EmptyQueue (Queue Q)
{
  return Q.front==Q.rear;
}

void EnQueue (Queue &Q, ElemType item)
{
  if((Q.rear+1)%Q.MaxSize==Q.front){
    int k=sizeof(ElemType);
    Q.queue=(ElemType*)realloc(Q.queue,2*Q.MaxSize*k);
    if(Q.rear!=Q.MaxSize-1){
      for(int i=0;i<=Q.rear;i++)
        Q.queue[i+Q.MaxSize]=Q.queue[i];
      Q.rear+=Q.MaxSize;
    }
    Q.MaxSize=2*Q.MaxSize;
  }
  Q.rear=(Q.rear+1)%Q.MaxSize;
  Q.queue[Q.rear]=item;
  Q.len++;
}

ElemType OutQueue (Queue &Q)
{
  if(Q.front==Q.rear){
    cerr<<"queue is empty!"<<endl;
    exit(1);
  }
  Q.front=(Q.front+1)%Q.MaxSize;
  Q.len--;
  return Q.queue[Q.front];
}

ElemType PeekQueue (Queue &Q)
{
  if(Q.front==Q.rear){
    cerr<<"queue is empty!"<<endl;
    exit(1);
  }
  return Q.queue[(Q.front+1)%Q.MaxSize];
}

void ClearQueue (Queue &Q)
{
  if(Q.queue!=NULL)
    delete []Q.queue;
  Q.front=Q.rear=0;
  Q.queue=NULL;
  Q.MaxSize=0;
}

#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct{
  char name[10];  
  char sex;
}dancer;
typedef dancer ElemType;
#include"test8.h"
void partner()
{
  Queue QM,QF;
  dancer t;
  char ch,oldch;
  int i;
  InitQueue(QM);
  InitQueue(QF);
  oldch=' ';
  printf("请输入跳舞者的姓名和性别（以# #结束）：\n");
  while((ch=getchar())!='#'||oldch!='#'){
    i=0;
    while(ch!='\n'){
      if(ch!=' ')
        t.name[i++]=ch;
      else{
        ch=getchar();
        t.sex=ch;
      }
      ch=getchar();
    }
    t.name[i]='\0';
    oldch='#';
    if(t.sex=='M')
      EnQueue(QM,t);
    else if(t.sex=='F')
      EnQueue(QF,t);    
  }
  printf("配对的舞伴是：\n");
  while(!EmptyQueue(QF)&&!EmptyQueue(QM)){
    t=OutQueue(QF);
    printf("%s  ",t.name);
    t=OutQueue(QM);
    printf("%s\n",t.name);
  }
  if(QM.len>QF.len){
    printf("男队还有人等待下一轮舞曲。\n");
    t=OutQueue(QM);
    printf("%s  将是下一轮得到舞伴的第一人。\n",t.name);
  }
  else if(QM.len<QF.len){
    printf("女队还有人等待下一轮舞曲。\n");
    t=OutQueue(QF);
    printf("%s 将是下一轮得到舞伴的第一人。\n",t.name);
  }
  ClearQueue(QM);
  ClearQueue(QF);
}
void main()
{
  partner();
}