队列

队列：
（3）循环队列的类型定义

1   #define Queur Size 100   //应根据具体情况定义该值
2      typedef char Queue DataType;  //DataType的类型依赖于具体的应用
3      typedef Sturet{               //头指针，队非空时指向队头元素
4            int front;              //尾指针，队非空时指向队尾元素的下一位置
5            int rear;               //计数器，记录队中元素总数
6            DataType data[QueueSize]
7      }CirQueue;

判别队列是"空"还是"满"。解决办法：使用一个计数器记录队列中元素的总数（即队列长度）
（4）循环队列的基本运算
　用第三种方法，循环队列的六种基本运算：
　　① 置队空

 void InitQueue(CirQueue *Q)
      {
              Q->front=Q->rear=0;
              Q->count=0;     //计数器置0
       }

② 判队空

int QueueEmpty(CirQueue *Q)
       {
            return Q->count==0;  //队列无元素为空
        }

③ 判队满

int QueueFull(CirQueue *Q)
        {
            return Q->count==QueueSize;  //队中元素个数等于QueueSize时队满
         }

④ 入队

void EnQueue(CirQueuq *Q,DataType x)
         {
            if(QueueFull((Q))                   
                   Error("Queue overflow");     //队满上溢
            Q->count ++;                        //队列元素个数加1
            Q->data[Q->rear]=x;                 //新元素插入队尾
            Q->rear=(Q->rear+1)%QueueSize;      //循环意义下将尾指针加1

⑤ 出队

DataType DeQueue(CirQueue *Q)
          {
              DataType temp;
              if(QueueEmpty((Q))
                   Error("Queue underflow");     //队空下溢
              temp=Q->data[Q->front];
              Q->count--;                        //队列元素个数减1
              Q->front=(Q->front+1)&QueueSize;   //循环意义下的头指针加1
              return temp; 
           }

⑥取队头元素

DataType QueueFront(CirQueue *Q)
            {
                if(QueueEmpty(Q))
                    Error("Queue if empty.");
                return Q->data[Q->front];
            }

队列的应用--舞伴问题

1、问题叙述　假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。

2、问题分析　先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。　在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。

3、具体算法及相关的类型定义

  typedef struct{
           char name[20];
           char sex;  //性别，'F'表示女性，'M'表示男性
       }Person;
       typedef Person DataType;  //将队列中元素的数据类型改为Person
        
       void DancePartner(Person dancer[],int num)
       {//结构数组dancer中存放跳舞的男女，num是跳舞的人数。
            int i;
            Person p;
            CirQueue Mdancers,Fdancers;
            InitQueue(&Mdancers);//男士队列初始化
            InitQueue(&Fdancers);//女士队列初始化
            for(i=0;i<num;i++){//依次将跳舞者依其性别入队
                 p=dancer[i];       
                 if(p.sex=='F')
                     EnQueue(&Fdancers.p);   //排入女队
                 else
                     EnQueue(&Mdancers.p);   //排入男队
             }
             printf("The dancing partners are: 
 
");
             while(!QueueEmpty(&Fdancers)&&!QueueEmpty(&Mdancers)){
                   //依次输入男女舞伴名
                   p=DeQueue(&Fdancers);     //女士出队
                   printf("%s        ",p.name);//打印出队女士名
                   p=DeQueue(&Mdancers);     //男士出队
                   printf("%s
",p.name);    //打印出队男士名
             }
             if(!QueueEmpty(&Fdancers)){ //输出女士剩余人数及队头女士的名字
                   printf("
 There are %d women waitin for the next  round.
",Fdancers.count);
                   p=QueueFront(&Fdancers);  //取队头
                   printf("%s will be the first to get a partner. 
",p.name);
              }else
                  if(!QueueEmpty(&Mdancers)){//输出男队剩余人数及队头者名字
                         printf("
 There are%d men waiting for the next   round.
",Mdacers.count);
                         p=QueueFront(&Mdancers);
                         printf("%s will be the first to get a partner.
",p.name);
                   }
        }//DancerPartners