第3章堆栈与队列ppt课件.ppt

《第3章堆栈与队列ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章堆栈与队列Chapter3StackandQueue堆栈堆栈的应用队列队列的应用3.1堆栈一、堆栈的基本概念定义栈：用于局部变量、函数的形参等的空间分配。堆：由程序员申请，并对之进行释放。例如：malloc（）；free（）；3.1堆栈一、堆栈的基本概念定义栈是限定只能在表的一端进行插入和删除的线性表。在表中允许插入和删除的一端叫做栈顶(top)；表的另一端则叫做栈底(bottom)。栈又称后进先出(LastInFirstOut,简写为LIFO)表出栈或退栈入栈或进栈a0a1…an-2an-1bottomtop相关术语栈满：栈内元素个数为MaxSize时。top=MaxSize-1栈

2、空：栈内无元素。top=-1上溢：当栈满时，还要进栈。下溢：当栈空时，还要出栈。例：对于一个栈，给出输入项A、B、C，如果输入项序列由ABC组成，试给出所有可能的输出序列。A进A出B进B出C进C出ABCA进A出B进C进C出B出ACBA进B进B出A出C进C出BACA进B进B出C进C出A出BCAA进B进C进C出B出A出CBA不可能产生输出序列CAB1、初始化2、进栈3、退栈4、取栈顶元素5、判栈是否非空二、堆栈的操作三、栈的顺序表示和实现——顺序堆栈1.顺序栈的存储结构出栈或退栈入栈或进栈bottomtopa0a1a3a4a5maxlen-1543210顺序栈的定义typedefintData

3、Type;#definemaxlen64typedefstruct{DataTypestack[maxlen];inttop;}seqstack;topstack[maxlen]ss->tops->stack[0]s->stack[1]s->stack[2]…s->stack[maxlen-1]2.顺序堆栈的操作实现toptopa1a2a3a4toptoptopmaxlen个a1进栈a2进栈a3进栈a4进栈a4出栈top初始化voidinistack(seqstack*s){s->top=-1;}判栈空操作intempty(seqstacks){if(s.top==-1)return1;e

4、lsereturn0;}入栈intpush(seqstack*s,DataTypex){if(s->top==maxlen-1){printf(“Stackisfull”);return0;}s->top++;s->stack[s->top]=x;return1;}判栈满？栈顶下标加1入栈出栈intpop(seqstack*s,DataType*d){if(s->top==-1){printf("Stackisempty!");return0;}else{*d=s->stack[s->top];(s->top)--;return0;}}判栈空？元素出栈栈顶下标减1取栈顶元素intg

5、ettop(seqstack*s,DataType*d){if(s->top==-1){printf(“Stackisempty!”);return0;}else{*d=s->stack[s->top];return1;}}堆栈算法练习顺序栈的C语言描述：typedefintelemtype;#definemaxsize10elemtypestack[maxsize];inttop;写出堆栈的入栈和出栈算法两个堆栈共享空间目的：节省空间扩展知识——堆栈共用问题两个堆栈共享空间的运算：初始化进栈出栈a0…aiaj…am0maxsize-1LeftTopRightTop…数据结构定义：ty

6、pedefstruct{DataTypestack[maxlen];intLeftTop;intRightTop;}dqstack;初始化算法voidInitiDqstack(dqstack*s);{s->LeftTop=-1;s->RightTop=maxlen;}intPushDqstack(dqstack*s,charWhichStack,DataTypex){if(s->LeftTop>=s->RightTop-1){printf(“栈满”);return0;}if(WhichStack!=‘L’&&WhichStack!=‘R’){printf(“出错”);return0;}if

7、(WhichStack==‘L’)s->stack[++s->LeftTop]=x;elses->stack[--s->RightTop]=x;return1;}进栈算法判断是否栈满判断输入是否错X入左栈X入右栈共用堆栈的出栈算法:自编。共用堆栈的算法练习:已知：一个双向堆栈stack[M](M自己定义)，编写一个从键盘输入数据，若输入的是奇数，则存入左栈；若输入的是偶数，则存入右栈，直到栈满为止的算法。12EFhead