第1節(jié) 解密qq號(hào)——隊(duì)列

1. 新學(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ù)放到這串?dāng)?shù)的末尾，再將第 5 個(gè)數(shù)刪除… 直到剩下最后一個(gè)數(shù)，將最后一個(gè)數(shù)也刪除。按照剛才刪除的順序，把這些刪除的數(shù)連在一 起就是小哈的 QQ 啦。現(xiàn)在你來(lái)幫幫小哼吧。小哈給小哼加密過(guò)的一串?dāng)?shù)是“5 3 0 3 9 3 0 1”。

密文	刪除的數(shù)字	移到最后的數(shù)字	QQ號(hào)
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

解密的第一步是將第一個(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ì)列中只剩下一個(gè)元素時(shí)，隊(duì)首和隊(duì)尾重合會(huì)帶來(lái)一些麻煩。我們這里規(guī)定隊(duì)首和隊(duì)尾重合時(shí)，隊(duì)列為空。
現(xiàn)在有 n 個(gè)數(shù)，n 個(gè)數(shù)全部放入隊(duì)列之后 head = 0;tail = strlen(QQ);此時(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++就 OK 啦。

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

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

隊(duì)列是一種特 殊的線性結(jié)構(gòu)，它只允許在隊(duì)列的首部(head)進(jìn)行刪除操作，這稱為“出隊(duì)”，而在隊(duì)列 的尾部(tail)進(jìn)行插入操作，這稱為“入隊(duì)”。
當(dāng)隊(duì)列中沒(méi)有元素時(shí)(即 head==tail)，稱為 空隊(duì)列。
“先進(jìn)先出”(First In First Out，FIFO)原則。

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)單，這與我們之前定義變量的方式 是一樣的，具體做法如下。

struct queue QQ;

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

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

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

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

第2節(jié) 解密回文——棧

棧是后進(jìn)先出的數(shù)據(jù) 結(jié)構(gòu)。它限定為只能在一端進(jìn)行插入和刪除操作。比如說(shuō)有一個(gè)小桶，小桶的直 徑只能放一個(gè)小球，我們現(xiàn)在小桶內(nèi)依次放入 2、1、3 號(hào)小球。假如你現(xiàn)在需要拿出 2 號(hào)小球， 那就必須先將 3 號(hào)小球拿出，再拿出 1 號(hào)小球，最后才能將 2 號(hào)小球拿出來(lái)。在剛才取小球的 過(guò)程中，我們最先放進(jìn)去的小球最后才能拿出來(lái)，最后放進(jìn)去的小球卻可以最先拿出來(lái)。

棧究竟有哪些作用呢?我們來(lái)看一個(gè)例子?！皒yzyx”是一個(gè)回文字符串，所謂回文字符 串就是指正讀反讀均相同的字符序列，如“席主席”、“記書(shū)記”、“aha”和“ahaha”均是回 文，但“ahah”不是回文。通過(guò)棧這個(gè)數(shù)據(jù)結(jié)構(gòu)我們將很容易判斷一個(gè)字符串是否為回文。
首先我們需要讀取這行字符串，并求出這個(gè)字符串的長(zhǎng)度。

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

如果一個(gè)字符串是回文的話，那么它必須是中間對(duì)稱的，我們需要求中點(diǎn)，即:

mid = len / 2 + 1;

接下來(lái)就輪到棧出場(chǎng)了。
我們先將 mid 之前的字符全部入棧。因?yàn)檫@里的棧是用來(lái)存儲(chǔ)字符的，所以這里用來(lái)實(shí) 現(xiàn)棧的數(shù)組類(lèi)型是字符數(shù)組即 char s[101];，初始化棧很簡(jiǎn)單，top = 0;就可以了。入棧的操作 是top++; s[top] = x(;假設(shè)需要入棧的字符暫存在字符變量x中)，其實(shí)可以簡(jiǎn)寫(xiě)為arr[++top] = x;。
現(xiàn)在我們就來(lái)將 mid 之前的字符依次全部入棧。

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

