堆栈堆栈的应用队列队列的应用.ppt

单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,堆栈,堆栈的应用,队列,队列的应用,第三章 堆栈和队列,2/24/2026,1,3.1 栈(Stack),只允许在一端插入和删除的顺序表,允许插入和删除,的一端称为,栈顶,(,top,),，,另一端称,为,栈底,(,bottom,),特点,后进先出,(,LIFO,),退栈,进栈,2/24/2026,2,进栈示例,2/24/2026,3,退栈示例,2/24/2026,4,栈的基本操作,1、初始化,2、进栈,3、退栈,4、取栈顶元素,5、判栈是否非空,6、置栈空,2/24/2026,5,进栈,seqstack*PUSH(seqstack*s,datatype x),if(s-top=maxsize-1),printf(“overflown”);return NULL;,else,s-top+;,s-datas-topx;,return s;,2/24/2026,8,退栈,datatype POP(seqstack*s),if(EMPTY(s)printf(“underflown”);return NULL;,else,s-top-;,return(s-datas-top+1);,2/24/2026,9,取栈顶,datatype TOP(seqstack*s),if(EMPTY(s)printf(“underflown”);return NULL;,else return(s-datas-top);,2/24/2026,10,两个堆栈共享空间,0,maxsize-1,lefttop,righttop,2/24/2026,11,栈的链接表示 链式栈,链式栈无栈满问题，空间可扩充,插入与删除仅在栈顶处执行,链式栈的栈顶在链头,适合于多栈操作,2/24/2026,12,栈的链接存储结构,链栈的结点定义,typedef int datatype;,typedef struct node,datatype data;,struct node*next;,linkstack;,2/24/2026,13,链栈的进栈算法,linkstack*PUSHLSTACK(linkstack*top,datatype x),linkstack*p;,pmalloc(sizeof(linkstack);,p-datax;p-nexttop;,return p;,2/24/2026,14,链栈的出栈算法,linkstack*POPLSTACK(linkstack*top,datatype*datap),linkstack*p;,if(top=NULL),printf(“under flown”);return NULL;,else,*dataptop-data;,ptop;,toptop-next;,free(p);,return top;,2/24/2026,15,例：,对于一个栈，给出输入项A、B、C，如果输入项序列,由ABC组成，试给出所有可能的输出序列。,A,进,A,出,B,进,B,出,C,进,C,出 ABC,A,进,A,出,B,进,C,进,C,出,B,出 ACB,A,进,B,进,B,出,A,出,C,进,C,出 BAC,A,进,B,进,B,出,C,进,C,出,A,出 BCA,A,进,B,进,C,进,C,出,B,出,A,出 CBA,不可能产生输出序列CAB,2/24/2026,16,栈的应用举例文字编辑器,seqstack s;,EDIT(),char c;,SETNULL(,cgetchar();,while(c!=*),if(c=#)POP(,else,if(c=)SETNULL(,else PUSH(,cgetchar();,2/24/2026,17,栈的应用递归函数,int FACT(int n),if(n=1)return(1);,else return(n*FACT(n-1);,2/24/2026,18,栈的应用表达式计算,中缀表达式：A+(B C/D),E,后缀表达式：ABCD/,E,+（逆波兰表达式）,后缀表达式特点,1、与相应的中缀表达式中的操作数次序相同,2、没有括号,2/24/2026,19,后缀表达式的处理过程,操作顺序,后缀表达式,ABCD/E+,T,1,C/D,ABT,1,E+,T,2,B T,1,AT,2,E+,T,3,T,2,E,AT,3,+,T,4,A+T,3,T,4,2/24/2026,20,A,B,C,D,E,A,B,C,T,1,A,B,T,2,A,T,3,2/24/2026,21,中缀表达式转换为后缀表达式,(,),#,(,#,frontmaxsize-1;,sq-rearmaxsize-1;,2/24/2026,30,顺序队列判队空,int EMPTY(sequeue*sq),if(sq-rear=sq-front),return(TRUE);,else,return(FALSE);,2/24/2026,31,顺序队列取队头元素,datatype FRONT(sequeue*sq),if(EMPTY(sq),printf(“queue is emptyn”);,return NULL;,else,return(sq-front+1)%maxsize);,2/24/2026,32,顺序队列入队,int ENQUEUE(sequeue*sq,datatype x),if(sq-front=(sq-rear+1)%maxsize),printf(“sequeue is fulln”;return NULL);,else,sq-rear(sq-rear+1)%maxsize;,sq-datasq-rearx;return(TRUE);,2/24/2026,33,顺序队列出队,datetype DEQUEUE(sequeue*sq),if(EMPTY(sq),printf(“queue is emptyn”);return NULL;,else,sq-front(sq-front+1)%maxsize;,return(sq-datasq-front);,2/24/2026,34,存储队列的数组被当作首尾相接的表处理。,队头、队尾指针,加,1,时从,maxSize,-,1,直接进到,0,，可用语言的取模,(,余数,),运算实现。,队头指针进,1,:,front,=(,front,+1)%,maxSize,;,队尾指针进,1:,rear,=(,rear,+1)%,maxSize,;,队列初始化：,front,=,rear,=0;,队空条件：,front,=,rear,;,队满条件：,(,rear,+1)%,maxSize,=,front,循环队列,(Circular Queue),2/24/2026,35,循环队列的进队和出队,2/24/2026,36,队列的链接表示 链式队列,队头在链头，队尾在链尾。,链式队列在进队时无队满问题，但有队空问题。,队空条件为,front=NULL,2/24/2026,37,链队列结点类型定义,typedef struct node,datatype data;,struct node*next;,linklist;,typedef struct,linklist*front,*rear;,linkqueue;,2/24/2026,38,链队列置队空,SETNULL(linkqueue*q),q-frontmalloc(sizeof(linklist);,q-front-nextNULL;,q-rearq-front;,2/24/2026,39,链队列判队空,int EMPTY(linkqueue*q),if q-front=q-rear),return(TRUE);,else,return(FALSE);,2/24/2026,40,链队列取队头结点,datatype FRONT(linkqueue*q),if(EMPTY(q),printf(“queue is emptyn”);,return NULL;,else,return(q-front-next-data);,2/24/2026,41,链队列入队,ENQUEUE(linkqueue*q,datatype x),q-rear-next(linklist*)malloc(sizeof(linklist);,q-rearq-rear-next;,q-rear-datax;,q-rear-nextNULL;,2/24/2026,42,链队列出队,datatype DEQUEUE(linkqueue*q),linklist*s;,if(EMPTY(q),printf(“queue is emptyn”);return NULL;,else,sq-front;,q-frontq-front-next;,free(s);,return(q-front-data);,2/24/2026,43,0,1,1,1,0,1,1,1,1,0,1,0,1,0,1,0,0,1,0,0,1,1,1,1,0,1,1,1,0,0,1,1,1,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1 2 3 4 5 6 7 8,1,2,3,4,5,6,队列的应用举例求迷宫的最短路径,2/24/2026,44,zx,zy,1,-1,0,2,-1,+1,3,0,+1,4,+1,+1,5,+1,0,6,+1,-1,7,0,-1,8,-1,-1,需要解决的问题1：如何从某一坐标点出发搜索其四周的邻点,2/24/2026,45,需要解决的问题2：如何存储搜索路径,需要解决的问题3：如何防止重复到达某坐标点,步,x,y,pre,1,1,1,0,2,2,2,1,3,3,3,2,4,3,4,3,2/24/2026,46,需要解决的问题4：如何输出搜索路径,1,12,13,14,15,16,17,18,19,20,x,1,5,2,5,6,5,6,6,5,6,y,1,6,6,3,1,7,5,4,8,8,pre,0,8,9,10,10,11,12,14,16,16,队列,2/24/2026,47,#define m 10,#define n 15,typedef struct,int x,y;,int pre;,sqtype;,sqtype sq400;,int mgm+1n+1;,int zx8,zy8;,2/24/2026,48,void mglj(),int i,j,v,front,rear,find x,y;,sq1.x1;sq1.y1;sq1.pre0;,front1;rear1;find=0;,maze11-1;,while(front=rear&!find),xsqfront.x;ysqfront.y;,for(v=1;v=8;v+),ix+zxv;,jy+zyv;,if(mgij=0),rear+;,sqrear.xi;sqrear.yj;,sqrear.prefront;,mazeij-1;,if(i=m)&(j=n),printlj(rear);,find=1;,front+;,if(!find)printf(“不存在路径n”);,2/24/2026,49,void printlj(int rear),int i;,i=rear;,do,printf(“n(%d,%d)”,sqi.x,sqi.y);,isqi.pre;,while(i!=0);,2/24/2026,50,