资源描述：
《2019 栈栈应用举例队列ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、3.1栈3.2栈的应用举例3.3队列第3章栈和队列重点:(1)栈、队列的定义、特点、性质和应用；(2)ADT栈、ADT队列的设计和实现以及基本操作及相关算法。难点:(1)循环队列中对边界条件的处理；(2)分析栈和队列在表达式求值、括号匹配、数制转换、迷宫求解中的应用实例，提高利用栈和队列解决实际问题的应用水平。本章重点难点3.1栈3.2栈的应用举例3.3队列第3章栈和队列3.1栈3.1.1抽象数据类型栈的定义3.1.2栈的表示和实现3.1.1抽象数据类型栈的定义栈的定义栈(Stack)是一种特殊的线性表，其插入和删除操作均在表的一端进行，是一种运算受限的线性表
2、。栈顶(top)是栈中允许插入和删除的一端。栈底(bottom)是栈顶的另一端。栈的术语栈的特点栈的示意图后进先出(LastInFirstOut，简称LIFO)。又称栈为后进先出表(简称LIFO结构)。an……a2a1栈底栈顶入栈出栈3.1.1抽象数据类型栈的定义ADTStack{数据对象：数据关系：抽象数据类型栈基本操作：}ADTStackR1＝{
3、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。D＝{ai
4、ai∈ElemSet,i=1,2,...,n,n≥0}见下页3.1.1抽象数据类型栈的定义InitStack(
5、&S)//初始化栈DestroyStack(&S)//销毁栈ClearStack(&S)//清空栈StackEmpty(S)//判栈空StackLength(S)//求栈长度GetTop(S,&e)//取栈顶元素Push(&S,e)//入栈Pop(&S,&e)//出栈StackTravers(S,visit())//遍历栈栈的基本操作3.1.1抽象数据类型栈的定义3.1栈3.1.1抽象数据类型栈的定义3.1.2栈的表示和实现3.1.2栈的表示和实现//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZE100;//存储空间初始分配量
6、#defineSTACKINCREMENT10;//存储空间分配增量typedefstruct{SElemType*base;//栈底指针SElemType*top;//栈顶指针intstacksize;//当前可使用最大容量}SqStack;SqStackS;顺序栈的C语言实现3.1.2栈的表示和实现栈初始化过程演示(1)给栈S申请栈空间(2)设置基地址S.base和栈顶地址SSS.base(3)设置栈容量S.stacksize=STACK_INIT_SIZEStatusInitStack(SqStack&S){//构造一个空栈SS.base=(ElemTy
7、pe*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}3.1.2栈的表示和实现栈初始化算法3.1.2栈的表示和实现入栈操作演示(1)如果栈满，给栈增加容量abcdef(2)将数据存入栈顶位置，栈顶后移一位SS.baseeSStatusPush(SqStack&S,SElemTypee){if(S-S.base>=S.stacksize){S.base=(ElemTy
8、pe*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S++=e;returnOK;}3.1.2栈的表示和实现入栈操作演示3.1.2栈的表示和实现DestroyStack(&S)//销毁栈ClearStack(&S)//清空栈StackEmpty(S)//判栈空StackLength(S)//求栈长度GetTop(S
9、,&e)//取栈顶元素Pop(&S,&e)//出栈StackTravers(S,visit())//遍历栈其它栈操作讨论TypedefstructSNode{ElemTypedata;//数据域structSnode*next;//链域}SNode,*LinkStack;3.1.2栈的表示和实现链栈的C语言类型定义链栈的实现与链表的实现基本相同，头结点作为栈顶位置。LinkStack*top;//栈顶指针InitStack(&S)//初始化栈DestroyStack(&S)//销毁栈ClearStack(&S)//清空栈StackEmpty(S)//判栈空St
10、ackLength(S)//求栈长度G
