新 學(xué)期開(kāi)始了，小哈是小哼的新同桌（小哈是個(gè)小美女哦~），小哼向小哈詢問(wèn)QQ號(hào)，小哈當(dāng)然不會(huì)直接告訴小哼啦，原因嘛你懂的。所以小哈給了小哼一串加密過(guò) 的數(shù)字，同時(shí)小哈也告訴了小哼解密規(guī)則。規(guī)則是這樣的：首先將第1個(gè)數(shù)刪除，緊接著將第2個(gè)數(shù)放到這串?dāng)?shù)的末尾，再將第3個(gè)數(shù)刪除并將第4個(gè)數(shù)再放到這串 數(shù)的末尾，再將第5個(gè)數(shù)刪除……直到剩下最后一個(gè)數(shù)，將最后一個(gè)數(shù)也刪除。按照剛才刪除的順序，把這些刪除的數(shù)連在一起就是小哈的QQ啦。現(xiàn)在你來(lái)幫幫小 哼吧。小哈給小哼加密過(guò)的一串?dāng)?shù)是“6 3 1 75 8 9 2 4”。

? ? ? ?OK，現(xiàn)在輪到你動(dòng)手的時(shí)候了。快去找出9張便簽或小紙片，將“6 3 1 75 8 9 2 4”這9個(gè)數(shù)分別寫(xiě)在9張便簽上，模擬一下解密過(guò)程。如果你沒(méi)有理解錯(cuò)解密規(guī)則的話，解密后小哈的QQ號(hào)應(yīng)該是“6 1 5 94 7 2 8 3”。

? ? ? ?其實(shí)解密的過(guò)程就像是將這些數(shù)“排隊(duì)”。每次從最前面拿兩個(gè)，第1個(gè)扔掉，第2個(gè)放到尾部。具體過(guò)程是這樣的：剛開(kāi)始這串?dāng)?shù)是“6 3 1 75 8 9 2 4”，首先刪除6并將3放到這串?dāng)?shù)的末尾，這串?dāng)?shù)更新為“1 7 5 89 2 4 3”。接下來(lái)刪除1并將7放到末尾，即更新為“5 8 9 24 3 7”。再刪除5并將8放到末尾即“9 2 4 3 7 8”，刪除9并將2放到末尾即“4 3 7 8 2”，刪除4并將3放到末尾即“7 8 2 3”，刪除7并將8放到末尾即“2 3 8”，刪除2并將3放到末尾即“8 3”，刪除8并將3放到末尾即“3”，最后刪除3。因此被刪除的順序是“6 1 5 9 4 7 2 8 3”，這就是小哈的QQ號(hào)碼了，你可以加她試試看^_^。

? ? ? ?既然現(xiàn)在已經(jīng)搞清楚了解密法則，不妨自己嘗試一下去編程，我相信你一定可以寫(xiě)出來(lái)的。

? ? ? ?首先需要一個(gè)數(shù)組來(lái)存儲(chǔ)這一串?dāng)?shù)即intq[101]。并初始化這個(gè)數(shù)組即intq[101]={0,6,3,1,7,5,8,9,2,4};（此處初 始化是我多寫(xiě)了一個(gè)0，用來(lái)填充q[0]，因?yàn)槲冶容^喜歡從q[1]開(kāi)始用，對(duì)數(shù)組初始化不是很理解的同學(xué)可以去看下我的上一本書(shū)《啊哈C！思考快你一 步》）接下來(lái)就是模擬解密的過(guò)程了。

? ? ? ?解密的第一步是將第一個(gè)數(shù)刪除，你可以想一下如何在數(shù)組中刪除一個(gè)數(shù)呢？最簡(jiǎn)單的方法是將所有后面的數(shù)都往前面挪動(dòng)一位，將前面的數(shù)覆蓋。就好比我們?cè)?排隊(duì)買(mǎi)票，最前面的人買(mǎi)好離開(kāi)了，后面所有的人就需要全部向前面走一步，補(bǔ)上之前的空位，但是這樣的做法很耗費(fèi)時(shí)間。

? ? ? ?在這里，我將引入兩個(gè)整型變量head和tail。head用來(lái)記錄隊(duì)列的隊(duì)首（即第一位），tail用來(lái)記錄隊(duì)列的隊(duì)尾（即最后一位）的下一個(gè)位置。 你可能會(huì)問(wèn)為什么tail不直接記錄隊(duì)尾，卻要記錄隊(duì)尾的下一個(gè)位置呢？這是因?yàn)楫?dāng)隊(duì)列當(dāng)中只剩下一個(gè)元素時(shí)，隊(duì)首和隊(duì)尾重合會(huì)帶來(lái)一些麻煩。我們這里規(guī) 定隊(duì)首和隊(duì)尾重合時(shí)，隊(duì)列為空。

