资源描述：
《第3章 栈和队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第3章栈和队列3.1栈3.2队列本章小结3.1.1栈的定义3.1.2栈的顺序存储结构及其基本运算实现3.1.3栈的链式存储结构及其基本运算的实现3.1.4栈的应用例子3.1栈栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。栈顶的当前位置是动态的,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。当栈中没有数据元素时,称为空栈。栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。3.1.1栈的定义栈顶栈底出栈进栈栈示意图例3.1
2、设有4个元素a、b、c、d进栈,给出它们所有可能的出栈次序。答:所有可能的出栈次序如下:abcdabdcacbdacdbadcbbacdbadcbcadbcdabdcacbadcbdacdbadcba例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
3、,出栈的顺序只能是D,C,B,A。所以本题答案为D。例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,…,n,其输出序列是p1,p2,…,pn,若p1=3,则p2的值。(A)一定是2(B)一定是1(C)不可能是
4、1(D)以上都不对答:当p1=3时,说明1,2,3先进栈,立即出栈3,然后可能出栈,即为2,也可能4或后面的元素进栈,再出栈。因此,p2可能是2,也可能是4,…,n,但一定不能是1。所以本题答案为C。栈的几种基本运算如下:(1)初始化栈InitStack(&s):构造一个空栈s。(2)销毁栈ClearStack(&s):释放栈s占用的存储空间。(3)求栈的长度StackLength(s):返回栈s中的元素个数。(4)判断栈是否为空StackEmpty(s):若栈s为空,则返回真；否则返回假。(5)
5、进栈Push(&S,e):将元素e插入到栈s中作为栈顶元素。(6)出栈Pop(&s,&e):从栈s中退出栈顶元素,并将其值赋给e。(7)取栈顶元素GetTop(s,&e):返回当前的栈顶元素,并将其值赋给e。(8)显示栈中元素DispStack(s):从栈顶到栈底顺序显示栈中所有元素。3.1.2栈的顺序存储结构及其基本运算实现假设栈的元素个数最大不超过正整数MaxSize,所有的元素都具有同一数据类型ElemType,则可用下列方式来定义栈类型SqStack:typedefstruct{ElemT
6、ypedata[MaxSize]；inttop；/*栈指针*/}SqStack；顺序栈进栈和出栈示意图在顺序栈中实现栈的基本运算算法:(1)初始化栈initStack(&s)建立一个新的空栈s,实际上是将栈顶指针指向-1即可。对应算法如下:voidInitStack(SqStack*&s){s=(SqStack*)malloc(sizeof(SqStack));s->top=-1;}(2)销毁栈ClearStack(&s)释放栈s占用的存储空间。对应算法如下:voidClearStack(SqSt
7、ack*&s){free(s);}(3)求栈的长度StackLength(s)返回栈s中的元素个数,即栈指针加1的结果。对应算法如下:intStackLength(SqStack*s){return(s->top+1);}(4)判断栈是否为空StackEmpty(s)栈S为空的条件是s->top==-1。对应算法如下:intStackEmpty(SqStack*s){return(s->top==-1);}(5)进栈Push(&s,e)在栈不满的条件下,先将栈指针增1,然后在该位置上插入元素e。对
8、应算法如下:intPush(SqStack*&s,ElemTypee){if(s->top==MaxSize-1)return0;/*栈满的情况,即栈上溢出*/s->top++;s->data[s->top]=e;return1;}(6)出栈Pop(&s,&e)在栈不为空的条件下,先将栈顶元素赋给e,然后将栈指针减1。对应算法如下:intPop(SqStack*&s,ElemType&e){if(s->top==-1)return0;/*栈为空的情况,即栈下溢出*/e=s->dat
