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

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

1、数据结构-栈和队列课件栈（Stack）1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式队列（Queue）1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式3.1栈定义只能在表的一端（栈顶）进行插入和删除运算的线性表逻辑结构与线性表相同，仍为一对一关系存储结构用顺序栈或链栈存储均可，但以顺序栈更常见运算规则只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则实现方式关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同基本操作有入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空等顺序栈的表示

2、空栈base==top是栈空标志stacksize=4topAbasebasetopABABCtopbasetopbaseABCDbasetop3120top指示真正的栈顶元素之上的下标地址栈满时的处理方法：1、报错,返回操作系统。2、分配更大的空间，作为栈的存储空间,将原栈的内容移入新栈。#defineMAXSIZE100typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;顺序栈的表示构造一个空栈步骤：(1)分配空间并检查空间是否分配失败，若失败则返回错

3、误顺序栈初始化basestacksizetops(2)设置栈底和栈顶指针S.top=S.base;(3)设置栈大小StatusInitStack(SqStack&S){S.base=newSElemType[MAXSIZE]；if(!S.base)returnOVERFLOW;S.top=S.base;S.stackSize=MAXSIZE;returnOK;}顺序栈初始化判断顺序栈是否为空boolStackEmpty(SqStackS){if(S.top==S.base)returntrue;elsereturnfalse;}ba

4、setop3120求顺序栈的长度intStackLength(SqStackS){returnS.top–S.base;}basetopABStatusClearStack(SqStackS){if(S.base)S.top=S.base;returnOK;}清空顺序栈basetop3120StatusDestroyStack(SqStack&S){if(S.base){deleteS.base;S.stacksize=0;S.base=S.top=NULL;}returnOK;}销毁顺序栈(1)判断是否栈满，若满则出错(2)元素e

5、压入栈顶(3)栈顶指针加1顺序栈进栈StatusPush(SqStack&S,SElemTypee){if(S.top-S.base==S.stacksize)//栈满returnERROR;*S.top++=e;returnOK;}*S.top=e;S.top++;ABCtopbase(1)判断是否栈空，若空则出错(2)获取栈顶元素e(3)栈顶指针减1顺序栈出栈StatusPop(SqStack&S,SElemType&e){if(S.top==S.base)//栈空returnERROR;e＝*--S.top;returnOK;

6、}--S.top;e=*S.top;ABCtopbase判断是否空栈，若空则返回错误否则通过栈顶指针获取栈顶元素取顺序栈栈顶元素StatusGetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;//栈空e=*(S.top–1);returnOK;}e=*(S.top--);???ABCtopbase435612中到了12顺序不能实现；135426可以实现。1.如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？练习练习Ａ．iＢ．n-iＣ．n-

7、i+1Ｄ．不确定Ｃ2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为练习Ａ．top不变Ｂ．top=0Ｃ．top++Ｄ．top--D3.在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为b[0]t[0]t[1]b[1]0m-1V双栈共享一个栈空间优点：互相调剂，灵活性强，减少溢出机会将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的

8、栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长（如下图所示）。bot[0]top[0]top[1]bot[1]0m-1Vtypedefstruct{inttop[2],bot[2];//栈顶和栈底指针SElemType