第3章-栈及队列.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 栈和队列,本章内容,3.1,栈,3.1.1 栈的定义及基本运算,3.1.2 栈的存储结构和实现,3.1.3 栈的应用,3.2,队列,3.2.1,队列的定义及基本运算,3.2.2,队列的存储结构和实现,3.2.3,队列的应用,3.1.1 栈的定义及基本运算,栈(,Stack),的定义,栈,(Stack),是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶,(top),另一端为栈底,(bottom),。当表中没有元素时称为空栈。,a,n,a,n-1,.,a,2,a,1,栈底,栈顶,入栈,出栈,栈的特点,栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（,LIFO）。,3.1.1 栈的定义及基本运算,栈的运算演示,(1)A、B、C、D,四个元素依次进入一个栈，再依次出栈，得到一个输出序列,DCBA。,D,C,B,A,ABCD,DCBA,3.1.1 栈的定义及基本运算,栈的运算演示,(1)A、B、C、D,四个元素依次进入一个栈，再依次出栈，得到一个输出序列,DCBA。,(2)能否由入栈序列,A、B、C、D、E,得到出栈序列,CBDAE？,ABCDE,操作序列：,出栈序列：,元素,A,入栈,A,A,元素,B,入栈,B,B,元素,C,入栈,C,C,3.1.1 栈的定义及基本运算,栈的运算演示,(1)A、B、C、D,四个元素依次进入一个栈，再依次出栈，得到一个输出序列,DCBA。,(2)能否由入栈序列,A、B、C、D、E,得到出栈序列,CBDAE？,DE,操作序列：,出栈序列：,元素,A,入栈,A,元素,B,入栈,B,元素,C,入栈,元素,C,出栈,C,C,元素,B,出栈,B,3.1.1 栈的定义及基本运算,栈的运算演示,(1)A、B、C、D,四个元素依次进入一个栈，再依次出栈，得到一个输出序列,DCBA。,(2)能否由入栈序列,A、B、C、D、E,得到出栈序列,CBDAE？,DE,操作序列：,出栈序列：,元素,A,入栈,A,元素,B,入栈,元素,C,入栈,元素,C,出栈,C,元素,B,出栈,B,元素,D,入栈,D,D,元素,D,出栈,D,元素,A,出栈,A,3.1.1 栈的定义及基本运算,栈的运算演示,(1)A、B、C、D,四个元素依次进入一个栈，再依次出栈，得到一个输出序列,DCBA。,(2)能否由入栈序列,A、B、C、D、E,得到出栈序列,CBDAE？,E,操作序列：,出栈序列：,元素,A,入栈,元素,B,入栈,元素,C,入栈,元素,C,出栈,C,元素,B,出栈,B,元素,D,入栈,元素,D,出栈,D,元素,A,出栈,A,元素,E,入栈,E,E,元素,E,出栈,E,栈的基本运算,InitStack(&S,):,初始化栈,S,StackEmpty,():,判断栈是否为空,Push(e):,将元素,e,放入栈顶,Pop(e):,移走栈顶的元素，同时由,e,带回该元素的值,Gettop,():,获取栈顶的元素，但不从栈中移走,3.1.1 栈的定义及基本运算,3.1.2 栈的存储结构和实现,a,n,a,n-1,.,a,2,a,1,栈,base,top,栈的表示和实现,假设栈,S=(a,1,，,a,2,，,a,3,，,，,a,n,),，则,a,1,称为栈底元素,，,a,n,为栈顶元素,。栈中元素按,a,1,，,a,2,，,a,3,，,a,n,的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为,后进先出表,(Last In First Out,，,LIFO),3.1.2 栈的存储结构和实现,顺序栈,由于栈是,运算受限的线性表,，因此线性表的存储结构对栈也适应。,栈的顺序存储结构简称为顺序栈,，它是运算受限的线性表。因此，可用数组来实现顺序栈。,3.1.2 栈的存储结构和实现,顺序栈的类型定义,/,-栈的顺序存储表示-,#,define STACK_INIT_SIZE 100,#define STACKINCREMENT 10,typedef,struct,ElemType,*base;,/,栈底指针，栈构造前和销毁后为空,ElemType,*top;,/,栈顶指针，指向栈顶元素的下一位置,int,stacksize,;,/,当前分配的栈的存储空间数,SqStack,;,顺序栈,设,S,是,SqStack,类型的指针变量。,base,是栈底指针。,Top,是栈顶指针。,栈不存在条件,S.base,=NULL,栈空条件,S.top,=,S.base,插入栈顶元素，栈顶指针,S.top,=S.top+1,删除栈顶元素，栈顶指针,S.top,=S.top-1,栈满条件,S.top-S.base,=,S.stacksize,3.1.2 栈的存储结构和实现,3.1.2 栈的存储结构和实现,顺序栈的,C,语言实现,(1)初始化,Status,InitStack(SqStack,&S),/,构造一个空栈,S.base,=(,ElemType,*),malloc(STACK_INIT_SIZE,*,sizeof(ElemType,);,if(!S.base,)exit(OVERFLOW);,S.top,=S.base;,S.stacksize,=,STACK_INIT_SIZE;,return OK;,/,InitStack,(2),判断栈空,int,StackEmpty(SqStack,*S),return(S.base,=,S.top,);,(3),判断栈满,int,StackFull(SqStack,*S),return(S.top-S.base,=,S.stacksize,);,3.1.2 栈的存储结构和实现,3.1.2 栈的存储结构和实现,(,4),元素入栈,Status,Push(SqStack,&S,ElemType,e),/,插入元素,e,为新的栈顶元素,if(,S.top,S.base,=,S.stacksize,),return ERROR;/,栈满,*,S.top,=e;,S.top,+,;,return OK;,/Push,请自学其他操作的实现算法。,3.1.2 栈的存储结构和实现,链栈,栈的链式存储结构称为链栈,，它是运算是受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。,栈顶指针就是链表的头指针,。,链栈的类型说明如下：,typedef,struct,stacknode,SElemType,data;,struct,stacknode,*next;,stacknode,;,3.1.2 栈的存储结构和实现,链栈,a,n,a,n-1,.,a,2,a,1,栈,栈底,栈顶,S,栈的链式存储,a,n,a,n-1,a,1,a,2,思考,链栈是否需要另外设置头指针？,建立链栈适合用哪种插入法？,链栈的基本操作的实现。,链栈的基本操作,置空栈,void,InitStack(SqStack,*p),ptop=NULL;,判断栈空,int,StackEmpty(linkstack,*p),return ptop=NULL;,3.1.2 栈的存储结构和实现,链栈的基本操作,进栈,void,Push(linkstack,*,p,SElemType,e),stacknode,*q;,q=(,stacknode,*),malloc(sizeof(stacknode,);,qdata=e;,qnext=ptop;,ptop=q;/,设置栈顶指针,3.1.2 栈的存储结构和实现,链栈的基本操作,退栈,SElemType,Pop(linkstack,*p),SElemType,x;,stacknode,*q=ptop;,if(StackEmpty(p,),error(“stack,underflow.”);,x=qdata;,ptop=qnext;,/,删除栈顶元素,free(q,);,return x;,3.1.2 栈的存储结构和实现,链栈的基本操作,取栈顶元素,SElemType,GetTop(linkstack,*p),if(StackEmpty(p,),error(“stack,is empty.”);,return,ptopdata;,3.1.2 栈的存储结构和实现,3.,2,栈的应用举例,根据栈的,FILO,特性，用作某些处理问题的工具。,数制转换,例：,43,10,=101011,2,被除数,除数,商,余数,43,2,21,1,21,2,10,1,10,2,5,0,5,2,2,1,2,2,1,0,1,2,0,1,0,输出,void conversion(),InitStack(S,);/,构造空栈,scanf,(“%,d”,&n,);,while(n,),Push(S,n%2);,n=n/2;,while(!,StackEmpty(S,),Pop(S,e,);,printf(“%d”,e,);,3.,2,栈的应用举例,括号匹配,设一个表达式中可以包含三种括号：“(”和“)”、“”和“”、“”和“”，并且这三种括号可以按照任意的次序,嵌套,使用，考查表达式中的括号是否匹配。例如：,.(.).).,例：,a=b+(c-d)*(e-f);,while(m(a8+t)m=m+1;t=t-1;,实现方法利用栈进行表达式中的括号匹配,自左至右扫描表达式，若遇左括号，则将左括号入栈，若遇右括号，则将其与栈顶的左括号进行匹配，若配对，则栈顶的左括号出栈，否则出现括号不匹配错误。,思考：匹配的充要条件？,3.,2,栈的应用举例,迷宫问题,寻找一条从入口到出口的通路。,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,入口,出口,前进方向：,上(北)、下(南)、左(西)、右(东),东,南,北,西,走步规则：,首先从向下开始，按照逆时针方向搜索下一步可能前进的位置,3.,2,栈的应用举例,栈,迷宫问题,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,(1,1),i,(2,1),i,(3,1),i,(4,1),i,(5,1),i,(6,1),(7,1),i,3.,2,栈的应用举例,栈,迷宫问题,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,(1,1),i,(2,1),i,(3,1),i,(4,1),i,(5,1),i,(6,1),(7,1),i,(5,2),i,(5,3),i,(6,3),i,(6,4),i,(8,8),i,i,i,i,i,i,3.,2,栈的应用举例,迷宫问题,迷宫的表示,const,int,N=8;,struct,PosType,int,x,y;,;,char mazeNN;/,位置上的标识，是否可通过,迷宫初始化,用二层嵌套循环对迷宫赋值,迷宫求解(见教材算法),输出栈中的路径,3.,2,栈的应用举例,Status,MazePath(maze,start,end),/,若迷宫中存在一条从入口,start,到出口,end,的通道，则求出这样的一条通路,InitStack(S,);,curpos,=start;,curstep,=1;,do,if(,pass(curpos,)/,当前位置可以通过,Mark(maze,curpos,);/,留下记号,e=(curstep,curpos,1);push(S,e);/,加入路径,if(,curpos,=end)return true;/,到达出口,curpos,=NextPos(curpos,1);/,下一个位置,curstep,+;,else/,当前位置不能通过,if(!,StackEmpty(S,)pop(S,e);/,退回一步,while(e.di,=4&!,StackEmpty(S,)/,当前位置是死胡同,Markdead(maze,e.seat)；pop(S,e,);/,留下记号，沿来路返回,if(,e.di,4)/,当前位置还有其他方向没有探索，继续试探,e.di,+;push(S,e);,curpos,=,NextPos(e.seat,e.di,);,while(!,StackEmpty(S,);,return false;,表达式求值,算符优先法,4+23-10/5,先乘除,后加减,;,从左算到右,先括号内,后括号外,4+23-10/5=4+6-10/5=10-10/5=10-2=8,表达式由,操作数,(operand),、,运算符,(operator),和,界限符,(delimiter),组成的。,将运算符和界限符统称为,算符,。它们构成的集合命名为,OP,3.,2,栈的应用举例,表达式求值,算符优先算法,:,用两个工作栈。一个称作,OPTR,用于存放运算符,;,另一个称作,OPND,用以存放操作数或运算结果。,首先置操作数栈为空栈，表达式起始符“,#”,为运算符的栈底元素；,依次读入表达式中每个字符，若是操作数则进,OPND,栈，若是运算符，则和,OPTR,栈的栈顶运算符比较优先权后作相应操作，直到整个表达式求值完毕,(OPTR,栈的栈顶元素和当前读入的字符均为“,#”),3.,2,栈的应用举例,OperandType,EvaluateExpression,(),InitStack(OPTR,);,Push(OPTR,#);,InitStack(OPND,);c=,getchar,();,while(c,!=#,|,GetTop(OPTR,)!=#),if(!In(c,OP,),Push(OPND,c,);c=,getchar,();,else,/,不是运算符则进栈,switch(Precede(GetTop(OPTR),c,),case:,/,退栈并将运算结果入栈,Pop(OPTR,theta,);,Pop(OPND,b,);,Pop(OPND,a,);,Push(OPND,Operate(a,theta,b,);,break;,/switch,/while,return,GetTop(OPND,);,/,EvaluateExpression,3.,2,栈的应用举例,3.3 栈与递归的实现,栈与递归的实现,用栈结构实现程序设计语言中函数的嵌套调用和递归调用,例：,long,f(int,n),if(n1)return n*f(n-1);,else return 1;,void main(),int,n=4;,printf(“%ld”,f(n,);,栈与递归,3.3 栈与递归的实现,n,阶,Hanoi,塔 问题,假设有三个分别命名为,X,、,Y,和,Z,的塔座，在塔座,X,上插有,n,个直径大小各不相同、依小到大编号为,1,，,2,，,n,的圆盘。现要求将,X,轴上的,n,个圆盘移至塔座,Z,上并仍按同样顺序叠排。,每次只能移动一个圆盘；,圆盘可以插在,X,、,Y,和,Z,中的任一塔座上；,任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。,栈与递归,3.3 栈与递归的实现,n,阶,Hanoi,塔问题,Base case:,n,=1 X,Z,栈与递归,3.3 栈与递归的实现,n,阶,Hanoi,塔问题,Base case:,n,=1 X,Z,栈与递归,3.3 栈与递归的实现,n,阶,Hanoi,塔问题,Recursion:,n,1,前,n,-1,个盘,:X Y,栈与递归,3.3 栈与递归的实现,n,阶,Hanoi,塔问题,Recursion:,n,1,前,n,-1,个盘,:X Y,栈与递归,3.3 栈与递归的实现,n,阶,Hanoi,塔问题,Recursion:,n,1,最大盘,:X Z,栈与递归,3.3 栈与递归的实现,n,阶,Hanoi,塔问题,Recursion:,n,1,最大盘,:X Z,栈与递归,3.3 栈与递归的实现,n,阶,Hanoi,塔问题,Recursion:,n,1,前,n-1,个盘,:Y Z,栈与递归,3.3 栈与递归的实现,n,阶,Hanoi,塔问题,Recursion:,n,1,前,n-1,个盘,:Y Z,栈与递归,3.,4.1,队列的定义及基本运算,队列(,Queue),的定义,队列是仅限定在表尾进行插入和表头进行删除操作的线性表。,术语,队头(,front),队列的表头，即只允许删除的一端。,队尾(,rear),队列的表尾,，,即只允许插入的一端。,入队(,EnQueue,),向队尾插入元素。,出队(,DeQueue,),从队头删除元素。,队列的特点,队列的修改是按先进先出的原则进行的。因此，队列称为先进先出表（,FIFO）。,a,1,a,2,a,i,a,n,队头,front,队尾,rear,出队,入队,3.,4.1,队列的定义及基本运算,队列的基本运算,InitQueue(&Q,):,初始化队列,Q,QueueEmpty,():,判断队列是否为空,EnQueue(e,):,将元素,e,放入队尾,DeQueue(e,):,移走队头元素，由,e,带回该元素的值,GetFront,():,获取队头元素的值，但不从队列中移走该元素,Length():,计算并返回队列中元素的个数,3.,4.2,队列的存储结构和实现,链队列,队列的链式存储结构,队列的链式存储,a,1,a,2,a,n,a,i,Q.front,Q.rear,a,1,a,2,a,i,a,n,队头,front,队尾,rear,出队,入队,3.,4.2,队列的存储结构和实现,链队列的,C,语言实现,/-,单链队列的存储结构-,typedef,struct,QNode,/,链表结点类型,QElemType,data;,struct,QNode,*next;,QNode,*,QueuePtr,;,typedef,struct,/,队列类型,QueuePtr,front;/,队头指针,QueuePtr,rear;/,队尾指针,LinkQueue,;,data,Q.front,Q.rear,Status,InitQueue(LinkQueue,&Q),/,构造一个空队列,Q,Q.front=Q.rear=(,QueuePtr)malloc(sizeof(QNode,);,if(!Q.front)exit(OVERFLOW);,Q.front-next=NULL;,return OK;,(2),入队,Status,EnQueue(LinkQueue,&Q,QElemType,e),/,将元素,e,插入到队列,Q,中,p=(,QueuePtr)malloc(sizeof(QNode,);,if(!p)exit(OVERFLOW);,p-data=e;p-next=NULL;,Q.rear-next=p;Q.rear=p;,return OK;,3.,4.2,队列的存储结构和实现,链队列基本操作的实现,(1)初始化,Q.front,Q.rear,Status,DeQueue(LinkQueue,&Q,QElemType,&e),/,若队列不空，则队头元素出队列，用,e,返回其值，返回,OK,/,否则返回,ERROR,if(,Q.rear,=,Q.front,),return ERROR;,p=,Q.front,-next;,e=p-data;,Q.front,-next=p-next;,if(,Q.rear,=p),Q.rear,=,Q.front,;,free(p,);,return OK;,3.,4.2,队列的存储结构和实现,链队列基本操作的实现,(1)初始化,(2),入队列,(3),出队列,Q.front,Q.rear,思考：,如果不设置头结点，需要考虑那些特殊情况？,3.,4.2,队列的存储结构和实现,循环队列队列的顺序存储结构,a,1,a,2,a,i,a,n,队头,front,队尾,rear,出队,入队,6,F36,a,n,6,F26,a,i,.,.,6,F02,a,2,6,F00,a,1,Q.front,Q.rear,a,1,a,2,a,3,Q.front,a,n,Q.rear,0,1,2,n,n+1,m-1,循环队列,循环队列的,C,语言实现,/-,-,循环队列的存储结构-,-,#,define MAXSIZE 100,typedef,struct,QElemType,*base;,int,front;,int,rear;,SqQueue,;,3.,4.2,队列的存储结构和实现,循环队列基本操作的实现,(1)初始化,Status,InitQueue(SqQueue,&Q),Q.base,=(,QElemType,*),malloc(,MAXSIZE,*,sizeof(,QElemType,),);,if(!,Q.base,)exit(OVERFLOW);,Q.front,=,Q.rear,=0;,return OK;,(base+,Maxsize-1),base,3.,4.2,队列的存储结构和实现,3.,4.2,队列的存储结构和实现,循环队列基本操作的实现,(2)入队,Status,EnQueue(SqQueue,&,Q,QElemType,e),/,将元素,e,插入队列,Q,的队尾,if(Q.rear+1)%MAXSIZE,=,Q.front)return ERROR;,Q.baseQ.rear=e;,Q.rear=(Q.rear+1)%MAXSIZE;,return OK;,循环队列基本操作的实现,(3)出队,Status,DeQueue(SqQueue,&,Q,QElemType,&e),/,删除队列,Q,的队头元素并用,e,带回,if(,Q.front,=,Q.rear,)return ERROR;,e=,Q.baseQ.front,;,Q.front,=(Q.front+1)%MAXSIZE;,return OK;,3.,4.2,队列的存储结构和实现,双端队列,双端队列,队头,队尾,出队,入队,出队,入队,输出受限的双端队列,队头,队尾,出队,入队,入队,双端队列,输入受限的双端队列,队头,队尾,出队,入队,出队,优先队列,在许多情况下，简单的队列结构是不够的，需要使用某些优先规则来完善先入先出机制，例如,优先队列的问题是如何找到一种实现优先的方法，使得入队和出队列操作得以相对容易实现。,优先队列可以通过两种修正的链表结构来实现。,一种结构是元素仍然依次进入（即加入元素时，时间复杂度为,O(1),），而取出元素时则需遍历队列（即出队时的时间复杂度为,O(n,),），,另一种是根据元素的优先级决定其插入的位置（即入队时的时间复杂度为,O(n,),，出队时的时间复杂度为,O(1),）。,3.,4.3,队列的应用,同栈一样，队列也是一种应用广泛的线性表，在日常生活和计算机科学中很常见：,离散事件模拟,排队问题,作业控制,广度优先搜索,.,本章小结,本章应掌握的内容,栈的定义、运算,顺序栈、链栈,队列的定义、运算及实现,循环链队列、循环顺序队列,