? ? ? ?現(xiàn)在有9個(gè)數(shù)，9個(gè)數(shù)全部放入隊(duì)列之后head=1;tail=10;此時(shí)head和tail之間的數(shù)就是目前隊(duì)列中“有效”的數(shù)。如果要?jiǎng)h除一個(gè)數(shù)的 話，就將head++就OK了，這樣仍然可以保持head和tail之間的數(shù)為目前隊(duì)列中“有效”的數(shù)。這樣做雖然浪費(fèi)了一個(gè)空間，卻節(jié)省了大量的時(shí)間， 這是非常劃算的。新增加一個(gè)數(shù)也很簡(jiǎn)單，把需要增加的數(shù)放到隊(duì)尾即q[tail]之后再tail++就歐克啦。

? ? ? ?我們來(lái)小結(jié)一下，在隊(duì)首刪除一個(gè)數(shù)的操作是head++;

? ? ? ?在隊(duì)尾增加一個(gè)數(shù)（假設(shè)這個(gè)數(shù)是x）的操作是q[tail]=x;tail++;

? ? ? ?整個(gè)解密過(guò)程，請(qǐng)看下面這個(gè)霸氣外漏的圖。

? ? ? ?最后的輸出就是6 1 5 94 7 2 8 3，代碼實(shí)現(xiàn)如下。

????????

#include <stdio.h> int?main() { ????int?q[102]={0,6,3,1,7,5,8,9,2,4},head,tail; ????int?i; ????//初始化隊(duì)列 ????head=1; ????tail=10;?//隊(duì)列中已經(jīng)有9個(gè)元素了，tail執(zhí)向的隊(duì)尾的后一個(gè)位置 ????while(head<tail)?//當(dāng)隊(duì)列不為空的時(shí)候執(zhí)行循環(huán) ????{ ????????//打印隊(duì)首并將隊(duì)首出隊(duì) ????????printf("%d ",q[head]); ????????head++; ??????????????????????????????????????????????????????? ????????//先將新隊(duì)首的數(shù)添加到隊(duì)尾 ????????q[tail]=q[head]; ????????tail++; ????????//再將隊(duì)首出隊(duì) ????????head++; ????} ????????????????????????????????????????????????????????? ????getchar();getchar(); ????return?0; }

? ? ? ?怎么樣上面的代碼運(yùn)行成功沒(méi)有？現(xiàn)在我們?cè)賮?lái)總結(jié)一下隊(duì)列的概念。隊(duì)列是一種特殊的線性結(jié)構(gòu)，它只允許在隊(duì)列的首部（head）進(jìn)行刪除操作稱(chēng)之為“出 隊(duì)”，而在隊(duì)列的尾部（tail）進(jìn)行插入操作稱(chēng)之為“入隊(duì)”。當(dāng)隊(duì)列中沒(méi)有元素時(shí)（即head==tail），稱(chēng)為空隊(duì)列。在我們的日常生活中有很多情 況都符合隊(duì)列的特性。比如我們之前提到過(guò)的買(mǎi)票，每個(gè)排隊(duì)買(mǎi)票的窗口就是一個(gè)隊(duì)列。在這個(gè)隊(duì)列當(dāng)中，新來(lái)的人總是站在隊(duì)列的最后面，來(lái)的越早的人越靠前也 就越早能買(mǎi)到票，就是先來(lái)的人先服務(wù)，我們稱(chēng)為“先進(jìn)先出”（First InFirst Out，FIFO）原則。

? ? ? ?隊(duì)列將是我們今后學(xué)習(xí)廣度優(yōu)先搜索以及隊(duì)列優(yōu)化的Bellman-Ford最短路算法的核心數(shù)據(jù)結(jié)構(gòu)。所以現(xiàn)在將隊(duì)列的三個(gè)基本元素（一個(gè)數(shù)組，兩個(gè)變量）封裝為一個(gè)結(jié)構(gòu)體類(lèi)型，如下。

????

struct?queue { ????int?data[100];//隊(duì)列的主體，用來(lái)存儲(chǔ)內(nèi)容 ????int?head;//隊(duì)首 ????int?tail;//隊(duì)尾 };

? ? ? ?上面我們定義了一個(gè)結(jié)構(gòu)體類(lèi)型，我們通常將其放在main函數(shù)的外面，請(qǐng)注意結(jié)構(gòu)體的定義末尾有個(gè);號(hào)。struct是結(jié)構(gòu)體的關(guān)鍵字，queue是我 們?yōu)檫@個(gè)結(jié)構(gòu)體起的名字。這個(gè)結(jié)構(gòu)體有三個(gè)成員分別是：整型數(shù)組data、整型head和整型tail。這樣我們就可以把這三個(gè)部分放在一起作為一個(gè)整體 來(lái)對(duì)待。你可以這么理解：我們定義了一個(gè)新的數(shù)據(jù)類(lèi)型，這個(gè)新類(lèi)型非常強(qiáng)大，用這個(gè)新類(lèi)型定義出的每一個(gè)變量可以同時(shí)存儲(chǔ)一個(gè)整型數(shù)組和兩個(gè)整數(shù)。

