数据结构第3章栈和队列课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,栈(Stack),队列(Queue),栈和队列的应用,第三章 栈和队列,栈(Stack)第三章 栈和队列,1,操作原则,后进先出,(,LIFO,),3.1,栈(Stack),top,bottom,a,1,a,n,a,n-1,进栈,a,1,a,n,出栈,a,n,a,1,只允许在一端插入和删除的,线性表,S=（,a,1,a,2,a,3,a,n-1,a,n,）,允许插入和删除的一端称为,栈顶,(,top,)，,另一端称为,栈底,(,bottom,),top,bottom,a,1,a,n,a,n-1,x,操作原则3.1 栈(Stack)topbott,2,ADT List,数据对象:,D=a,i,|1,i,n,n,0,a,i,属Elemtype类型,数据关系:,R1=|a,i,a,i+1,D,i=1,2,n-1,基本运算:,InitStack(,ClearStack(S);,StackEmpty(S);,StackLength(S):,Push(,Pop(&S,&e),GetTop(S,DispStack(S);,抽象数据类型栈的定义,ADT List抽象数据类型栈的定义,3,typedef struct,/,顺序栈定义,ElemType datamaxsize,;,/,栈数组,int,top,;,/,栈顶指针,SqStack,;,顺 序 栈,top(,栈空,),0 1 2 3 4 5 6 7 8 9 maxsize-1,data,c,a,b,顺 序 栈top(栈空)0 1 2,4,top,空栈,top,a,进栈,a,top,a,b,c,d,e,f,进栈溢出,top,b,进栈,a,b,top,a,b,c,d,e,e,进栈,top,a,b,d,e,e,退栈,c,top空栈topa 进栈a topabcd,5,top,空,栈,top,a,b,d,d,退栈,c,c,退栈,top,a,b,c,b,退栈,a,b,top,a,a,退栈,top,top空栈topabdd 退栈cc 退栈topabcb 退栈,6,void,InitStack,(SqStack,*&S,),/,置空栈,S=(,SqStack,*)malloc(sizeof(,SqStack,);,S,-,top,=,-1,;,return;,bool,StackEmpty,(,SqStack,*S),/,判断栈是否空？空则返回1，否则返回0,if(S-top=-1)return,false,;,else return true;,void InitStack(SqStack*&S),7,bool,push(SqStack*&S,ElemType e),/,若栈满返回0,否则,新元素,x,进栈并返回1,if(,S-top=maxsize-1)return false;,S-top+;,S,-,dataS,-,top,=e,;,/,加入新元素,return true;,bool pop(SqStack*&S,ElemType&e),/,若栈空返回0,否则栈顶元素读到,x,并返回1,if(S-top=-1)return false;,e=S,-,dataS,-,top;S-top-;,return true;,bool push(SqStack*&S,ElemTy,8,栈 1 top,1,top,2 栈2,0 MaxSize-1,data,双栈共享一个栈空间,进栈 退栈,栈1,top1+;datatop1=x;,x=datatop1;top1-;,栈2,top2-;datatop2=x;,x=datatop2;top2+;,栈满？,栈空？,数据类型,typedef struct,ElemType dataMaxSize,;,int,top1,top2,;,D,seqStack,;,基本运算,push(&S,i,x),pop(&S,i,&x),stackempty(S,i),栈 1 top1 top2,9,链 式 栈,注：每个结点的指针指向直接前驱,结点结构：,data next,数据类型：,typedef struct linknode,ElemType data;,struct linknode *next;,LiStack;,LiStack*s;,/top,确定链栈,s,a,b,c,链 式 栈注：每个结点的指针指向直接前驱结点结构：dat,10,s,a,b,p,x,p-next=s-next,生成新结点p,s-next=p,链式栈操作的实现,void,push(LiStack*&S,ElemType e),LiStack,*p;,p=(LiStack*),malloc,(,sizeof,(LiStack),;,p,-,data=e,;,p,-,next=S-next,;,S-next=p;,进栈,sabpxp-next=s-next生成新结,11,p=s-next,s-next=p-next,退栈,s,a,b,c,p,bool,StackEmpty(LiStack*S),if(S-next=NULL),return true,;,return false;,bool pop(LiStack*&S,ElemType,*,e),if,(S-next=NULL),return,false,;,p=S-next,;,S-next=p-next;,e,=p,-,data,;,free,(p),;,return,true,;,p=s-nexts-next=p-next退栈sabc,12,3.2,栈的应用,例如：函数的嵌套调用,main()f1()f2()f3(),f1();f2();f3();,r1:r2:r3:,依次保存r1、r2、r3，而返回时依次取出r3、r2、r1返回调用函数，,后进先出,，利用栈保存返回地址。,注,：为确保正确返回调用函数，则需要保存返回地址。,r1,r2,r3,r1,r2,r3,3.2 栈的应用例如：函数的嵌套调用main(),13,1 1 1 1 1 1 1 1 1,1 1,1 1,1 1,1 1,1 1,1,1 1,1 1 1 1 1 1 1 1 1,0 1 1 1 0 1 0,1 0 0 0 0 1 1,0 1 0 1 0 1 1,0 1 0 1 1 1 0,1 0 1 0 1 0 1,0 0 1 0 0 0 1,1 1 0 0 1 1 0,例如：迷宫问题,(x,y),(x+1,y),(x-1,y),(x-1,y-1),(x,y-1),(x+1,y-1),(x+1,y+1),(x,y+1),(x-1,y+1),(1,1,2),(2,2,1),(2,3,1),(2,4,1),(2,5,3),(3,5,?),(2,5,7),(1,5,?),(2,4,4),(3,3,3),(4,3,2),1 1 1 1 1 1 1 1,14,例如：表达式的计算,中缀表达式:,#A+(B C/D)*E#,后缀表达式:,#A B C D/-E*+#,问题：,由于各运算优先级别不同，计算机很难实现。,注：,只有当扫描到运算符时，才可进行运算，因此，需要先保存已扫描的操作数。由于后保存的数先进行运算，满足,后进先出,的原则，所以利用栈来保存操作数及每次运算的结果。,A,B,C,D,/:,R1=C/D,R1,-:,R2=B-R1,R2,*:,R3=R2*E,+:,R4=A+R3,R4,E,R3,例如：表达式的计算中缀表达式:#A+(B C,15,允许删除的一端叫做队头(,front,)，,允许插入的一端叫做队尾(,rear,)。,front,rear,a,1,a,2,a,n,-1,a,n,3.3,队列(,Queue),队列是只允许在一端删除，在另一端插入的线性表,操作原则,先进先出(,FIFO,First In First Out,),x,队尾插入,a,1,队头删除,允许删除的一端叫做队头(front)，frontreara1,16,ADT List,数据对象:,D=a,i,|1,i,n,n,0,a,i,属Elemtype类型,数据关系:,R1=|a,i,a,i+1,D,i=1,2,n-1,基本运算:,InitQueue(,ClearQueue(,QueueEmpty(Q);,QueueLength(Q):,EnQueue(,DeQueue(&Q,&e),GetFront(Q,抽象数据类型队列的定义,ADT List抽象数据类型队列的定义,17,typedef int,ElemType,;,typedef struct,ElemType dataMaxSize,;,int,front,rear,;,SqQueue,;,队列的顺序存储表示 顺序队列,0 2 3 4 5 6 7 8 9 MaxSize-1,data,a b c d,rear,（指向队尾元素）,front,（指向队头之前）,typedef int ElemType;队列的顺序存储表示,18,队列的进队和出队,front,rear,空队列,front,rear,A,进队,A,front,rear,B,进队,A B,front,rear,B,退队,C D,front,rear,C,D,进队,A B C D,front,rear,A,退队,B C D,队列的进队和出队 frontrear空队列frontrea,19,队列的进队和出队的操作,解决办法之一：将队列元素存放数组首尾,相接，形成,循环(环形)队列,。,进队：,rear=rear+1,datarear=x,出队:,fro,nt=front+1,x=,datafront,H进,队,溢出,C D E F,front,rear,1 2 3 4 5 6 7,G,G,进队,C出,队,？,“假溢出”,？,满,？,空,H,rear,rear,队列的进队和出队的操作解决办法之一：将队列元素存放数组首尾进,20,循环队列(Circular Queue),front,rear,6,MaxSize-1,0,1,2,3,4,5,D,A,B,C,.,循环队列(Circular Queue)frontrear,21,0,1,2,3,4,5,6,7,front,rear,front,0,1,2,3,4,5,6,7,A,rear,front,0,1,2,3,4,5,6,7,A,B,C,rear,队列初值,A,进队,B,C,进队,A,退队,B,退队,front,rear,0,1,2,3,4,5,6,7,B,C,rear,front,0,1,2,3,4,5,6,7,B,C,A,0,01234567frontrearfront01234567,22,Y,进队,rear,front,6,7,0,1,2,3,4,5,X,W,Y,Z,Z,进队,rear=rear+1,()%MaxSize,6,7,0,1,2,3,4,5,B,A,C,B,A,rear,A,出队,B,出队,front=front+1,()%MaxSize,front,？,空,C,出队,front,front,C,front=rear,rear,A,B,C,D,？,满,rear,A B C,进队,D,进队,front=rear,？如何区别满和空,Y进队rearfront67012345XWYZZ进队rea,23,6,7,0,1,2,3,4,5,X,W,Y,Z,A,B,C,方法一,：,增加一个存储单元n,用于存储队列的长度,n=0,空,n=MaxSize,满,方法二,：,利用队列中最后一个,存储单元标志满,空：,front=rear,满:,rear,front,front=rear+1,()%MaxSize,67012345XWYZA B C 方法一：增加一个存储单元,24,void,Initqueue(SqQueue*&Q),Q=(SqQueue*)malloc(sizeof(SqQueue);,Q,-,rear=Q,-,front=0,;,bool,QueueE