啊哈!算法-第2章-栈、队列、链表

第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节 模拟链表