第1節 解密qq號——隊列

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

密文	刪除的數字	移到最后的數字	QQ號
53039301	5	3	5
0393013	0	3	50
930133	9	3	509
01333	0	1	5090
3331	3	3	50903
313	3	1	509033
31	3		5090333
1	1		50903331

解密的第一步是將第一個數刪除，你可以想一下如何在數組中刪除一個數呢。最簡單的 方法是將所有后面的數都往前面挪動一位，將前面的數覆蓋。就好比我們在排隊買票，最前 面的人買好離開了，后面所有的人就需要全部向前面走一步，補上之前的空位，但是這樣的 做法很耗費時間。
在這里，我將引入兩個整型變量 head 和 tail。head 用來記錄隊列的隊首(即第一位)， tail 用來記錄隊列的隊尾(即最后一位)的下一個位置。你可能會問:為什么 tail 不直接記 錄隊尾，卻要記錄隊尾的下一個位置呢?這是因為當隊列中只剩下一個元素時，隊首和隊尾重合會帶來一些麻煩。我們這里規定隊首和隊尾重合時，隊列為空。
現在有 n 個數，n 個數全部放入隊列之后 head = 0;tail = strlen(QQ);此時 head 和 tail 之間的數就是
目前隊列中“有效”的數。如果要刪除一個數的話，就將 head++就 OK 了，這樣仍然可以保 持 head 和 tail 之間的數為目前隊列中“有效”的數。這樣做雖然浪費了一個空間，卻節省了 大量的時間，這是非常劃算的。新增加一個數也很簡單，把需要增加的數放到隊尾即 q[tail] 之后再 tail++就 OK 啦。

1. 在隊首刪除一個數的操作是 head++;
2. 在隊尾增加一個數(假設這個數是 x)的操作是 q[tail] = x; tail++;
3. 以上操作重復執行若干次，直到head < tail結束即可

#include<iostream>using namespace std;const int maxn = 100;
int head, tail;
char QQ[maxn];
int main(){cin >> QQ;head = 0; // head指向密文的開始位置，tail指向密文的結束位置+1tail = strlen(QQ);// 當隊列不為空的時候執行循環while (head < tail){// 打印隊首，并將隊首出隊cout << QQ[head++];//先將新隊首的數添加到隊尾，再將隊首出隊QQ[tail++] = QQ[head++];}return 0;
}

隊列是一種特 殊的線性結構，它只允許在隊列的首部(head)進行刪除操作，這稱為“出隊”，而在隊列 的尾部(tail)進行插入操作，這稱為“入隊”。
當隊列中沒有元素時(即 head==tail)，稱為 空隊列。
“先進先出”(First In First Out，FIFO)原則。

struct queue{int data[100]; // 隊列的主體，用來存儲內容int head; // 隊首int tail; // 隊尾
};

上面定義了一個結構體類型，我們通常將其放在 main 函數的外面，請注意結構體的定 義末尾有個;號。struct 是結構體的關鍵字，queue 是我們為這個結構體起的名字。這個結構 體有三個成員分別是:整型數組 data、整型 head 和整型 tail。這樣我們就可以把這三個部分 放在一起作為一個整體來對待。你可以這么理解:我們定義了一個新的數據類型，這個新類 型非常強大，用這個新類型定義出的每一個變量可以同時存儲一個整型數組和兩個整數。

有了新的結構體類型，如何定義結構體變量呢?很簡單，這與我們之前定義變量的方式 是一樣的，具體做法如下。

struct queue QQ;

請注意 struct queue 需要整體使用，不能直接寫 queue q;。這樣我們就定義了一個結構體 變量 q。這個結構體變量就可以滿足隊列的所有操作了。那又該如何訪問結構體變量的內部 成員呢?可以使用.號，它叫做成員運算符或者點號運算符，如下:

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

下面這段代碼就是使用結構體來實現的隊列操作。

#include<iostream>using namespace std;struct queue{string data; // 隊列主體，用來存儲內容int head, tail; // 隊首和隊尾
};int main(){queue QQ;cin >> QQ.data;// 初始化隊列QQ.head = 0;QQ.tail = QQ.data.length();// //當隊列不為空的時候執行循環while (QQ.head <= QQ.tail){cout << QQ.data[QQ.head]; //打印隊首QQ.head++; // 將隊首出隊QQ.data[QQ.tail] = QQ.data[QQ.head];  // 先將新隊首的數添加到隊尾QQ.head++; // 再將隊首出隊QQ.tail++;}return 0;
}

第2節 解密回文——棧

棧是后進先出的數據 結構。它限定為只能在一端進行插入和刪除操作。比如說有一個小桶，小桶的直 徑只能放一個小球，我們現在小桶內依次放入 2、1、3 號小球。假如你現在需要拿出 2 號小球， 那就必須先將 3 號小球拿出，再拿出 1 號小球，最后才能將 2 號小球拿出來。在剛才取小球的 過程中，我們最先放進去的小球最后才能拿出來，最后放進去的小球卻可以最先拿出來。

棧究竟有哪些作用呢?我們來看一個例子。“xyzyx”是一個回文字符串，所謂回文字符 串就是指正讀反讀均相同的字符序列，如“席主席”、“記書記”、“aha”和“ahaha”均是回 文，但“ahah”不是回文。通過棧這個數據結構我們將很容易判斷一個字符串是否為回文。
首先我們需要讀取這行字符串，并求出這個字符串的長度。

char arr[100];
int len;
cin >> arr;
len = strlen(arr);

