序 · 数据结构

欢迎来到【数据结构】章节。

初学数据结构，您可能会觉得无从下手；不过不用担心——我们接下来讲的栈和队列，在生活中就有很多例子。比如，顾名思义，“队列”当然就对应着我们日常生活中排队的过程。

您听说过“建模”一词吗？所谓“建模”，就是把事物进行抽象，根据实际问题来建立对应的数学模型。

我们在商场里面排队买东西，和我们在淘宝上抢购商品，差别很大；但它们都遵循着相同的规则——讲“先来后到”。早来的，就早买到商品；晚来的，就晚买到商品，甚至可能买不到商品。我们利用“先来后到”这一规则，可以把这两种排队模式统一起来——它们都是“队列”，都可以用队列这一数据结构来模拟。

建模就是把实际问题“抽象”起来。“抽象”并不意味着晦涩难懂；相反，它为我们提供了大量的便利。计算机很难直接去解决实际问题，但是如果我们把实际问题建模成数学问题，就会大大地方便计算机来“理解”和“解决”。

我们写程序来处理实际问题，一般来讲是这样的：

比如吧，我们拿到了某次数学考试的成绩单，现在我们需要知道谁考得最好。
您当然不能把成绩单对着电脑晃一晃，然后问“谁考得最好？”我们需要一种方式，让计算机来理解我们的问题，这就是建模。
这个问题可以建模成：“给定数组score[]，问数组内元素的最大值”。这样建模之后，就很方便我们写程序解决问题了。对于这个数学问题，我们采用之前讨论过的“擂台法”，就可以给出答案。

如何把实际问题建模成数学问题，主要依靠我们的经验和直觉、当然还有你灵动的思维；而算法与数据结构，正是解决数学问题的两把利剑。

我们之前已经研究过很多算法了！比如，二分法可以用来“给定单调函数，求零点”；冒泡排序可以用来“给定一个数组，将其排序后输出”……你已经知道算法很有用，我们接下来要学习的数据结构，也一样很有用！

在这个章节中，我们首先讨论两种线性表——栈和队列，它们将会成为很多算法的基础。接下来，我们将学习两种结构——树和图，许多问题都可以转化为树上、图上的问题。

祝您学习愉快！

• 序 · 数据结构
• 栈和队列
  • 栈：从洗盘子说起
  • 如何实现一个栈
  • 括号匹配——栈的应用
  • 栈与递归
  • 队列：模拟排队
  • 约瑟夫问题——队列的应用
• 栈与队列 课后习题
  • A. 基础题
  • B. 思考题
  • C. 挑战题

栈和队列

栈：从洗盘子说起

假设小止是餐厅里的洗碗工。她身边有一叠餐盘要洗。客人们吃完饭之后，要洗的盘子会放在这叠餐盘的顶端；而小止洗盘子的时候，总会取出这叠餐盘最顶上的盘子来洗。

比如吧：本来桌子上没有餐盘。一个人吃完饭了，依次把1、2、3这三个盘子放在了桌子上：

现在小止取出了最顶端的3号盘子洗，洗完之后取出现在的顶端盘子——2号。这叠餐盘变成了这样：

又有一个客人吃完了饭，依次放进了4、5这两个盘子：

在这之后，小止依次洗完了5、4、1这三个盘子。她的工作结束啦~

回过头来，我们来研究这一叠盘子。我们把“放盘子”和“取盘子”视为事件，那么在每一次事件之后，这叠盘子会是什么状态呢？

观察上面这张表，你有没有发现：越靠左的元素就越“顽固”，越靠右的元素就越容易改变？比如，1最早被加入，它直到最后才退出；2的加入时间稍后，也比较稳固，直到它的后辈3退出后，2才会退出这叠餐盘。

事实上，越早加入的元素，越晚退出。不难发现：对于这叠餐盘，如果a比b早加入，那a一定比b后退出。请你随意找一对元素，来验证一下这个结论！

最后，我们再看一眼“盘子状态”那一列表格。是不是觉得长得很像连绵的山，或是金字塔？请记住这个图像。这种“感性”的理解，有时候也很重要。这有助于你的联想能力。

