2.1 栈的概念、实现及应用

二、综合应用题

　　1．综合应用题题目部分
　　● 习题1：n个不同元素入栈共有多少种出栈顺序？请给出推导和结论。
　　● 习题2：证明：有可能从初始输入序列1，2…n，利用一个栈得到输出序列p1，p2…pn（p1，p2…pn是1，2…n的一种排列）的充分必要条件是：不存在这样的i，j，k满足i<j<k同时pj<pk<pi。
　　● 习题3：用一个数组A[max]作为两个堆栈的共享空间。
　　（1）请说明共享方法，栈满/栈空的判断条件，设计栈操作push(i，x)和pop(i)，其中i为0或1，用于表示栈号，x为入栈值，栈顶分别用top[0]和top[1]表示。
　　（2）如果初始化栈后指向以下操作系列，分别写出每步后的两个栈内的元素信息和栈顶指针取值（假设max = 6）：push(0,1)、push(1,2)、push(0,3)、push(1,4)、pop(0)、pop(1)、pop(0)、pop(1)。
　　● 习题4：计算算术表达式的值时，可用两个栈作辅助工具。对于给出的一个表达式，从左向右扫描它的字符，并将操作数放入栈OPND中，运算符放入栈OPTR中，但每次扫描到运算符时，要把它同OPTR的栈顶运算符进行优先级比较，当扫描到的运算符的优先级不高于栈顶运算符的优先级时，取出栈OPND的栈顶和次栈顶的两个元素，以及栈OPTR的栈顶运算符进行运算将结果放入栈OPND中。为方便比较，假设栈OPTR的初始栈顶为#（#运算符的优先级低于加、减、乘、除中任何一种运算）。现假设要计算表达式：

#(30-15)× (4/2)-9×2#

　　写出栈OPND和OPTR的变化过程。
　　2．综合应用题的答案与分析
　　习题1分析：
　　这是一个典型的概率问题：
　　根据你的题设，我们可以设定元素为1～n共n个不同元素随机进栈。
　　第一个出栈的元素可以为1～n中的任何一个元素。
　　第二个出栈的元素可以为n-1个元素中的任何一个元素。
　　第三个出栈的元素可以为n-2个元素中的任何一个元素。
　　……
　　第n个出栈的元素可以为所剩下的最后一个元素。
　　所以，出栈顺序有n!种。
　　习题2分析：
　　首先证明充分条件：如果不存在这样的i，j，k满足i<j<k同时满足pj<pk<pi，即对于输入序列：…，pj，…pk…，pi…（pj<pk<pi）不存在这样的输出序列…，pi，…pj…，pk…。例如：对于输入序列1，2，3，不存在输出序列3，1，2。
　　从中可以看出，pi是后进先出，满足栈的特点。因为pi是最大的，也就是说pi在pj和pk进入之后再进入，却在输出序列中排在pj和pk的前面，同时也说明，在pk之前先进入的pj不可能在pk之后出来，反过来说明满足先进后出的特定，所以构成一个栈。
　　对于必要条件：如果初始输入序列是1,2…n，假设进栈，又同时存在这样的i，j，k满足i<j<k同时pj<pk<pi，即对于输入序列：…,pj,…pk…,pi…（pj<pk<pi）存在这样的输出序列…,pi,…pj…,pk…。
　　从中可以看出，pi先进后出，满足栈的特点。因为pi最大，也就是在pj和pk之后进入，同时也可以看出在pk之前先进入的pi却在pk之前出来，反过来说明不满足先进后出的特点。这与前面的假设是一个栈相矛盾。
　　习题3分析：
　　（1）两个栈的栈底分别为数组的两端，初始值如表2-3所示。

表2-3 习题3分析表（1）

　　算法push(i,x)的关键代码如下：

　　算法pop(i)的关键代码如下：

　　（2）每次操作后栈的信息变化情况如表2-4所示。

表2-4 习题3分析表（2）

续表

　　习题4分析，如表2-5所示。

表2-5 习题4分析表

　　3．训练自测表（如表2-6所示）

表2-6 应用题练习自测表

续表