数据结构 教学课件 作者 宗大华 宗杰 黄芳 《数据结构》大本课件-3.ppt

《数据结构 教学课件 作者 宗大华 宗杰 黄芳 《数据结构》大本课件-3.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第3章堆栈与队列3.13.23.3本章讲述内容：堆栈队列堆栈与队列的应用3.1堆栈3.1.1堆栈的基本知识堆栈的定义1.若对线性表加以限定，使得插入和删除操作只能在它的某一端进行，那么这种线性表就被称为“堆栈”，简称为“栈”。所以，栈是一种特殊的线性表。堆栈的基本知识2.在一个栈中，被允许进行插入和删除的那一端称为“栈顶(Top)”，不能进行插入和删除的那一端称为“栈底(Bottom)”。.栈顶与栈底.进栈与出栈从当前栈顶处插入一个新元素，称此操作为“进栈(Push)”，插入的这个元素就成为了新的栈顶；从当前栈顶处

2、删除一个元素，称此操作为“出栈(Pop)”，这时栈中被删元素的下一个元素成为新的栈顶。topbottom(空栈)(栈顶、栈底)topbottom(有3个元素的栈)(栈底元素)(栈顶元素)a1a2a3出栈进栈.最后插入栈的元素肯定最先移出栈。因此，栈是一种具有“后进先出(LIFO)”逻辑特点的数据结构，其意思是元素到达栈的顺序与离开栈的顺序恰好是相反的。3.1.2堆栈的顺序存储实现新建顺序栈的算法算法3-1算法描述(1)算法分析(2)Create_Ss(Ss,Ss_top,Ss_max){elemtypeSs[MAX

3、*size];Ss_max=MAX;Ss_top=0;returnOk;}由于每个进栈元素所需存储量为size，故Ss申请的存储量应该是Ss_max×size。.324Ss_top=01Ss_maxSs_max×size~~~~高低顺序栈Ss地址方向刚建完的顺序栈其栈顶指针Ss_top为0，表明此时栈为空。随着元素进、出栈，用Ss_top计数，从1变化到Ss_max，它实际上就是数组的下标。.算法讨论(3)可以用C语言的数组来实现顺序栈。由于C语言的数组下标是从0开始的，因此最初应该把Ss_top设置成“−1”，变

4、化范围是从0到Ss_max-1，这在具体程序设计时应该注意。顺序栈的进栈算法算法3-2算法描述(1)算法分析(2)Push_Ss(Ss,Ss_top,Ss_max,x){if(Ss_top==Ss_max)returnERROR;else{Ss_top++;Ss[Ss_top]=x;}}插入时要先判断栈是否满，已经放有Ss_max个元素的栈是不可能再实施进栈操作的。在栈不满的前提下，该算法通过如下两条操作实现进栈：Ss_top++;Ss[Ss_top]=x;.当栈里有元素时，Ss_top的值有两个意义：总是指向当前

5、栈顶元素所在的栈位，总是当前栈里已有元素的个数。.若条件：Ss_top==Ss_max成立，表示栈Ss满，就不能再做进栈操作了。如果在顺序栈满时仍打算进栈，就称为发生了“上溢”出错。.A1Ss_top2顺序栈Ss3(Ss_max=6)4B56A1Ss_top2顺序栈Ss3(Ss_max=6)456A1Ss_top2顺序栈Ss3(Ss_max=6)4B56A1Ss_top2顺序栈Ss3(Ss_max=6)456CDEFBC顺序栈的出栈算法算法3-3算法描述(1)算法分析(2)Pop_Ss(Ss,Ss_top,x){i

6、f(Ss_top==0)printf("Thestackisempty!");else{x=Ss[Ss_top];Ss_top--;}}算法通过下面两条操作实现元素的出栈：x=Ss[Ss_top];Ss_top--;由于Ss_top总是指向栈中栈顶元素的位置，所以应先将里面内容读出送入变量x，然后调整Ss_top的指向，使其指向新的栈顶元素位置。.出栈时要注意栈是否为空。这通过条件：Ss_top==0来判断。如果在顺序栈空时仍打算出栈，就称为发生了“下溢”出错。.ASs_topASs_topASs_topASs_t

7、opASs_topASs_topASs_topSs_top栈空A进栈B进栈B出栈C进栈D进栈E进栈E出栈BBCCDCDECDE获取顺序栈栈顶元素的算法算法3-4算法描述(1)算法分析(2)遍历顺序栈算法算法3-5算法描述(1)算法分析(2)Get_Ss(Ss,Ss_top,x){if(Ss_top==0)printf("Thestackisempty!");elsex=Ss[Ss_top];}获取顺序栈栈顶元素的操作与出栈操作是不一样的。对比算法3-3可以知道，这里没有调整Ss_top的操作。Display_Ss(

8、Ss,Ss_top){i=Ss_top;for(i,i>=0,i--)printf("%d",Ss[i]);}由于要从顺序栈的栈顶到栈底逐个加以显示，所以用for循环来实现。开始先把Ss_top赋予变量i后，进入for循环，打印一个元素，变量i就减1，当i变为0，表明已到达栈底了。注意，操作“i=Ss_top;”是非常必要的。若没有它，而是直接使用Ss_to