? ? ? ?有了新的結(jié)構(gòu)體類(lèi)型，如何定義結(jié)構(gòu)體變量呢？很簡(jiǎn)單，這與我們之前定義變量的方式是一樣，如下。

1	struct?queue q;

? ? ? ?請(qǐng)注意struct queue需要整體使用，不能直接寫(xiě)queue q;這樣我們就定義了一個(gè)結(jié)構(gòu)體變量q。這個(gè)結(jié)構(gòu)體變量q就可以滿足隊(duì)列的所有操作了。那又該如何訪問(wèn)結(jié)構(gòu)體變量的內(nèi)部成員呢？可以使用.號(hào)，它叫做成員運(yùn)算符或者點(diǎn)號(hào)運(yùn)算符，如下：

q.head=1;

q.tail=1; scanf("%d",&q.data[q.tail]);

? ? ? ?好了，下面這段代碼就是使用結(jié)構(gòu)體來(lái)實(shí)現(xiàn)的隊(duì)列操作。

????

#include <stdio.h> struct?queue { ????int?data[100];//隊(duì)列的主體，用來(lái)存儲(chǔ)內(nèi)容 ????int?head;//隊(duì)首 ????int?tail;//隊(duì)尾 }; ??????????????????????????????????????????? int?main() { ????struct?queue q; ????int?i; ????//初始化隊(duì)列 ????q.head=1; ????q.tail=1; ????for(i=1;i<=9;i++) ????{ ????????//依次向隊(duì)列插入9個(gè)數(shù) ????????scanf("%d",&q.data[q.tail]); ????????q.tail++; ????} ????????????????????????????????????????????? ????while(q.head<q.tail)?//當(dāng)隊(duì)列不為空的時(shí)候執(zhí)行循環(huán) ????{ ????????//打印隊(duì)首并將隊(duì)首出隊(duì) ????????printf("%d ",q.data[q.head]); ????????q.head++; ?????????????????????????????????????????????????? ????????//先將新隊(duì)首的數(shù)添加到隊(duì)尾 ????????q.data[q.tail]=q.data[q.head]; ????????q.tail++; ????????//再將隊(duì)首出隊(duì) ????????q.head++; ????} ????????????????????????????????????????????? ????getchar();getchar(); ????return?0; }

? ? ? ?上面的這種寫(xiě)法看起來(lái)雖然冗余了一些，但是可以加強(qiáng)你對(duì)隊(duì)列這個(gè)算法的理解。C++的STL庫(kù)已經(jīng)有隊(duì)列的實(shí)現(xiàn)，有興趣的同學(xué)可以參看相關(guān)材料。隊(duì)列的 起源已經(jīng)無(wú)法追溯。在還沒(méi)有數(shù)字計(jì)算機(jī)之前，數(shù)學(xué)應(yīng)用中就已經(jīng)有對(duì)隊(duì)列的記載了。我們生活中隊(duì)列的例子也比比皆是，比如排隊(duì)買(mǎi)票，又或者吃飯時(shí)候用來(lái)排隊(duì) 等候的叫號(hào)機(jī)，又或者撥打銀行客服選擇人工服務(wù)時(shí)，每次都會(huì)被提示“客服人員正忙，請(qǐng)耐心等待”，因?yàn)榭头藛T太少了，撥打電話的客戶需要按照打進(jìn)的時(shí)間 順序進(jìn)行等候等等。這里表?yè)P(yáng)一下肯德基的宅急送，沒(méi)有做廣告的嫌疑啊，每次一打就通，基本不需要等待。但是我每次打銀行的客服（具體是哪家銀行就不點(diǎn)名 了）基本都要等待很長(zhǎng)時(shí)間，總是告訴我“正在轉(zhuǎn)接，請(qǐng)稍后”，嘟嘟嘟三聲后就變成“客服正忙，請(qǐng)耐心等待！”然后就給我放很難聽(tīng)的曲子。看來(lái)錢(qián)在誰(shuí)那里誰(shuí) 就是老大啊……

碼字不容易啊，轉(zhuǎn)載麻煩注明出處

【一周一算法】解密QQ號(hào)——隊(duì)列

http://bbs.ahalei.com/thread-4489-1-1.html

(出處: 啊哈磊_編程從這里起步)

本文轉(zhuǎn)自 ? ?風(fēng)雨蕭條 博客，原文鏈接： ?http://blog.51cto.com/1095221645/1417928 ? ? ?如需轉(zhuǎn)載請(qǐng)自行聯(lián)系原作者

總結(jié)

以上是生活随笔為你收集整理的【坐在马桶上看算法】算法4：队列——解密QQ号的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。