棧和隊列 - 棧和隊列的應用實例 - 隊列的應用實例

　　隊列的應用舞伴問題

　　問題敘述

　　假設在周末舞會上男士們和女士們進入舞廳時各自排成一隊跳舞開始時依次從男隊和女隊的隊頭上各出一人配成舞伴

　　若兩隊初始人數不相同則較長的那一隊中未配對者等待下一輪舞曲現要求寫一算法模擬上述舞伴配對問題

　　問題分析

　　先入隊的男士或女士亦先出隊配成舞伴因此該問題具體有典型的先進先出特性可用隊列作為算法的數據結構

　　在算法中假設男士和女士的記錄存放在一個數組中作為輸入然後依次掃描該數組的各元素並根據性別來決定是進入男隊還

　　是女隊當這兩個隊列構造完成之後依次將兩隊當前的隊頭元素出隊來配成舞伴直至某隊列變空為止此時若某隊仍有等待配

　　對者算法輸出此隊列中等待者的人數及排在隊頭的等待者的名字他(或她)將是下一輪舞曲開始時第一個可獲得舞伴的人

　　具體算法及相關的類型定義

　　typedef struct{

　　char name[];

　　char sex; //性別F表示女性M表示男性

　　}Person;

　　typedef Person DataType; //將隊列中元素的數據類型改為Person

　　void DancePartner(Person dancer[]int num)

　　{//結構數組dancer中存放跳舞的男女num是跳舞的人數

　　int i;

　　Person p;

　　CirQueue MdancersFdancers;

　　InitQueue(&Mdancers);//男士隊列初始化

　　InitQueue(&Fdancers);//女士隊列初始化

　　for(i=;i

　　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

From:http://tw.wingwit.com/Article/program/sjjg/201311/23917.html