新學(xué)期開始了，小哈是小哼的新同桌（小哈是個小美女哦~）瑟蜈，小哼向小哈詢問 QQ 號，小哈當(dāng)然不會直接告訴小哼啦渣窜，原因嘛你懂的铺根。所以小哈給了小哼一串加密過的數(shù)字，同時小哈也告訴了小哼解密規(guī)則乔宿。規(guī)則是這樣的：首先將第 1 個數(shù)刪除位迂，緊接著將第 2 個數(shù)放到這串?dāng)?shù)的末尾，再將第 3個數(shù)刪除并將第 4 個數(shù)再放到這串?dāng)?shù)的末尾，再將第 5 個數(shù)刪除……直到剩下最后一個數(shù)掂林，將最后一個數(shù)也刪除臣缀。按照剛才刪除的順序，把這些刪除的數(shù)連在一起就是小哈的 QQ 啦⌒喊铮現(xiàn)在你來幫幫小哼吧精置。小哈給小哼加密過的一串?dāng)?shù)是“6 3 1 75 8 9 2 4”。
OK锣杂，現(xiàn)在輪到你動手的時候了脂倦。快去找出 9 張便簽或小紙片元莫，將“6 3 1 75 8 9 2 4”這 9 個數(shù)分別寫在 9 張便簽上赖阻，模擬一下解密過程。如果你沒有理解錯解密規(guī)則的話踱蠢，解密后小哈的 QQ 號應(yīng)該是“6 1 5 94 7 2 8 3”火欧。
其實解密的過程就像是將這些數(shù)“排隊”。每次從最前面拿兩個茎截，第 1 個扔掉苇侵，第 2 個放到尾部。具體過程是這樣的：剛開始這串?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”。接下來刪除 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 號碼了蹬叭，你可以加她試試看_。
既然現(xiàn)在已經(jīng)搞清楚了解密法則状知，不妨自己嘗試一下去編程秽五，我相信你一定可以寫出來的。
首先需要一個數(shù)組來存儲這一串?dāng)?shù)即 intq[101]饥悴。并初始化這個數(shù)組即 intq[101]={0,6,3,1,7,5,8,9,2,4};（此處初始化是我多寫了一個 0坦喘，用來填充 q[0]盲再，因為我比較喜歡從 q[1]開始用，對數(shù)組初始化不是很理解的同學(xué)可以去看下我的上一本書《啊哈 C瓣铣！思考快你一步》）接下來就是模擬解密的過程了答朋。
解密的第一步是將第一個數(shù)刪除，你可以想一下如何在數(shù)組中刪除一個數(shù)呢棠笑？最簡單的方法是將所有后面的數(shù)都往前面挪動一位梦碗，將前面的數(shù)覆蓋。就好比我們在排隊買票腐晾，最前面的人買好離開了叉弦，后面所有的人就需要全部向前面走一步丐一，補(bǔ)上之前的空位藻糖，但是這樣的做法很耗費時間。
在這里库车，我將引入兩個整型變量 head 和 tail巨柒。head 用來記錄隊列的隊首（即第一位），tail 用來記錄隊列的隊尾（即最后一位）的下一個位置柠衍。你可能會問為什么 tail 不直接記錄隊尾洋满，卻要記錄隊尾的下一個位置呢？這是因為當(dāng)隊列當(dāng)中只剩下一個元素時珍坊，隊首和隊尾重合會帶來一些麻煩牺勾。我們這里規(guī)定隊首和隊尾重合時，隊列為空阵漏。
現(xiàn)在有 9 個數(shù)驻民，9 個數(shù)全部放入隊列之后 head=1;tail=10;此時 head 和 tail 之間的數(shù)就是目前隊列中“有效”的數(shù)。如果要刪除一個數(shù)的話履怯，就將 head++ 就 OK 了回还，這樣仍然可以保持 head 和 tail 之間的數(shù)為目前隊列中“有效”的數(shù)。這樣做雖然浪費了一個空間叹洲，卻節(jié)省了大量的時間柠硕，這是非常劃算的。新增加一個數(shù)也很簡單运提，把需要增加的數(shù)放到隊尾即 q[tail]之后再 tail++ 就歐克啦蝗柔。
我們來小結(jié)一下，在隊首刪除一個數(shù)的操作是 head++;在隊尾增加一個數(shù)（假設(shè)這個數(shù)是x）的操作是 q[tail]=x;tail++;整個解密過程民泵，請看下面這個霸氣外漏的圖癣丧。
最后的輸出就是 6 1 5 94 7 2 8 3，代碼實現(xiàn)如下洪灯。
#include <stdio.h> int main() { int q[102]={0,6,3,1,7,5,8,9,2,4},head,tail; int i; //初始化隊列 head=1; tail=10; //隊列中已經(jīng)有9個元素了坎缭，tail執(zhí)向的隊尾的后一個位置 while(head<tail) //當(dāng)隊列不為空的時候執(zhí)行循環(huán) { //打印隊首并將隊首出隊 printf("%d ",q[head]); head++; //先將新隊首的數(shù)添加到隊尾 q[tail]=q[head]; tail++; //再將隊首出隊 head++; } getchar();getchar(); return 0; }
怎么樣上面的代碼運行成功沒有竟痰？現(xiàn)在我們再來總結(jié)一下隊列的概念。隊列是一種特殊的線性結(jié)構(gòu)掏呼，它只允許在隊列的首部（head）進(jìn)行刪除操作稱之為“出隊”坏快，而在隊列的尾部（tail）進(jìn)行插入操作稱之為“入隊”。當(dāng)隊列中沒有元素時（即 head==tail）憎夷，稱為空隊列莽鸿。在我們的日常生活中有很多情況都符合隊列的特性。比如我們之前提到過的買票拾给，每個排隊買票的窗口就是一個隊列祥得。在這個隊列當(dāng)中，新來的人總是站在隊列的最后面蒋得，來的越早的人越靠前也就越早能買到票级及，就是先來的人先服務(wù)，我們稱為“先進(jìn)先出”（First InFirst Out额衙，F(xiàn)IFO）原則饮焦。
隊列將是我們今后學(xué)習(xí)廣度優(yōu)先搜索以及隊列優(yōu)化的 Bellman-Ford 最短路算法的核心數(shù)據(jù)結(jié)構(gòu)。所以現(xiàn)在將隊列的三個基本元素（一個數(shù)組窍侧，兩個變量）封裝為一個結(jié)構(gòu)體類型县踢，如下。
struct queue { int data[100];//隊列的主體伟件，用來存儲內(nèi)容 int head;//隊首 int tail;//隊尾 };
上面我們定義了一個結(jié)構(gòu)體類型硼啤，我們通常將其放在 main 函數(shù)的外面，請注意結(jié)構(gòu)體的定義末尾有個;號斧账。struct 是結(jié)構(gòu)體的關(guān)鍵字谴返，queue 是我們?yōu)檫@個結(jié)構(gòu)體起的名字。這個結(jié)構(gòu)體有三個成員分別是：整型數(shù)組 data其骄、整型 head 和整型 tail亏镰。這樣我們就可以把這三個部分放在一起作為一個整體來對待。你可以這么理解：我們定義了一個新的數(shù)據(jù)類型拯爽，這個新類型非常強(qiáng)大，用這個新類型定義出的每一個變量可以同時存儲一個整型數(shù)組和兩個整數(shù)毯炮。
有了新的結(jié)構(gòu)體類型逼肯，如何定義結(jié)構(gòu)體變量呢？很簡單桃煎，這與我們之前定義變量的方式是一樣篮幢，如下。
struct queue q;
請注意 struct queue 需要整體使用为迈，不能直接寫 queue q;這樣我們就定義了一個結(jié)構(gòu)體變量 q三椿。這個結(jié)構(gòu)體變量 q 就可以滿足隊列的所有操作了缺菌。那又該如何訪問結(jié)構(gòu)體變量的內(nèi)部成員呢？可以使用.號搜锰，它叫做成員運算符或者點號運算符伴郁，如下：
q.head=1; q.tail=1; scanf("%d",&q.data[q.tail]);
好了，下面這段代碼就是使用結(jié)構(gòu)體來實現(xiàn)的隊列操作蛋叼。
#include <stdio.h> struct queue { int data[100];//隊列的主體焊傅，用來存儲內(nèi)容 int head;//隊首 int tail;//隊尾 }; int main() { struct queue q; int i; //初始化隊列 q.head=1; q.tail=1; for(i=1;i<=9;i++) { //依次向隊列插入9個數(shù) scanf("%d",&q.data[q.tail]); q.tail++; } while(q.head<q.tail) //當(dāng)隊列不為空的時候執(zhí)行循環(huán) { //打印隊首并將隊首出隊 printf("%d ",q.data[q.head]); q.head++; //先將新隊首的數(shù)添加到隊尾 q.data[q.tail]=q.data[q.head]; q.tail++; //再將隊首出隊 q.head++; } getchar();getchar(); return 0; }
上面的這種寫法看起來雖然冗余了一些，但是可以加強(qiáng)你對隊列這個算法的理解狈涮。C++ 的 STL 庫已經(jīng)有隊列的實現(xiàn)狐胎，有興趣的同學(xué)可以參看相關(guān)材料。隊列的起源已經(jīng)無法追溯歌馍。在還沒有數(shù)字計算機(jī)之前握巢，數(shù)學(xué)應(yīng)用中就已經(jīng)有對隊列的記載了。我們生活中隊列的例子也比比皆是骆姐，比如排隊買票镜粤，又或者吃飯時候用來排隊等候的叫號機(jī)，又或者撥打銀行客服選擇人工服務(wù)時玻褪，每次都會被提示“客服人員正忙，請耐心等待”公荧，因為客服人員太少了带射，撥打電話的客戶需要按照打進(jìn)的時間順序進(jìn)行等候等等。這里表揚(yáng)一下肯德基的宅急送循狰，沒有做廣告的嫌疑啊窟社，每次一打就通，基本不需要等待绪钥。但是我每次打銀行的客服（具體是哪家銀行就不點名了）基本都要等待很長時間灿里，總是告訴我“正在轉(zhuǎn)接，請稍后”程腹，嘟嘟嘟三聲后就變成“客服正忙匣吊，請耐心等待！”然后就給我放很難聽的曲子寸潦∩В看來錢在誰那里誰就是老大啊……
【一周一算法】解密 QQ 號——隊列http://bbs.ahalei.com/thread-4489-1-1.html(出處: 啊哈磊_編程從這里起步)
