栈与队列 课后习题

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

A. 基础题

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

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

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

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

B. 思考题

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

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

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

【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)$。这段代码的复杂度到底如何呢？

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

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】。