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

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/4.1.png" alt="picture4.1" />

OK，現(xiàn)在輪到你動手的時候了?？烊フ页?9 張便簽或小紙片，將“6 3 1 75 8 9 2 4”這 9 個數(shù)分別寫在 9 張便簽上，模擬一下解密過程。如果你沒有理解錯解密規(guī)則的話，解密后小哈的 QQ 號應該是“6 1 5 94 7 2 8 3”。

其實解密的過程就像是將這些數(shù)“排隊”。每次從最前面拿兩個，第 1 個扔掉，第 2 個放到尾部。具體過程是這樣的：剛開始這串數(shù)是“6 3 1 75 8 9 2 4”，首先刪除 6 并將 3 放到這串數(shù)的末尾，這串數(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ù)組來存儲這一串數(shù)即 intq[101]。并初始化這個數(shù)組即 intq[101]={0,6,3,1,7,5,8,9,2,4};（此處初始化是我多寫了一個 0，用來填充 q[0]，因為我比較喜歡從 q[1]開始用，對數(shù)組初始化不是很理解的同學可以去看下我的上一本書《啊哈 C！思考快你一步》）接下來就是模擬解密的過程了。

解密的第一步是將第一個數(shù)刪除，你可以想一下如何在數(shù)組中刪除一個數(shù)呢？最簡單的方法是將所有后面的數(shù)都往前面挪動一位，將前面的數(shù)覆蓋。就好比我們在排隊買票，最前面的人買好離開了，后面所有的人就需要全部向前面走一步，補上之前的空位，但是這樣的做法很耗費時間。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/4.2.png" alt="picture4.2" />

在這里，我將引入兩個整型變量 head 和 tail。head 用來記錄隊列的隊首（即第一位），tail 用來記錄隊列的隊尾（即最后一位）的下一個位置。你可能會問為什么 tail 不直接記錄隊尾，卻要記錄隊尾的下一個位置呢？這是因為當隊列當中只剩下一個元素時，隊首和隊尾重合會帶來一些麻煩。我們這里規(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++ 就歐克啦。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/4.3.png" alt="picture4.3" />

我們來小結(jié)一下，在隊首刪除一個數(shù)的操作是 head++;
在隊尾增加一個數(shù)（假設這個數(shù)是x）的操作是 q[tail]=x;tail++;
整個解密過程，請看下面這個霸氣外漏的圖。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/4.4.png" alt="picture4.4" />

最后的輸出就是 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) //當隊列不為空的時候執(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）進行刪除操作稱之為“出隊”，而在隊列的尾部（tail）進行插入操作稱之為“入隊”。當隊列中沒有元素時（即 head==tail），稱為空隊列。在我們的日常生活中有很多情況都符合隊列的特性。比如我們之前提到過的買票，每個排隊買票的窗口就是一個隊列。在這個隊列當中，新來的人總是站在隊列的最后面，來的越早的人越靠前也就越早能買到票，就是先來的人先服務，我們稱為“先進先出”（First InFirst Out，F(xiàn)IFO）原則。

隊列將是我們今后學習廣度優(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)體的關鍵字，queue 是我們?yōu)檫@個結(jié)構(gòu)體起的名字。這個結(jié)構(gòu)體有三個成員分別是：整型數(shù)組 data、整型 head 和整型 tail。這樣我們就可以把這三個部分放在一起作為一個整體來對待。你可以這么理解：我們定義了一個新的數(shù)據(jù)類型，這個新類型非常強大，用這個新類型定義出的每一個變量可以同時存儲一個整型數(shù)組和兩個整數(shù)。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/4.5.png" alt="picture4.5" />

有了新的結(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) //當隊列不為空的時候執(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;
    }

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

【一周一算法】解密 QQ 號——隊列
http://bbs.ahalei.com/thread-4489-1-1.html
(出處: 啊哈磊_編程從這里起步)