《栈和队列》PPT课件.ppt

1第三章第三章 栈和队列栈和队列3.1 栈栈3.2 栈的应用举例栈的应用举例3.4 队列队列2 通常称，栈和队列是限定通常称，栈和队列是限定插入和删除插入和删除只能只能在表的在表的“端点端点”进行的线性表。进行的线性表。线性表线性表 栈栈 队列队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1 Delete(L,i)Delete(S,n)Delete(Q,1)1in栈和队列是两种常用的数据类型栈和队列是两种常用的数据类型3学习提要：学习提要：1.1.掌握栈和队列这两种抽象数据类型的特点，掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。并能在相应的应用问题中正确选用它们。2.2.熟练掌握栈类型的两种实现方法，即两种存熟练掌握栈类型的两种实现方法，即两种存 储结构表示时的基本操作实现算法，特别应储结构表示时的基本操作实现算法，特别应 注意栈满和栈空的条件以及它们的描述方法。注意栈满和栈空的条件以及它们的描述方法。3.3.熟练掌握循环队列和链队列的基本操作实现熟练掌握循环队列和链队列的基本操作实现 算法，特别注意队满和队空的描述方法。算法，特别注意队满和队空的描述方法。重难点内容：重难点内容：顺序栈的相关操作、循环队列的判空判满顺序栈的相关操作、循环队列的判空判满43.1 栈（栈（stack）栈的类型定义栈的类型定义 栈的表示和实现栈的表示和实现5栈的定义和特点栈的定义和特点v定义：限定仅在定义：限定仅在表尾表尾进行插入或删除操进行插入或删除操作的线性表，表尾作的线性表，表尾栈顶栈顶，表头，表头栈底栈底，不含元素的空表称不含元素的空表称空栈。空栈。ana1a2.栈底栈底栈栈顶顶.出栈出栈进栈进栈栈栈s=(a1,a2,an)v特点：先进后出（特点：先进后出（FILO）或后进先出）或后进先出（LIFO）栈的类型定义6 ADT Stack 数据对象数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,aiD,i=2,.,n 约定an 端为栈顶，a1 端为栈底。基本操作：基本操作：ADT Stack 栈的类型定义栈的类型定义7InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit()8顺序栈顺序栈3.1.2 栈的表示和实现栈的表示和实现 类似于线性表的顺序映象实现，类似于线性表的顺序映象实现，指向表尾的指针可以作为指向表尾的指针可以作为栈顶指针栈顶指针。/-栈的顺序存储表示栈的顺序存储表示-#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;typedef struct SElemType *base;SElemType *top;int stacksize;SqStack;9实现：一维数组实现：一维数组sMtop123450进栈进栈A栈满栈满BCDEF设数组维数为设数组维数为M Mtop=base,top=base,栈空，此时出栈，则栈空，此时出栈，则下下溢溢（underflow)underflow)top=M,top=M,栈满，此时入栈，则栈满，此时入栈，则上溢上溢（overflow)overflow)toptoptoptoptop123450空栈空栈topbasebasetop出栈出栈toptop栈空栈空base栈底指针栈底指针base,base,始终始终指向栈底位置；指向栈底位置；栈顶栈顶指针指针top,top,其初值指向其初值指向栈底，始终在栈顶元栈底，始终在栈顶元素的下一个位置素的下一个位置123450ABtop10 Status InitStack(SqStack&S)/构造一个空栈SS.base=(SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType);if(!S.base)exit(OVERFLOW);/存储分配失败 ;S.stacksize=STACK_INIT_SIZE;return OK;11 Status Push(SqStack&S,SElemType e)if(-=)/栈满，追加存储空间 =(SElemType*)realloc(,(+STACKINCREMENT)*sizeof(SElemType);if(!)exit(OVERFLOW);/存储分配失败 =+;+=STACKINCREMENT;*+=e;return OK;12Status Pop(SqStack&S,SElemType&e)/若栈不空，则删除S的栈顶元素，/用e返回其值，并返回OK；/否则返回ERROR if =S.base)return ERROR;e=*-S.top;return OK;130M-1栈栈1底底栈栈1顶顶栈栈2底底栈栈2顶顶在一个程序中同时使用两个栈在一个程序中同时使用两个栈14链栈链栈 栈的链式存储结构。栈顶指针就是栈的链式存储结构。栈顶指针就是链表的头指针。链表的头指针。栈顶指针a1an注意注意:链栈中链栈中指针的方向指针的方向an-1注意注意:链栈链栈中指针的方向中指针的方向注意：注意：链栈中的指针方向链栈中的指针方向15v 入栈操作入栈操作v 出栈操作出栈操作 .栈底栈底toptopxptop .栈底栈底topqp-next=top;top=p q=top;top=top-next 163.2 栈的应用栈的应用3.2.1 数制转换数制转换3.2.2 括号匹配的检验括号匹配的检验3.2.3 行编辑程序问题行编辑程序问题3.2.4 迷宫求解迷宫求解3.2.5 表达式求值表达式求值173.2.1 数制转换数制转换十进制十进制N和其他和其他d进制数的转换原进制数的转换原理理:N=(N div d)*d+N mod d 其中：其中：div为为整除整除运算，运算，mod为为求余求余运算运算18toptop4top40top405 例如：例如：(1348)10=(2504)8，其运算过程如下：，其运算过程如下：N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2计算顺序输出顺序top405219 void conversion()initstack(S);scanf(“%d”,N);while(N)push(S，N%8);N=N/8;while(!Stackempty(s)pop(S,e);printf(“%d”,e);/conversion203.3.2 括号匹配的检验括号匹配的检验 则则 检验括号是否匹配检验括号是否匹配的方法可用的方法可用“期待的急迫程度期待的急迫程度”这个概念来描述。这个概念来描述。假设在表达式中假设在表达式中（）或（）或（）等为正确的格式，等为正确的格式，（）或（）或（）或）或（）（）)均均为不正确的格式。为不正确的格式。21分析可能出现的分析可能出现的不匹配不匹配的情况的情况:到来的右括弧到来的右括弧并非是所并非是所“期待期待”的；的；例如：例如：考虑下列括号序列：考虑下列括号序列：()1 2 3 4 5 6 7 8直到结束，也没有到来直到结束，也没有到来所所“期待期待”的括弧。的括弧。22算法的设计思想：算法的设计思想：1）凡出现）凡出现左括弧左括弧，则，则进栈进栈；2）凡出现）凡出现右括弧右括弧，首先检查栈是否空，首先检查栈是否空 若若栈空栈空，则表明该，则表明该“右括弧右括弧”多余多余，否则否则和栈顶元素和栈顶元素比较，比较，若若相匹配相匹配，则，则“左括弧出栈左括弧出栈”，否则表明否则表明不匹配不匹配。3）表达式检验结束时，）表达式检验结束时，若若栈空栈空，则表明表达式中，则表明表达式中匹配正确匹配正确，否则表明否则表明“左括弧左括弧”有余有余。233.2.3 行编辑程序问题行编辑程序问题如何实现？如何实现？“每接受一个字符即存入存储器每接受一个字符即存入存储器”?不恰当不恰当!合理的作法是：合理的作法是：设立一个输入缓冲区，用以接受用设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户输入的一行字符，然后逐行存入用户数据区，并假设户数据区，并假设“#”为退格符，为退格符，“”为退行符。为退行符。24假设从终端接受了这样两行字符：假设从终端接受了这样两行字符：whli#ilr#e（s#*s)outchaputchar(*s=#+);则实际有效的是下列两行：则实际有效的是下列两行：while(*s)putchar(*s+);25 while(ch!=EOF&ch!=n)switch(ch)case#:Pop(S,c);break;case:ClearStack(S);break;/重置S为空栈 default:Push(S,ch);break;ch=getchar();/从终端接收下一个字符 ClearStack(S);/重置S为空栈if(ch!=EOF)ch=getchar();while(ch!=EOF)/EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；263.2.4 迷宫求解迷宫求解通常用的是通常用的是“穷举求解穷举求解”的方法的方法27求迷宫路径算法的求迷宫路径算法的基本思想基本思想是：是：v若当前位置若当前位置“可通可通”，则纳入路，则纳入路径，径，继续前进继续前进;v若当前位置若当前位置“不可通不可通”，则，则后退，换方向继续探索后退，换方向继续探索;v若四周若四周“均无通路均无通路”，则将，则将当前位置从路径中删除出去。当前位置从路径中删除出去。28 限于二元运算符的表达式定义:Exp=S1 OP S2 操作数操作数:变量、常量、表达式变量、常量、表达式 运算符运算符:算术运算符、关系运算符、算术运算符、关系运算符、逻辑运算符逻辑运算符 界限符：界限符：括号、结束符括号、结束符3.2.5 表达式求值表达式求值29例：例：3*(7 2)OPND栈栈OPTR栈栈CCC3*(C7CC2C275C*531530例：例：3*(7 2)OPTR栈栈 OPND栈栈 输入输入 操作操作1#3*(7 2)#PUSH(OPND,3)2#3 *(7 2)#PUSH(OPTR,*)3#*3 (7 2)#PUSH(OPTR,()4#*(3 7 2)#PUSH(OPND,7)5#*(3 7 2)#PUSH(OPTR,)6#*(3 7 2)#PHSH(OPND,2)7#*(3 7 2 )#operate(7,-,2)8#*(3 5 )#POP(OPTR)9#*3 5#operate(3,*,5)10#15#return GetTop(OPND)31OperandType EvaluateExpression()/设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。InitStack(OPTR);Push(OPTR,#);initStack(OPND);c=getchar();while(c!=#|GetTop(OPTR)!=#)if(!In(c,OP)Push(OPND,c);c=getchar();/不是运算符则进栈 else /while return GetTop(OPND);/EvaluateExpression 32switch(precede(GetTop(OPTR),c)case :/退栈并将运算结果入栈 Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);break;/switch333.4 队列队列 队列的类型定义队列的类型定义 链队列链队列 循环队列循环队列34队列队列是限定只能在表的一端进行插入，在是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。表的另一端进行删除的线性表。a1 a2 a3.an 入队入队出队出队frontrear队列队列Q=(a1,a2,an)v队列特点：先进先出队列特点：先进先出(FIFOFIFO)队列的类型定义队列的类型定义v队尾队尾(rear)允许允许插入插入的一端的一端v队头队头(front)允许允许删除删除的一端的一端35 ADT Queue 数据对象：数据对象：Dai|aiElemSet,i=1,2,.,n,n0 数据关系：数据关系：R1|ai-1,ai D,i=2,.,n 约定其中约定其中a1 端为端为队列头队列头，an 端为端为队列尾队列尾基本操作：基本操作：队列的类型定义 ADT Queue36队列的基本操作：队列的基本操作：InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q,visit()37typedef struct QNode/结点类型结点类型 QElemType data;struct QNode *next;QNode,*QueuePtr;typedef struct/链队列类型链队列类型 QueuePtr front;/队头指针 QueuePtr rear;/队尾指针 LinkQueue;3.4.2 链队列队列的链式表示和实现链队列队列的链式表示和实现38a1an空队列空队列39frontrearx入队入队xfrontreary入队入队xyfrontrearx出队出队xyfrontrear空空队队front reary出队出队Q.rear-next=pQ.rear=pp=Q.front-nextQ.front-next=p-next 40 Status InitQueue(LinkQueue&Q)/构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);/存储分配失败 Q.front-next=NULL;return OK;41 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;42 Status DeQueue(LinkQueue&Q,QElemType&e)/若队列不空，则删除Q的队头元素，/用 e 返回其值，并返回OK；否则返回ERROR if(Q.front=Q.rear)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;43 循环队列队列的顺序表示和实现循环队列队列的顺序表示和实现#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base;/动态分配存储空间 int front;/头指针，若队列不空，/指向队列头元素 int rear;/尾指针，若队列不空，指向 /队列尾元素 的下一个位置 SqQueue;44实现：用一维数组实现实现：用一维数组实现sqM123450空队列空队列rear=0 front=0J1J2J3rearrear123450J4,J5,J6入队J4J5J6frontrearrear123450frontJ1,J1,J3入队rear123450J1,J2,J3出队J1J2J3frontfrontfrontfrontv存在问题：存在问题：l当当front=0,rear=M时再有元素入队发生溢出时再有元素入队发生溢出真溢出真溢出l当当front0,rear=M时再有元素入队发生溢出时再有元素入队发生溢出假溢出假溢出rear45v解决方案解决方案l队首固定，每次出队剩余元素向下移动队首固定，每次出队剩余元素向下移动浪浪费时间费时间l循环队列循环队列u 基本思想：把队列基本思想：把队列设想成环形设想成环形，让，让sq0接接在在sqM-1 之后，若之后，若rear+1=M,则令则令rear=0;u实现：利用实现：利用“模模”运算运算u入队：入队：baserear=x;rear=(rear+1)%M;u出队：出队：x=basefront;front=(front+1)%M;u队满、队空判定条件队满、队空判定条件46012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4,J5,J6出队出队J7,J8,J9入队入队队空：队空：front=rearfront=rear队满：队满：front=rearfront=rear解决方案：解决方案：1.另外另外设一个标志位设一个标志位以区别队空、队满以区别队空、队满2.少用一个元素空间少用一个元素空间：队空：队空：front=rear 队满：队满：(rear+1)%M=front3.使用一个计数器记录队列中元素的总数使用一个计数器记录队列中元素的总数J5J6012345rearfront初始状态J447 Status InitQueue(SqQueue&Q)/构造一个空队列Q Q.base=(QElemType*)malloc (MAXQSIZE*sizeof(QElemType);if(!Q.base)exit(OVERFLOW);/存储分配失败 Q.front=Q.rear=0;return OK;48Status EnQueue(SqQueue&Q,QElemType e)/插入元素e为Q的新的队尾元素 if(Q.rear+1)%MAXQSIZE=)return ERROR;/队列满 Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;49 Status DeQueue(SqQueue&Q,QElemType&e)/若队列不空，则删除Q的队头元素，/用e返回其值，并返回OK;否则返回ERROR if(Q.front=)return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;50第三章作业3.1 设将整数设将整数1、2、3、4依次进栈，但只要出栈时依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题：回答下有问题：（1）若入栈次序为）若入栈次序为push(1)，pop()，push(2），），push(3)，pop()，pop()，push(4)，pop()，则出栈，则出栈的数字序列为什么？的数字序列为什么？（2）请分析）请分析1、2、3、4的的24种排列中，哪些序种排列中，哪些序列可以通过相应的入出栈得到。列可以通过相应的入出栈得到。补充作业：补充作业：写出检验括号匹配的算法。写出检验括号匹配的算法。513.12 写出以下程序段的输出结果（队列中的元素写出以下程序段的输出结果（队列中的元素 类型类型QElemType 为为char）。）。Void main()Queue Q;InitQueue(Q);Char x=e,y=c;EnQueue(Q,h);EnQueue(Q,r);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,a);While(!QueueEmpty(Q)DeQueue(Q,y);Printf(y);Printf(x);参考答案EnQueue(Q,h);EnQueue(Q,r);EnQueue(Q,y);/hrc入队此时队列是入队此时队列是 hrc(h是头是头)DeQueue(Q,x);EnQueue(Q,x);/h赋给赋给x出队，然后出队，然后x再入队此时再入队此时x=h即即h入队入队,此时队列是此时队列是rch。DeQueue(Q,x);EnQueue(Q,a);/r赋给赋给x出队，出队，a入队，此时队列是入队，此时队列是chawhile(!QueueEmpty(Q)DeQueue(Q,y);printf(y);/当队列不为空时依次把队列中元素赋给当队列不为空时依次把队列中元素赋给y 列，并打印。此时打印出的是列，并打印。此时打印出的是chaPrintf(x);/打印打印x的值就是前面赋给的值就是前面赋给x的的r 所以打印出的是所以打印出的是 char 52