栈和队列在项目中的应用

Answer 1

队列的应用--舞伴问题
　　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>　　p=dancer[i];　　if(p.sex=='F')　　EnQueue(&Fdancers.p); //排入女队　　else　　EnQueue(&Mdancers.p); //排入男队　　}　　printf("The dancing partners are: \n \n");　　while(!QueueEmpty(&Fdancers)&&!QueueEmpty(&Mdancers)){　　//依次输入男女舞伴名　　p=DeQueue(&Fdancers); //女士出队　　printf("%s ",p.name);//打印出队女士名　　p=DeQueue(&Mdancers); //男士出队　　printf("%s\n",p.name); //打印出队男士名　　}　　if(!QueueEmpty(&Fdancers)){ //输出女士剩余人数及队头女士的名字　　printf("\n There are %d women waitin for the next round.\n",Fdancers.count);　　p=QueueFront(&Fdancers); //取队头　　printf("%s will be the first to get a partner. \n",p.name);　　}else　　if(!QueueEmpty(&Mdancers)){//输出男队剩余人数及队头者名字　　printf("\n There are%d men waiting for the next round.\n",Mdacers.count);　　p=QueueFront(&Mdancers);　　printf("%s will be the first to get a partner.\n",p.name);　　}　　}//DancerPartners

参考资料：希赛教育