接下來(lái)進(jìn)入判斷回文的關(guān)鍵步驟。將當(dāng)前棧中的字符依次出棧，看看是否能與 mid 之后 的字符一一匹配，如果都能匹配則說(shuō)明這個(gè)字符串是回文字符串，否則這個(gè)字符串就不是回 文字符串。

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

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

#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); // 求字符串的長(zhǎng)度mid = len / 2 - 1; // 求字符串的終點(diǎn)top = 0; // 棧的初始化// 將mid前的字符一次入棧for (int i = 0; i <= mid; i++){s[++top] = arr[i];}// 判斷字符串的長(zhǎng)度是奇數(shù)還是偶數(shù)，并找出需要進(jìn)行字符匹配的起始下標(biāo)if (len % 2 == 0){next = mid + 1;}else{next = mid + 2;}// 開(kāi)始匹配for (int i = next; i < len; i++){if (arr[i] != s[top]){break;}top--;}// 如果top的值為0，則說(shuō)明棧內(nèi)所有的字符都被一一匹配了if (top == 0){cout << "YES";}else{cout << "NO";}return 0;
}

第3節(jié) 紙牌游戲——小貓釣魚(yú)

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

假如游戲開(kāi)始時(shí)，小哼手中有 6 張牌，順序?yàn)?2 4 1 2 5 6，小哈手中也有 6 張牌，順序 為 3 1 3 5 6 4，最終誰(shuí)會(huì)獲勝呢?現(xiàn)在你可以拿出紙牌來(lái)試一試。接下來(lái)請(qǐng)你寫(xiě)一個(gè)程序來(lái) 自動(dòng)判斷誰(shuí)將獲勝。這里我們做一個(gè)約定，小哼和小哈手中牌的牌面只有 1~9。

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

首先我們先來(lái)創(chuàng)建一個(gè)結(jié)構(gòu)體用來(lái)實(shí)現(xiàn)隊(duì)列，如下。

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

上面代碼中 head 用來(lái)存儲(chǔ)隊(duì)頭，tail 用來(lái)存儲(chǔ)隊(duì)尾。數(shù)組 data 用來(lái)存儲(chǔ)隊(duì)列中的元素， 數(shù)組 data 的大小我預(yù)設(shè)為 1000，其實(shí)應(yīng)該設(shè)置得更大一些，以防數(shù)組越界。當(dāng)然對(duì)于本題 的數(shù)據(jù)來(lái)說(shuō) 1000 已經(jīng)足夠了。
再創(chuàng)建一個(gè)結(jié)構(gòu)體用來(lái)實(shí)現(xiàn)棧，如下。

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

其中 top 用來(lái)存儲(chǔ)棧頂，數(shù)組 data 用來(lái)存儲(chǔ)棧中的元素，大小設(shè)置為 10。因?yàn)橹挥?9 種不同的牌面，所以桌上最多可能有 9 張牌，因此數(shù)組大小設(shè)置為 10 就夠了。提示一下: 為什么不設(shè)置為 9 呢?因?yàn)?C ++數(shù)組下標(biāo)是從 0 開(kāi)始的。

接下來(lái)我們需要定義兩個(gè)隊(duì)列變量 q1 和 q2。q1 用來(lái)模擬小哼手中的牌，q2 用來(lái)模擬小 哈手中的牌。定義一個(gè)棧變量 s 用來(lái)模擬桌上的牌。

struct queue heng, ha;
struct stack table;

接下來(lái)來(lái)初始化一下隊(duì)列和棧。

// 初始化隊(duì)列heng, ha為空，此時(shí)兩人手中都還沒(méi)有牌
heng.head = 1;
heng.tail = 1;
ha.head = 1;
ha.tail = 1;
// 初始化棧table為空，最開(kāi)始的時(shí)候桌上也沒(méi)有牌
table.top = 0;

未完待續(xù)… …

第4節(jié) 鏈表

第5節(jié) 模擬鏈表