资源描述：
《数据结构第3章栈和队列ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、栈和队列1、栈和队列的定义及特点； 2、栈的顺序存储表示； 3、队列的顺序存储表示；队列的链接存储表示； 4、栈和队列的应用举例。教学内容限定仅在表尾进行插入或删除操作。3.1栈3.1.1抽象数据类型栈的定义栈的定义a1a2an-1an…栈顶(top)栈底(bottom)出栈进栈栈底元素栈顶元素栈：线性表后进先出(LIFO结构)。栈的抽象数据类型的定义ADTStack{数据对象：D＝{ai
2、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
3、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)操
4、作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALSE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的
5、栈顶元素，并用e返回其值。}ADTStack3.1.2栈的表示和实现顺序栈顺序栈：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。topbaseAtopBtopCtopDtopEtop空栈若再进行元素“出栈”操作，将产生“下溢”。top栈满若再进行元素“入栈”操作，将产生“上溢”。#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct{ ElemType*elem;//数组指针，指示线性表的基地址intlengt
6、h;//当前长度intlistsize;//当前分配的存储容量(以sizeof(ElemType)为单位)}SqList;SelemType*base;//栈底指针，它始终指向栈底的位置。SelemType*top;//栈顶指针。intstacksize;//当前分配的栈可使用的最大存储容量。Sqstack;注：base的值为NULL，表明栈结构不存在。#defineSTACK_INIT_SIZE100//栈存储空间的初始分配量#defineSTACKINCREMENT10//栈存储空间的分配增量栈的基本操作在顺序栈中的实现#definemaxs9;main(){intstack[maxs
7、];inttop=0;while(top0)e=stack[top-1];top-=1;}InitStackPushPoptop12toptoptop2topGetTop21StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemtype));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STAC
8、K_INIT_SIZE;returnOK;}//InitStackStatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINcrement)*sizeof(SElemtype));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}//PushStatusGetTop(
9、SqStackS,SElemType&e){if(S.top==S.base)returnERROR;e=*(S.top–1);returnOK;}//GetTopStatusPop(SqStack&S,SElemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//Pop栈顶指针链栈an注意:链栈中指针的方向an-1a1…^▲3.2栈的应用举例3.2.1
