2.6 本章真题解析

2.6.2 综合应用题

　　例题18
　　编写算法，利用栈的基本操作将栈S1复制到S2中。
　　例题18分析
　　本题需要用到一个辅助栈S3，首先将S1中的元素出栈并入栈到S3中，然后，S3的所有元素出栈并入栈到S2中，这时栈S1就已经复制到S2中了。算法描述如下：
　　
　　例题19
　　请利用两个栈s1和s2来模拟一个队列。已知栈的三个运算定义如下：
　　（1）PUSH(ST,x)：元素x入ST栈；
　　（2）POP(ST,x)：ST栈顶元素出栈，赋给变量x；
　　（3）Sempty(ST)：判ST栈是否为空。
　　请写明如何利用栈的运算来实现队列的三个运算：
　　（1）enquene：插入一个元素入队列；
　　（2）dequene：删除一个元素出队列；
　　（3）quene_empty：判队列为空。
　　请写明算法的思想及必要的注释。
　　例题19分析
　　栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列时，s1作为输入栈，元素逐个入栈，以此模拟队列元素的入队。当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素在s2中处于栈顶。s2退栈，相当于队列的出队，实现了先进先出。显然，只有栈s2为空且s1也为空时，队列才为空。其算法描述如下：
　　
　　例题20
　　编写算法，将循环队列中的内容倒置，并将该循环队列存储在一个数组A[1..n]中。
　　例题20分析
　　使用一个栈起到过渡的作用，先将sq队列中的元素出队并将其入栈ss，直到队列空为止，然后初始化队列，即sq->front=sq->rear=n；再出栈，并将其入队列，直到栈空为止。其算法描述如下：
　　
　　例题21
　　用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法、栈满/栈空的判断条件，并用C语言设计公用的入栈操作push(i，x)，其中i为0或1，用于表示栈号，x为入栈的值。
　　例题21分析
　　两个栈共享一个向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为S[MAX]，则一个栈顶指针为-1，另一个栈顶指针为MAX时，栈为空。用C语言编写的入栈操作push(i，x)如下：
　　
　　例题22
　　设表达式以字符形式已存入数组E[n]中，'#'为表达式的结束符，试写出判断表达式中括号“(”和“)”是否配对的C语言描述算法：EXYX(E)，算法中可调用栈操作的基本算法。
　　例题22分析
　　判断表达式中括号是否匹配，可借用栈来实现。如果是左括号，则入栈，右括号则出栈。出栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。其算法描述如下：
　　
　　例题23
　　设顺序双向循环队列的数据结构定义为：
　　
　　设Q为BSeqCQuene类变量，并设初始化操作时有Q->rear=Q->front=0，要求：
　　（1）给出顺序双向循环队列满和空的条件；
　　（2）给出顺序双向循环队列抽象数据类型BSeqCQuene的入队和出队的操作算法。
　　例题23分析
　　（1）对于正向循环队列，front为队头指针，rear为队尾指针，正向循环队列的数据元素下标值递增；对于反向循环队列，则rear为队头指针，front为队尾指针，反向循环队列的数据元素下标值递减。设计双向循环队列的方法类似于顺序循环队列的设计方法，即把表元素设计成首尾衔接。因此，有
　　正向循环队列：队列空的条件为Q->rear=Q->front
　　队列满的条件为(Q->rear+1)%MaxSize=Q->front
　　反向循环队列：队列空的条件为Q->rear=Q->front
　　队列满的条件为Q-> front -1=Q-> rear
　　(当Q->front-1<0时，令Q->front= MaxSize-1)
　　（2）算法思想：正向循环队列的入队和出队操作算法与顺序循环队列的入队和出队操作算法完全相同；反向循环队列的入队和出队操作算法与顺序循环队列的入队和出队操作算法思想类似，但要把rear看做是队头指针，把front看做是队尾指针，入队操作且当front-1<0时，令front= MaxSize-1。其算法描述如下：
　　
　　例题24
　　从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以“$”作为输入结束，操作数之间用空格分隔，操作符只可能有“+”、“-”、“*”、“/”四种运算，例如：234 34+2*$。
　　例题24分析
　　逆波兰表达式（即后缀表达式）求值规定如下：设立运算栈OPND，对表达式从左到右扫描（读入），当扫描到数时，压入OPND栈；当扫描到运算符时，从OPND退出两个数，进行相应的运算，结果再压入OPND栈。这个过程一直进行到读出表达式结束符$，这时OPND栈中只有一个数，就是结果。其算法描述如下：