例3.2设一个栈的输入序列为A，B，C，D"，则借助一个栈所得到的输出序列不可能是(A) A,B,C,D(B) D,C,B,A(C) A,C,D,B(D) D,A,B,C答：可以简单地推算，容易得出D,A,B,C是不可能的，因为D先出来，说明A,B,C,D均在栈中按照入栈顺序，在栈中顺序应为D,C,B,A，出栈的顺序只能是D,C,B,A。所以本题答案为D
11 例3.2 设一个栈的输入序列为A，B，C，D，则 借助一个栈所得到的输出序列不可能是 。 (A) A,B,C,D (B) D,C,B,A (C) A,C,D,B (D) D,A,B,C 答：可以简单地推算，容易得出D,A,B,C是不 可能的，因为D先出来，说明A,B,C,D均在栈中， 按照入栈顺序，在栈中顺序应为D,C,B,A，出栈的 顺序只能是D,C,B,A。所以本题答案为D
例3.3已知一个栈的进栈序列是1,2,3.,n其输出序列是pP,P2,Pn，若pi=n，则p;的值(A) i(B) n-i(D) 不确定(C) n-i+1答：当p,=n时，输出序列必是n,n-1,...,3,2,1则 : P2=n-1 ，P3=n-2,..,P,=1 ，推断出p;=n-i+1所以本题答案为C
12 例3.3 已知一个栈的进栈序列是1,2,3,.,n， 其输出序列是p1 ,p2 ,.,pn ，若p1=n，则pi 的 值 。 (A) i (B) n-i (C) n-i+1 (D) 不确定 答：当p1 =n时，输出序列必是n,n-1,.,3,2,1， 则：p2=n-1，p3=n-2,.,pn =1，推断出pi=n-i+1， 所以本题答案为C
例3.4设n个元素进栈序列是1,2,3.，其输出序列是P1,P2...,Pn，若pi=3，则p2的值(A)一定是2(B)一定是1(C) 不可能是1(D)以上都不对答：当p,=3时，说明1,2,3先进栈，立即出栈3，然后可能出栈，即为2，也可能4或后面的元素进栈，再出栈。因此，P2可能是2，也可能是4,.….n，但一定不能是1。所以本题答案为C。2
13 例3.4 设n个元素进栈序列是1,2,3,.，其输出序列 是p1 ,p2 ,.,pn，若p1 =3，则p2的值 。 (A) 一定是2 (B) 一定是1 (C) 不可能是1 (D) 以上都不对 答：当p1 =3时，说明1,2,3先进栈，立即出栈3，然 后可能出栈，即为2，也可能4或后面的元素进栈，再 出栈。因此，p2可能是2，也可能是4,.,n，但一定不 能是1。所以本题答案为C
在顺序栈中实现栈的基本运算算法(1)初始化栈initStack(&s)建立一个新的空栈s，实际上是将栈顶指针指向1即可。*&s)void InitStack(SqStacks=(SqStack *)malloc(sizeof(SqStack):s->top=-1;2
14 在顺序栈中实现栈的基本运算算法: (1)初始化栈 initStack(&s) 建立一个新的空栈s,实际上是将栈顶指针指向- 1即可。 void InitStack(SqStack *&s) { s=(SqStack *)malloc(sizeof(SqStack)); s->top=-1; }
(2)销毁栈ClearStack(&s)释放栈S占用的存储空间void ClearStack(SqStack *&s)free(s) ;15
15 (2)销毁栈 ClearStack(&s) 释放栈s占用的存储空间。 void ClearStack(SqStack *&s) { free(s)； }