再来看另外一个例子。

这里采用火车调度的例子。

洗盘子和火车调度，看似毫不相关的两个例子，却拥有相同的性质。那就是：

越早进入列表的元素，越晚退出；
越晚进入列表的元素，越早退出。

我们把这种表叫做“后进先出”表——LIFO表。LIFO是“last in, first out”的缩写，满足这种条件的表就是栈（stack）。

一个栈可以提供下面几个功能：

• void push(x)：将x压入栈。对应上面的“放餐盘”和“冲进电梯”。
• void pop()：弹出栈顶的元素。对应“取走餐盘”和“离开电梯”。
• int top()： 查询栈顶的元素。我们由此知道接下来该洗哪个餐盘、接下来谁该退出电梯。

利用上面三个函数，我们来重新描述一下小止洗碗的过程：

push(1);
push(2);
push(3);
printf("洗[%d]号餐盘\n",top());
pop();
printf("洗[%d]号餐盘\n",top());
pop();
push(4);
push(5);
printf("洗[%d]号餐盘\n",top());
pop();
printf("洗[%d]号餐盘\n",top());
pop();
printf("洗[%d]号餐盘\n",top());
pop();

它的执行结果是：

洗[3]号餐盘
洗[2]号餐盘
洗[5]号餐盘
洗[4]号餐盘
洗[1]号餐盘

仿照洗餐盘的例子，现在请你利用上面三个函数，模拟进出电梯的过程，依次输出离开电梯的人。可以使用1,2,3...来表示甲乙丙……这些同学。

满足“后进先出”顺序的问题，往往可以抽象成栈这个结构。

在日后的学习中，我们将会很频繁地利用栈，所以我们下面介绍如何用C++写一个栈。

如何实现一个栈

以小止洗盘子为例，我们只需要用一个数组s[]，来从下到上存储这些盘子的编号。此外，需要一个变量tot来表示栈的大小。很容易写出下面的代码：

int s[10005],tot=0;
int top()
{
    return s[tot];     // s[tot]即为顶层的盘子编号
}
void push(int x)
{
    tot++;           // 更新tot值
    s[tot]=x;        // 把新盘子放在数组最后面
}
void pop()
{
    tot--;           // 更新tot值
}

这样我们就写完了一个栈。请你思考下面的问题：

• 为什么pop操作不需要改变s数组的尾部，只需要把tot减一？
• 如何实现一个isEmpty()函数，判断这个栈是否为空？
• （选做）我们上面是给这个栈指定了10005位的空间，如果我们事先不知道具体需要多少空间，你能利用结构体和指针，采用new/delete来动态分配内存，实现一个栈吗？提示：结构体可以这样写：

struct node
{
    int value;
    node* Front;
};

Note: STL的栈
我们经常懒得自己动手写栈。在这个时候，STL提供的stack容器真是太好用了！

先包含<stack>库，然后using namespace std，接下来我们可以这样使用：

用法	作用
stack <int> s	建立一个栈s，其内部元素类型是int
s.push(x)	将元素x压进栈s
s.pop()	弹出s的栈顶元素
s.top()	返回s的栈顶元素
s.empty()	返回s是否为空。为空则是1（true），栈内有元素则是0（false）。我们经常使用!s.empty()来判断s是否有元素
s.size()	返回s内的元素个数。

需要注意的是，这样写虽然方便，但是如果不打开-O2优化，就有一点慢。在非常需要追求运行速度的情况下，我们往往自己手写栈。

本书接下来的讨论，将会一直使用STL的栈。

括号匹配——栈的应用

现在我们来考虑这么一个问题：给定一个字符串，这个字符串由()[]{}这六个字符构成。

如果所有的括弧都可以匹配上，那么就说这个字符串合法。否则非法。下面给一些例子：