如果一個字符串是回文的話，那么它必須是中間對稱的，我們需要求中點，即:

mid = len / 2 + 1;

接下來就輪到棧出場了。
我們先將 mid 之前的字符全部入棧。因為這里的棧是用來存儲字符的，所以這里用來實 現棧的數組類型是字符數組即 char s[101];，初始化棧很簡單，top = 0;就可以了。入棧的操作 是top++; s[top] = x(;假設需要入棧的字符暫存在字符變量x中)，其實可以簡寫為arr[++top] = x;。
現在我們就來將 mid 之前的字符依次全部入棧。

for (int i = 0; i <= mid; i++){s[++top] = arr[i];

接下來進入判斷回文的關鍵步驟。將當前棧中的字符依次出棧，看看是否能與 mid 之后 的字符一一匹配，如果都能匹配則說明這個字符串是回文字符串，否則這個字符串就不是回 文字符串。

for(i = mid+1; i <= len - 1; i++){if (a[i] != s[top]){break; }top--; 
}
if(top == 0)printf("YES");
elseprintf("NO");

最后如果 top 的值為 0，就說明棧內所有的字符都被一一匹配了，那么這個字符串就是 回文字符串。完整的代碼如下。

#include<iostream>using namespace std;
const int maxn = 200;
int main(){char arr[maxn], s[maxn];int len, mid, next, top;cin >> arr; // 讀入一行字符串len = strlen(arr); // 求字符串的長度mid = len / 2 - 1; // 求字符串的終點top = 0; // 棧的初始化// 將mid前的字符一次入棧for (int i = 0; i <= mid; i++){s[++top] = arr[i];}// 判斷字符串的長度是奇數還是偶數，并找出需要進行字符匹配的起始下標if (len % 2 == 0){next = mid + 1;}else{next = mid + 2;}// 開始匹配for (int i = next; i < len; i++){if (arr[i] != s[top]){break;}top--;}// 如果top的值為0，則說明棧內所有的字符都被一一匹配了if (top == 0){cout << "YES";}else{cout << "NO";}return 0;
}

第3節 紙牌游戲——小貓釣魚

星期天小哼和小哈約在一起玩桌游，他們正在玩一個非常古怪的撲克游戲——“小貓釣 魚”。游戲的規則是這樣的:將一副撲克牌平均分成兩份，每人拿一份。小哼先拿出手中的 第一張撲克牌放在桌上，然后小哈也拿出手中的第一張撲克牌，并放在小哼剛打出的撲克牌 的上面，就像這樣兩人交替出牌。出牌時，如果某人打出的牌與桌上某張牌的牌面相同，即可將兩張相同的牌及其中間所夾的牌全部取走，并依次放到自己手中牌的末尾。當任意一人 手中的牌全部出完時，游戲結束，對手獲勝。

假如游戲開始時，小哼手中有 6 張牌，順序為 2 4 1 2 5 6，小哈手中也有 6 張牌，順序 為 3 1 3 5 6 4，最終誰會獲勝呢?現在你可以拿出紙牌來試一試。接下來請你寫一個程序來 自動判斷誰將獲勝。這里我們做一個約定，小哼和小哈手中牌的牌面只有 1~9。

我們先來分析一下這個游戲有哪幾種操作。小哼有兩種操作，分別是出牌和贏牌。這恰 好對應隊列的兩個操作，出牌就是出隊，贏牌就是入隊。小哈的操作和小哼是一樣的。而桌 子就是一個棧，每打出一張牌放到桌上就相當于入棧。當有人贏牌的時候，依次將牌從桌上 拿走，這就相當于出棧。那如何解決贏牌的問題呢?贏牌的規則是:如果某人打出的牌與桌 上的某張牌相同，即可將兩張牌以及中間所夾的牌全部取走。那如何知道桌上已經有哪些牌 了呢?最簡單的方法就是枚舉桌上的每一張牌，當然也有更好的辦法我們待會再說。OK， 小結一下，我們需要兩個隊列、一個棧來模擬整個游戲。

首先我們先來創建一個結構體用來實現隊列，如下。

struct queue{int data[1000];int head;int tail;
}

上面代碼中 head 用來存儲隊頭，tail 用來存儲隊尾。數組 data 用來存儲隊列中的元素， 數組 data 的大小我預設為 1000，其實應該設置得更大一些，以防數組越界。當然對于本題 的數據來說 1000 已經足夠了。
再創建一個結構體用來實現棧，如下。

struct stack{int data[10];int top;
};

其中 top 用來存儲棧頂，數組 data 用來存儲棧中的元素，大小設置為 10。因為只有 9 種不同的牌面，所以桌上最多可能有 9 張牌，因此數組大小設置為 10 就夠了。提示一下: 為什么不設置為 9 呢?因為 C ++數組下標是從 0 開始的。

接下來我們需要定義兩個隊列變量 q1 和 q2。q1 用來模擬小哼手中的牌，q2 用來模擬小 哈手中的牌。定義一個棧變量 s 用來模擬桌上的牌。

struct queue heng, ha;
struct stack table;

接下來來初始化一下隊列和棧。

// 初始化隊列heng, ha為空，此時兩人手中都還沒有牌
heng.head = 1;
heng.tail = 1;
ha.head = 1;
ha.tail = 1;
// 初始化棧table為空，最開始的時候桌上也沒有牌
table.top = 0;

未完待續… …

第4節 鏈表

第5節 模擬鏈表