(2) 如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到（即写出以 ‘S’表示进栈和以 ‘X’表示出栈的栈操作序列）。
解：(1) 123 231 321 213 132
(2) 可以得到135426的出站序列，但不能得到435612的出站序列。因为4356出站说明12已经在栈中，1不可能先于2出栈。 3.2 简述栈和线性表的差别。
解：线性表是具有相同特性的数据元素的一个有限序列。栈是限定仅在表尾进行插入或删除操作的线性表。
3.3 写出下列程序段的输出结果（栈的元素类型SElemType为char）。
void main() { } 解：stack
3.4 简述以下算法的功能（栈的元素类型SElemType为int）。
(1) status algo1(Stack S) {
} { }
Stack T; int d; InitStack(T);
while(!StackEmpty(S)){ }
while(!StackEmpty(T)){ }
Pop(T,d); Push(S,d); Pop(S,d);
if(d!=e) Push(T,d); int i,n,A[255]; n=0;
while(!StackEmpty(S)) { n++; Pop(S,A[n]); } for(i=1;i<=n;i++) Push(S,A[i]); Stack S; char x,y; InitStack(S); x= ‘c’; y= ‘k’; Push(S,x);
Push(S, ‘a’);
Push(S,y);
Pop(S,x); Push(S, ‘t’); Pop(S,x); Push(S, ‘s’);
while(!StackEmpty(S)) { Pop(S,y); printf(y); } printf(x);
Push(S,x);
(2) status algo2(Stack S,int e)
解：(1) 栈中的数据元素逆置 (2) 如果栈中存在元素e，将其从栈中清除
3.5 假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。
解：任何前n个序列中S的个数一定大于X的个数。 设两个合法序列为： T1=S……X……S……
T2=S……X……X……
假定前n个操作都相同，从第n+1个操作开始，为序列不同的起始操作点。由于前n个操作相同，故此时两个栈（不妨为栈A、B）的存储情况完全相同，假设此时栈顶元素均为a。
第n+1个操作不同，不妨T1的第n+1个操作为S，T2的第n+1个操作为X。T1为入栈操作，假设将b压栈，则T1的输出顺序一定是先b后a；而T2将a退栈，则其输出顺序一定是先a后b。由于T1的输出为……ba……，而T2的输出顺序为……ab……，说明两个不同的合法栈操作序列的输出元素的序列一定不同。
3.6 试证明：若借助栈由输入序列12…n得到的输出序列为在输出序列中不可能出现这样的情形：存在着i p1p2?pn(它是输入序列的一个排列)，则 pj pj 解：这个问题和3.1题比较相似。因为输入序列是从小到大排列的，所以若解为通过输入序列 pjpkpi可以得到输出序列pipjpk，显然通过序列123是无法得到312的，参 pj 见3.1题。所以不可能存在着i 3.7 按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例，并仿照教科书3.2节例3-2的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程： 步骤 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A-B×C/D+E↑F OPND栈 A A A B A B A B C A G A G A G D A H I I I E I E I E F 输入字符 A-B*C/D+E^F# -B*C/D+E^F# B*C/D+E^F# *C/D+E^F# C/D+E^F# /D+E^F# /D+E^F# D+E^F# +E^F# +E^F# +E^F# E^F# ^F# F# # 主要操作 PUSH(OPND,A) PUSH(OPTR,-) PUSH(OPND,B) PUSH(OPTR,*) PUSH(OPND,C) Operate(B,*,C) PUSH(OPTR,/) PUSH(OPND,D) Operate(G,/,D) Operate(A,-,H) PUSH(OPTR,+) PUSH(OPND,E) PUSH(OPTR,^) PUSH(OPND,F) Operate(E,^,F) 解：BC=G G/D=H A-H=I E^F=J I+J=K OPTR栈 # # #- #- #-* #-* #- #-/ #-/ #- # #+ #+ #+^ #+^ 16 17 #+ # I J K # # Operate(I,+,J) RETURN 3.8 试推导求解n阶梵塔问题至少要执行的move操作的次数。 解：2n?1 3.9 试将下列递推过程改写为递归过程。 void ditui(int n) { } 解： void ditui(int j) { } 3.10 试将下列递归过程改写为非递归过程。 void test(int &sum) { } 解： void test(int &sum) { Stack s; InitStack(s); int x; do{ cin>>x; Push(s,x); int x; cin>>x; if(x==0) sum=0; else { } cout< test(sum); sum+=x; if(j>1){ } return; cout< cout< } 3.11 简述队列和堆栈这两种数据类型的相同点和差异处。 解：栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。 队列也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。 3.12 写出以下程序段的输出结果（队列中的元素类型QElemType为char）。 void main() { } 解：char 3.13 简述以下算法的功能（栈和队列的元素类型均为int）。 void algo3(Queue &Q) { Stack S; int d; InitStack(S); while(!QueueEmpty(Q)) { } while(!StackEmpty(S)) DeQueue(Q, d); Push(S, d); Queue Q; InitQueue(Q); char x= ‘e’, y= ‘c’; EnQueue(Q, ‘h’); EnQueue(Q, ‘r’); EnQueue(Q, y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); EnQueue(Q, ‘a’); While(!QueueEmpty(Q)) { } cout< DeQueue(Q,y); cout< while(!StackEmpty(s)){ } DestoryStack(s); Pop(s,x); sum+=x; cout< } 解：队列逆置 3.14 若以1234作为双端队列的输入序列，试分别求出满足以下条件的输出序列： (1) 能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。 (2) 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列。 (3) 既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。 3.15 假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么有缺点。 解： class DStack{ ElemType *top[2]; ElemType *p; int stacksize; int di; public: DStack(int m) { } ~DStack(){delete p;} void Push(int i,ElemType x) { } ElemType Pop(int i) { di=i; if(di==0){ } else{ } if(top[1] Pop(S, d); EnQueue(Q, d);