数据结构-栈和队列ppt课件.ppt

《数据结构-栈和队列ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章栈和队列3.1栈3.2栈的应用举例3.3栈与递归的实现3.4队列3.1栈3.1.1抽象数据类型栈的定义⑴栈的定义栈(stack)，又称堆栈，是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。也就是说，栈是一种后进先出(LastInFirstOut)的线性表，简称为L

2、IFO表。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。例：入栈顺序：123可能出栈顺序：123，132，213，231，321不可能出栈顺序：312⑵栈的抽象数据类型ADTStackisData：含有n个元素a1,a2,a3,…,an,按LIFO规则存放，每个元素的类型都为ElemType。Operation://初始化栈svoidinitStack(Stack&s);//清除栈s的所有元素，使之成为空栈voidclearStack(Stack&s);//判断栈s是否为空，若是则返回true，否则返回fals

3、eboolisEmpty(Stack&s);//若栈已满则返回true，否则返回false，此操作为顺序栈所特有boolisFull(Stack&s);//返回栈顶元素，但不移动栈顶指针ElemTypepeek(Stack&s);//元素e进栈，即插入到栈顶voidpush(Stack&s,constElemType&e);//删除栈顶元素并返回之ElemTypepop(Stack&s);endStack3.1.2栈的表示和实现3.1.2.1顺序栈--栈的顺序存储结构和线性表类似，栈也有两种存储表示，其顺序存储结构简称为顺序

4、栈。顺序栈类型定义：sqstack.h#includeusingnamespacestd;constintMAXSIZE=50;structElem{intdata;};typedefElemElemType;structSqStack{ElemTypebase[MAXSIZE];inttop;};voidinitStack(SqStack&s);voidclearStack(SqStack&s);boolisEmpty(SqStack&s);boolisFull(SqStack&s);ElemTypep

5、eek(SqStack&s);voidpush(SqStack&s,constElemType&e);ElemTypepop(SqStack&s);s.base始终指向栈底s.base=NULL表示栈结构不存在s.top=0表示栈空s.top始终指向栈顶元素的下一个位置顺序栈基本操作的实现：sqstack.cpp#include"sqstack.h"⑴初始化栈voidinitStack(SqStack&s){s.top=0;}⑵清空栈voidclearStack(SqStack&s){s.top=0;}⑶判栈空boolisE

6、mpty(SqStack&s){returns.top==0;}⑷判栈满boolisFull(SqStack&s){returns.top==MAXSIZE;}⑸读取栈顶元素ElemTypepeek(SqStack&s){if(s.top==0){cerr<<"Stackisempty!"<

7、

8、行操作②表示同线性表③头指针--栈顶指针链栈的结构可用C++语言定义如下：structLNode{ElemTypedata;Lnode*next;};LNode*top;3.2栈的应用举例由于栈的操作具有后进先出的固有特性，致使栈成为程序设计中的有用工具。凡应用问题求解的过程具有"后