数据结构 第三章栈和队列.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 栈和队列,教学目的,通过本章的学习，要求掌握栈和队列的定义，熟练掌握顺序和链接存储的栈和队列的算法设计及其程序实现，了解栈和队的各种应用。,本章主要介绍以下内容：,栈的概念、存储结构及其基本操作,队列的概念、存储结构及其基本操作,栈与队列的应用举例,重点：栈和队列的定义、特征；顺序栈、链栈的描述及基本操作实现算法；循环队列和链队列的基本操作实现算法。,难点：栈满、栈空的条件及描述方法；队满和队空的描述方法；循环队列上的插入、删除操作。,栈（,stack,）,栈的定义,栈的类型定义,栈的存储方式,栈的定义,栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在,线性表的一端,进行。,a,1,a,n,a,2,栈的示意图,栈顶,栈底,进栈,出栈,进行插入和删除的一端是浮动端，被称为栈顶,固定端一端被称为栈底,假设栈,S=(a,1,，,a,2,，,a,3,，,a,n,),，则,a,1,称为栈底元素，,a,n,为栈顶元素。栈中元素按,a,1,，,a,2,，,a,3,，,a,n,的次序进栈，退栈的第一个元素应为栈顶元素。,换句话说，栈的修改是按后进先出的原则进行的。,因此，栈称为后进先出表（,LIFO,）,Last In First Out,。,栈的类型定义,ADT Stack,数据对象,：,D=ai|ai,ElemSet,i=1,2,.,n n0,数据关系,：,R1=,|ai,ai+1,ElemSet,i=1,2,.,n-10,约定,a,n,端为栈顶，,a,1,端为栈底,基本操作,：,结构初始化,InitStack(&S,),操作结果：构造一个空栈,S,销毁结构,DetroyStack,(&S),初始条件：栈,S,已经存在,操作结果：销毁栈,S,引用型操作,StackEmpty(S,),/,判断,S,是否为空栈，若为空返回,True,，否则返回,False,StackLength(S,),/,得到栈,S,的元素个数，即栈的长度,GetTop(S,，,&e),/,得到,S,的栈顶元素，并将之放入变量,e,中,StackTraverse(S,visit,(),/,从栈底到栈顶遍历栈,S,，对每个元素调用,visit(),加工型操作,ClearStack(&S,),/,清空栈,S,Push(&S,e,),/,向栈中插入元素,e,为新的栈顶元素,Pop(&S,&e,),/,删除栈,S,的栈顶元素，并用,e,返回值,栈的存储方法,栈有两种存储表示方法,:,顺序存储和链式存储,由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。,栈的顺序存储结构简称为,顺序栈,，它是运算受限的线性表。因此，可用数组来实现顺序栈。,通常由一个一维数组和一个记录栈顶元素位置的变量组成。当栈中没有数据元素时，表示为栈空。栈顶元素所对应的下标值,top=-1,。,在刚才基础上执行,Push(S,A),后得到这种状态,又有三个元素,B,、,C,、,D,先后入栈，此时栈顶元素的下标值,top=3,。,栈已满。,在刚才状态下，执行两次,Pop(S,x,),运算后得到,Top-1,D,0,1,2,3,0,1,2,3,Top-,A,0,1,2,3,Top-,A,B,C,0,1,2,3,Top-,A,B,顺序存储结构,顺序栈的,C#,语言描述如下：,public class SeqStack,private int maxSize;/,顺序栈的容量,private char data;/数组，用于存储顺序栈的数据元素，这里存储的只有字符型,private int top;/,指示顺序栈的栈顶,maxSize,为栈中元素的最大容量。,data,域,:,为一个一维数组，用于存储栈中元素。,top,域,:,栈顶指针。取值范围为,0,MaxSize-1,。,top=-1,表示栈空，,top=MaxSize-1,表示栈满。,类的实现,public class SeqStack,private int maxSize;/,顺序栈的容量,private char data;/,数组，用于存储顺序栈的数据元素，这里存储的只有字符型,private int top;/,指示顺序栈的栈顶,public int MaxSize /,最大容量属性,get return maxSize;,set maxSize=value;,public int Top /,栈顶属性,get return top;,使用,SeqList,s=new,SeqList,(),生成一个,SeqList,类的对象实例,栈底元素为,栈顶指针为,进栈时需将,s.top,加,1,，退栈时需将,s.top,减,1,s.top,front=qrear=null;,int,QueueEmpty(linkqueue,*q),return qfront=null,void,EnQueue(linkqueue,*,q,datatype,x),queuenode,*p;,p=(,queuenode,*),malloc(sizeof(queuenode,);,pdata=x;,pnext=null;,if(QueueEmpty(q,),qfront=qrear=p;,else,qrearnext=p;,qrear=p;,Datatype,Dequeue(linkqueue,*q),datatype,x;,queuenode,*p,if(queueempty(q,),error(“queue,underflow”);,p=qfront;,x=pdata;,qfront=pnext;,if(q,rear=p),qrear=null;,free(p,);,return x;,习题,将,1,、,2,、,3,、,4,四个数分别按顺序入栈（即必须按照先,1,再,2,再,3,最后,4,的顺序入栈），但可以按照任意次序出栈。,问题,1,：若入栈次序为,push(1),，,pop(),，,push(2),，,push(3),，,pop(),，,pop(),，,push(4),，,pop(),，则出栈的数字序列为什么？,问题,2,：能否得到出栈的数字序列,4132,和数字序列,1342,，并说明问什么不能得到或如何得到,问题,3,：请分析,1,、,2,、,3,、,4,的,24,种排列中，哪些序列可以通过相应的入出栈得到并分别写出入出栈次序,用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试设计置空队、判队空、判队满、出队、入队及取队头元素等六个基本操作。,