p1=p1->next; } else{ q=p;
p=p->next; } }
return OK; }
第3章 栈和队列
3.1 若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道）
则请回答：
(1) 如果进站的车厢序列为123 则可能得到的出站车厢序列是什么？ (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 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'); Push(S x);
Pop(S x); Push(S 's');
while(!StackEmpty(S)) { Pop(S y); printf(y); } printf(x); }
解：stack
3.4 简述以下算法的功能（栈的元素类型SElemType为int）
(1) status algo1(Stack S) {
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]);
}
(2) status algo2(Stack S int e)
{
Stack T; int d; InitStack(T);
while(!StackEmpty(S)){ Pop(S d);
if(d!=e) Push(T d);
}
while(!StackEmpty(T)){ Pop(T d);
Push(S d);
} }
解：(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 解：这个问题和3.1题比较相似 因为输入序列是从小到大排列的 所以若<< 则可以理解为通过输入序列可以得到输出序列 显然通过序列123是无法得到312的 参见3.1题 所以不可能存在着i 3.7 按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例 并仿照教科书3.2节例3-2的格式 画出对下列算术表达式求值时操作数栈和运算符栈的变化过程： A-B×C/D+E↑F 解：BC=G G/D=H A-H=I E^F=J I+J=K 步骤 OPTR栈 OPND栈 输入字符 主要操作 1 # A-B*C/D+E^F# PUSH(OPND A) 2 # A -B*C/D+E^F# PUSH(OPTR -) 3 #- A B*C/D+E^F# PUSH(OPND B) 4 #- A B *C/D+E^F# PUSH(OPTR *) 5 #-* A B C/D+E^F# PUSH(OPND C) 6 #-* A B C