资源描述：
《《栈和队列》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1第三章栈和队列3.1栈3.2栈的应用举例3.4队列2通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n栈和队列是两种常用的数据类型3学习提要：1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述
2、方法。3.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。重难点内容：顺序栈的相关操作、循环队列的判空判满43.1栈（stack）3.1.1栈的类型定义3.1.2栈的表示和实现5栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈。ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)特点：先进后出（FILO）或后进先出（LIFO）3.1.1栈的类型定义6ADTStack{数据对象：D＝{ai
3、ai∈ElemSet,i=1,2,...
4、,n,n≥0}数据关系：R1＝{
5、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：}ADTStack栈的类型定义7InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())8顺序栈3.1.2栈的表示和实现类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。//-----栈的顺序存储表示
6、-----#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;9实现：一维数组s[M]top123450进栈A栈满BCDEF设数组维数为Mtop=base,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450空栈topbasebasetop出栈toptop栈空base栈底
7、指针base,始终指向栈底位置；栈顶指针top,其初值指向栈底，始终在栈顶元素的下一个位置123450ABtop10StatusInitStack(SqStack&S){//构造一个空栈SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}11StatusPush(SqStack&S,SElemT
8、ypee){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;}12StatusPop(SqStack&S,SElemType
9、&e){//若栈不空，则删除S的栈顶元素，//用e返回其值，并返回OK；//否则返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}130M-1栈1底栈1顶栈2底栈2顶在一个程序中同时使用两个栈14链栈栈的链式存储结构。栈顶指针就是链表的头指针。栈顶指针∧a1an注意:链栈中指针的方向an-1注意:链栈中指针的方向注意：链栈中的指针方向15入栈操作出栈操作^…...栈底toptopxptop^…...栈底topqp->next=top;top=pq=top;top=top
10、->next163.2栈的应用3.2.1数制转换3.2.2括号匹配的检验3.2.3行编辑程序问题3.2.4迷宫求解3.2.5表达式求值173.2.1数制转换十进制N和其他d进制数的转换原理:N=(Ndivd)*d+Nmodd其中：di