[({})]：合法。
()[]()：合法。
[([]){}[]]{}：合法。
{{}：非法。第一个{找不到与之匹配的}。
([)(])：非法。中间的)、(都找不到与之匹配的括弧，因为被中括号断开。

我们的任务是写一个程序，判断给定字符串是否合法。

我们不难想出一个思路：将这个字符串从左往右写，一旦遇到匹配上的括号，我们就把这对括号擦掉，就像消消乐一样。

以[([]){}]为例。我们从左往右写，写到[([]，这里产生了一个匹配，所以我们把[]擦掉，纸上的字符串变成了[(。然后接着写，下一个字符是)，字符串变成[()，产生了匹配。我们擦掉()，现在纸上只剩下了一个[。
接下来，往后写一个字符，变成[{，没有产生匹配。再写一个，变成[{}，我们擦掉{}。现在纸上又只剩下一个[。接下来写]，产生了匹配，擦掉[]之后纸上什么也不剩了；原来的字符串也读完了。

这样，我们就认定：所给字符串是合法的。

请你用这种方法处理([)(])，在哪里出了问题？什么情况下，我们可以判断所给字符串非法？

这个思路看起来很有效。但是如何用程序来实现呢？

我们来看看模拟[([]){}]时的草稿纸吧。

[
[(
[([
[(
[
[{
[
<空>

长得是不是很像连绵的山？这提示我们，也许能利用栈来模拟我们刚才的做法！

这离我们下定论只有一步之遥了。判断一个过程能否用栈来模拟，当然是看能否满足“后进先出”或者“先进后出”。在这里，越早写下的括号，离可能产生匹配的地方越远，当然越晚得到匹配！我们的做法符合“先进后出”，所以可以用栈来模拟这个操作！

请你实现这个程序，并提交到【洛谷 XXXX】。

栈与递归

栈与递归是什么关系呢？我们先不急着给出结论。

来看看下面两个程序，请你在草稿纸上模拟它们的运行，写出运行结果：

// Prog A
void play(int n)
{
    printf("Play %d\n",n);
    if(n==1 || n==2) return;
    play(n-1);
    play(n-2);
}
// 执行 play(5)
// Prog B
void play(int n)
{
    int x;
    stack <int> s;
    s.push(n);
    while(!s.empty())
    {
        x=s.top();
        s.pop();
        printf("Play %d\n",x);
        if(x==1 || x==2) continue;
        s.push(x-1);
        s.push(x-2);
    }
}
// 执行play(5)

为什么它们的输出是一样的？

现在再来回顾递归过程。递归，就像一层一层叠盘子：每次函数调用就是放了一个盘子，递归调用相当于在自己这个盘子上面再放盘子。函数调用结束之后，当然是把自己这个盘子取走。

我们立刻发现，这个过程是先入后出的——越早的调用越“基础”，越晚的调用越“表层”。由此，我们把递归的调用过程和栈统一了起来！

按照“叠盘子”的思想，你能把下面的函数改写成非递归形式吗？试试看。

void f(int l,int r)
{
    int mid=(l+r)/2;
    printf("[%d,%d]\n",l,r);
    if(l == r) return;
    f(l,mid);
    f(mid+1,r);
}

以上，我们介绍完了栈。接下来，我们来研究另一个数据结构——队列。

队列：模拟排队

我们的生活中到处都是队列的例子。无论是去食堂排队用餐，还是在网上抢购商品，总是遵循着“先来后到”的规则。

满足先来后到规则的，就是队列。队列是FIFO表（first in, first out）。

那么，我们应该如何在程序中模拟排队呢？类比超市里的排队，我们需要实现哪些功能？

• void push(x)：将x压入队列。一个人来排队了，他应该站在队尾。
• void pop()：弹出队首的元素。排在最前面的人结完了账，离开队列。
• int front()： 查询队首的元素。这样我们可以知道现在应该给谁结账。

队列的代码比栈要稍微麻烦一点——毕竟栈是后端入、后端出；而栈是后端入、前端出。我们用q[]来记录队列里的人，用l指向队首，用r指向队尾。

int q[10005],l=1,r=0;
int front()
{
    return q[l];
}
void push(int x)
{
    r++;
    q[r]=x;
}
void pop()
{
    l++;
}

这样就用代码实现了队列。请思考下面的问题：

• 这份代码是如何利用l,r表示“目前在队列中的元素”区间的？为什么要把l设为1，把r设为0？
• 如何实现一个isEmpty()函数，判断这个栈是否为空？
• （选做）如何动态分配内存实现队列？提示：结构体node中记录int value和node *Next。
• （选做）每次执行pop操作，都会使l增加，在l之前的空间再也不会用到，所以我们浪费掉了很多空间。能利用起来这一部分空间吗？
  提示：我们之前实现队列，是“列表”的形式。尝试把首尾拼起来，成为一个环状！填空：每次一个指针达到_____之后，就把它设成_____，从而重复利用了数组前面那部分空间。
  这样的队列，称为“循环队列”。试代码实现之。

Note: STL的队列
像stack一样，STL提供了一个队列（queue），我们可以直接拿来用。

先包含<queue>库，然后using namespace std，接下来我们可以这样使用：

用法	作用
queue <int> q	建立一个队列q，其内部元素类型是int
q.push(x)	将元素x压进队列q
q.pop()	弹出q的队首元素
q.front()	返回q的队首元素
q.empty()	返回q是否为空。
q.size()	返回q内的元素个数。

queue的多数操作名字和stack的一样，但是需要注意，stack采用top()来返回栈顶元素，queue采用front()来返回队首元素。

约瑟夫问题——队列的应用

来考虑这样一个历史悠久的问题：一群小朋友坐成一个圈，已经按照1...n编号。从1号小朋友开始报数，报到k的小朋友出局；下一个小朋友继续从1开始报。显然，游戏进行到最后，场上只会剩下一个小朋友。此时这个小朋友获胜。

我们的问题是，给定n和k，问被淘汰的$n-1$个小朋友出局的顺序。

乍一看这和队列好像没有什么关系。但是我们来考虑这样的情景：1...n这些小朋友站在队列里。接下来，队首的人出队，然后走到队尾，这样一直循环，直到第k个小朋友。他淘汰出局，不再入队。队内现在只剩下了n-1名小朋友，我们继续重复刚刚的操作：前k-1个人出队之后走到队尾，接下来那位小朋友直接淘汰。

稍加思考，便不难看出这个情景与约瑟夫问题的等效性。我们利用这个队列，即可模拟约瑟夫问题的游戏过程。

代码如下：

queue <int> q;
int n,k;
void work()
{
    int i;
    for(i=1;i<=n;i++) q.push(i);
    while(q.size() != 1)
    {
        for(i=1;i<k;i++) q.push(q.front()),q.pop();
        printf("%d\n",q.front());
        q.pop();
    }
}

栈与队列 课后习题

习题分为了三个部分：基础题、思考题和挑战题。
基础题是客观题，用于帮助学生理解最基本的知识。
思考题是主观题，意在训练学生解决问题的能力。
挑战题供学有余力的选手玩一玩。

A. 基础题

【1】现在有一个栈S（初始为空），试着模拟以下的操作。
前四行是范例。请从第五行开始，填写右边的格子。

【2】将上题的栈换成队列，然后模拟这些操作。

【3】请利用一个栈，将下面的代码改写成非递归版本。

int ans=0;
int play(int n)
{
    ans+=n;
    if(n==1 || n==2) return 1;
    play(n-1);
    play(n-2);
}

B. 思考题

【1】栈和队列的区别在哪里？它们分别可以用来做什么？举出几个例子。

【2】在洛谷题解堆积如山的时候，管理员小Y会跑出来审核。她的精力是有限的，而她可以采取两种审核顺序：一种是优先审核最早提交的题解，另一种是优先审核最近提交的题解。

这两种顺序分别对应了什么数据结构？你觉得采取哪种方案更好？简述你的理由。

【3】你手头有一个STL的队列，只知道队列里面的元素单调递增——例如，队列是[1,3,3,5,6,8,9]。现在需要支持下面三个操作：

• int Top() 查询队首元素

• void Pop() 弹出队首元素

• void Delete(x) 删除掉元素x

其中，保证了Delete操作是从小到大删除元素——也就是说，保证更小的元素会比更大的元素先删除。

请你设计一个方案，以尽可能低的时间复杂度实现上面的需求。

提示：试试再开一个队列？

【4】还是以一叠餐盘为例。我们吃完饭之后，会把餐盘往上面一张一张地放；而我们洗盘子的时候，会一次性取出很多餐盘来洗。如果用程序来模拟上述过程，那就是：

stack<int> s;
void add()
{
    s.push(233);            //往s的顶端放一个餐盘
}
void wash(int n)
{
    int i;
    for(i=1;i<=n;i++)       //从s的顶端取出n张餐盘
        s.pop();
}

每次add()操作显然是$O(1)$的时间复杂度，但wash()操作可能不止$O(1)$。这段代码的复杂度到底如何呢？

提示：不要总想着搞清楚每一次函数调用的复杂度。试试研究每张餐盘吧！

【5】如何利用两个栈来实现一个队列？请给出时间复杂度尽量好的解决方案。

提示：刚刚做过的题目【4】可能有助于时间复杂度分析。

C. 挑战题

【1】我们平常写的表达式，运算符在数的中间，比如1+3*5，其中+在1和3*5之间，*在3和5之间。我们把这种表达式称为中缀表达式。
中缀表达式对我们而言很好用，但是计算机可能没那么喜欢中缀表达式。有一种表达式对计算机很友好，它叫“后缀表达式”。顾名思义，后缀表达式中，运算符在参数的后面。

阅读一个后缀表达式的方法是这样的：从左往右读式子，一旦遇到运算符，就往前取$n$个数——这个$n$取决于运算符有多少个参数——然后擦掉这些参数和这个运算符，把计算结果写在那里。接下来，重复刚才的操作，直到表达式中只剩下一个数为止。

举个例子。对于后缀表达式2 4 * 1 3 + -，我们是这样处理的：
首先从左往右读，读到了乘号。乘法有两个参数，所以我们取出前面的2和4，算出2*4=8。
现在，擦掉2 4 *，写上8，式子变成：8 1 3 + -。
我们从头开始往右读。读到加号之后，取出前面的1和3，算出1+3=4，把式子改写成：8 4 -。
接着，我们还是从头开始读这个式子。读到减号之后，我们取出8和4，算出8-4=4，于是最后的式子就是4。这就是我们想要的结果。事实上，与这个后缀表达式相对应的中缀表达式是2*4-(1+3)。

对于计算机而言，后缀表达式当然比中缀表达式更容易计算；另外，后缀表达式可以避免掉括号。这也是它相对于中缀表达式的一大优势。

结合这一章节介绍的数据结构，试着完成下面的三道题吧！就算写不出也没关系；思考这些问题的过程对你的学习是很有帮助的。

(1) 写一个程序，求后缀表达式的值。保证后缀表达式中仅有整数和四则运算符号。
(2) 在(1)的基础上，让你的程序支持一个三元运算符#：a b c #表示(a+b)*(b+c).
*(3) [选做] 上网查找“表达式树”的资料，然后完成下面的任务：
给定一个仅含变量和四则运算符号的后缀表达式，其中每个变量保证是一位小写字母。
编程构建表达式树。然后输入各个变量的值，求出表达式的值。

【2】现在有一个集合S，从小到大排好序之后输入给你。需要实现下面两个操作：

• int ask() 查询当前集合内的最小值

• void modify() 删除当前集合中的最小值和次小值，然后把它们的和加入集合

(1) 试编程实现之。要求时间复杂度O(n)。

提示：使用两个队列。

(2) 利用(1)的思想，我们可以高效地实现哈夫曼编码。查阅资料，并解决下面的问题：对于26个小写字母，给定每个字母的出现频次，求每个字母的编码。

(3) 推广(1)的做法，解决【洛谷P2827】。

【3】考虑约瑟夫问题。
(1) 我们程序的时间复杂度如何？
(2) 现在，我们只需要得知最后的胜利者是谁。利用一些数学知识，改进程序，使之只需$O(n)$的时间复杂度即可得出结果。