c++课件栈和队列资料.ppt

《c++课件栈和队列资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、栈栈的应用队列队列的应用第三章栈和队列栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS§3.1栈（stack）1.栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，通常称插入、删除的这一端，即表尾为栈顶(Top)，另一端表头为栈底(Base)，不含元素的空表称空栈。特点：先进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)2.栈的存储结构(1)顺序栈由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序

2、存储结构简称为顺序栈，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个变量top来指示当前栈顶的位置，通常称top为栈顶指针。栈顶指针top,指向实际栈顶后的空位置top123450进栈Atop出栈栈满BCDEFtoptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空basebase栈空topbase012345设栈的初始容量为Stacksizetop=base,栈空

3、，此时出栈则下溢（underflow)top-base>=Stacksize,栈满，此时入栈则上溢（overflow)顺序栈的存储顺序存储栈的结点类型的定义：#defineSTACK_INIT_SIZE100;//存储空间初始分配量#defineSTACKINCREMENT10;//存储空间分配增量typedefstruct{SElemType*base;//栈底指针SElemType*top;//栈顶指针intstacksize；//当前已分配的存储空间}sqStack;顺序栈入栈算法Push(sq

4、Stack&s,SElemTypee){if(s.top-s.base>=s.stacksize){s.base=(SElemtype*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!s.base)exit(“失败‘）；s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}*s.top++=e;}0M-1栈1底栈1顶栈2底栈2顶在一个程序中同时使用两个栈顺序栈出

5、栈算法StatusPop(sqStack&s,SElemType&e){if(s.top==s.base)returnERROR；--s.top;*e=*s.top;returnOK;}[例1：]多进制输出：例把十进制数159转换成八进制数(159)10=(237)81598198280237余7余3余2toptop7top73top732例1的解法：nndiv8nmod81591971923202voidconversion(){//教材48页initstack(s);//构造空栈，见教材47页sc

6、anf(“%”,n);while(n){push(s,n%8);//入栈n=n/8;}while(!Stackempty(s))//判断是否为空栈，见教材46页{pop(s,e);//出栈,e为出栈元素printf(“%d”,e);}}[例2：]假设以I和O分别表示入栈和出栈，栈的初态和终栈均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，下列所示的序列中，不合法的是()A.IOIIOIOOB.IOOIOIIOC.IIOOIOIOD.IIIOOIOO[例3:]一个栈的入栈序列为a，b，c，d，

7、e，则出栈的不可能序列为（）。A、edcbaB、decbaC、dceabD、abcde[例4:]设有一顺序栈S，元素s1、s2、s3、s4、s5、s6依次入栈，如果6个元素出栈的顺序是s2、s4、s3、s6、s5、s1，则栈的容量至少应该是（）A、2B、3C、5D、62.栈的存储结构(2)链栈栈顶^…...topdatalink栈底链栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链栈的栈顶在链头适合于多栈操作结点定义：typedefintdatatype;typedefstructnode{data

8、typedata;structnode*link;}JD;入栈算法出栈算法^…...栈底toptopxptop^…...栈底topq回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文字符串：“madamimadam”3.栈的应用表达式求值（前提规则见教材52、53页）读一个字符，如为操作数，直接入到操作数栈；否则即为运算符，需判断：1、如当前