《栈和队列数据结构教程.pptx》由会员分享，可在线阅读，更多相关《栈和队列数据结构教程.pptx（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、3.1 栈3.2栈的应用举例3.3 队列3.4 队列的应用举例第1页/共22页3.1 栈 3.1.1 栈的定义栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示：进行插入和删除的一端是浮动端，通常被称为栈顶，并用一个“栈顶指针”指示；而另一端是固定端，通常被称为栈底。我们经常将栈用下图3-1的形式描述：a1,a2,a3,.,an 插入和删除插入和删除端端第2页/共22页图图 3-1第3页/共22页结论：后进先出（LastInFirstOut），简称为LIFO线性表。举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，
2、一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。举例2：死胡同。举例3：对一栈，给定的输入项目A,B,C,若输入的顺序是A,B,C，试给出全部的可能的输出序列。下面我们先给出栈结构的基本操作：（1）初始化栈Init_Stack(S)（2）入栈Push_Stack(S,x)（3）出栈Pop_Stack(S)（4）获取栈顶元素内容Top_Stack(S)（5）判断栈是否为空Empty_Stack(S)第4页/共22页 3.1.2 栈的顺序存储栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。类型定义如下所示：#defineMAXSIZE100typedef
3、structdatatypedataMAXSIZE;inttop;SeqStack定义一个指向顺序栈的指针：SeqStack*s;第5页/共22页基本操作算法：置空栈：首先建立栈空间，然后初始化栈顶指针。SeqStack*Init_SeqStack()SeqStack*s;s=malloc(sizeof(SeqStack);s-top=-1;returns;判空栈intEmpty_SeqStack(SeqStack*s)if(s-top=-1)return1;elsereturn0;第6页/共22页图3-2第7页/共22页入栈intPush_SeqStack(SeqStack*s,dataty
4、pex)if(s-top=MAXSIZE-1)return0;/*栈满不能入栈*/elses-top+;s-datas-top=x;return1;出栈intPop_SeqStack(SeqStack*s,datatype*x)if(Empty_SeqStack(s)return0;/*栈空不能出栈*/else*x=s-datas-top;s-top-;return1;/*栈顶元素存入*x，返回*/第8页/共22页取栈顶元素datatypeTop_SeqStack(SeqStack*s)if(Empty_SeqStack(s)return0;/*栈空*/elsereturn(s-datas-t
5、op);以下几点说明：1.对于顺序栈，入栈时，首先判断栈是否满了，栈满的条件为：s-top=MAXSIZE-1，栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。2.出栈和读栈顶元素操作，先判断栈是否为空，为空时不能操作，否则产生错误。通常栈空时常作为一种控制转移的条件。第9页/共22页 3.1.3 栈的链式存储若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图3-3所示。由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所
6、以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。第10页/共22页链式栈:栈的链接表示链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作top如图3-3第11页/共22页栈的链式存储结构在C语言中可用下列类型定义实现：typedefstructnodedatatypedata;structnode*next;StackNode，*LinkStack;说明top为栈顶指针：LinkStacktop;第12页/共22页下面我们将给出链栈各项基本操作的算法。置空栈Init_LinkStack（LinkStacktop）topNULL;判栈空intE
7、mpty_LinkStack（LinkStacktop）if（top=NULL）return1;elsereturn0;第13页/共22页入栈LinkStackPush_LinkStack（LinkStacktop,datatypex）StackNode*s;s=malloc（sizeof（StackNode）;s-data=x;s-next=top;top=s;returntop;第14页/共22页出栈LinkStackPop_LinkStack(LinkStacktop,datatype*x)StackNode*p;if（top=NULL）returnNULL;else*x=top-dat
8、a;p=top;top=top-next;free(p);returntop;第15页/共22页例3.1简单应用：数制转换问题将十进制数N转换为r进制的数，其转换方法利用辗转相除法：以N=3467，r=8为例转换方法如下：NN/8（整除）N%8（求余）34674333低4335415466606高所以：（3467）10=（6613）83.2 栈的应用举例第16页/共22页我们看到所转换的8进制数按低位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。算法思想如下：当N0时重复1，21若N0，则将
9、N%r压入栈s中，执行2;若N=0，将栈s的内容依次出栈，算法结束。2用N/r代替N第17页/共22页#defineL10voidconversion(intN，intr)intsL,top;/*定义一个顺序栈*/intx;top=-1;/*初始化栈*/while(N)s+top=N%r;/*余数入栈*/N=N/r;/*商作为被除数继续*/while(top!=-1)x=stop-;printf(“%d”,x);第18页/共22页课堂练习：I表示入栈，O表示出栈，若元素入栈顺序为1234，为了得到1342的出栈顺序，相应的I和O的操作串是什么？I1O1I2I3O3I4O4O2第19页/共22页main()inti,e,a=1,2,3,4,5,6,7,8,9;SeqStacks;Initstack(s);for(i=0;i9;i+)push(s,ai);/入栈while(!Stackempty(s)pop(s,e);/出栈printf(“%2d”,e)课堂练习：第20页/共22页作业：3.33.43.5第21页/共22页感谢您的观看！第22页/共22页