资源描述
1 3.1 栈栈 3.2 栈的应用举例栈的应用举例 3.3 队列队列 2 第第3 3章章 栈和队列栈和队列 重点重点:(1)栈、队列的定义、特点、性质和应用；栈、队列的定义、特点、性质和应用；(2)ADT栈、栈、ADT队列的设计和实现以及基本操作及队列的设计和实现以及基本操作及相关算法。相关算法。难点难点:(1)循环队列中对边界条件的处理；循环队列中对边界条件的处理；(2)分析分析栈和队列在表达式求值、括号匹配、数制转换、迷栈和队列在表达式求值、括号匹配、数制转换、迷宫求解中的应用实例，提高利用栈和队列解决实际宫求解中的应用实例，提高利用栈和队列解决实际问题的应用水平。问题的应用水平。本章重点难点 3 第第3 3章章 栈和队列栈和队列 3.1 栈栈 3.2 栈的应用举例栈的应用举例 3.3 队列队列 4 第第3 3章章 栈和队列栈和队列 3.1 栈栈 3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义 3.1.2 栈的表示和实现栈的表示和实现 5 第第3 3章章 栈和队列栈和队列3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义p栈的定义栈的定义栈栈(Stack)是一种特殊的线性表，其插入和删除操是一种特殊的线性表，其插入和删除操作均在表的一端进行，是一种运算受限的线性表。作均在表的一端进行，是一种运算受限的线性表。栈顶栈顶(top)是栈中允许插入和删除的一端。是栈中允许插入和删除的一端。栈底栈底(bottom)是栈顶的另一端。是栈顶的另一端。p栈的术语栈的术语 6 第第3 3章章 栈和队列栈和队列p栈的特点栈的特点p栈的示意图栈的示意图后进先出后进先出(Last In First Out，简称，简称LIFO)。又称栈为后进先出表又称栈为后进先出表(简称简称LIFO结构结构)。ana2a1栈底栈底栈顶栈顶入栈入栈出栈出栈3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义 7 第第3 3章章 栈和队列栈和队列 ADT Stack 数据对象：数据对象：数据关系：数据关系：p抽象数据类型栈抽象数据类型栈基本操作：基本操作：ADT StackR1|ai-1,aiD,i=2,.,n 约定约定an 端为栈顶，端为栈顶，a1 端为栈底。端为栈底。D ai|ai ElemSet,i=1,2,.,n,n0 见下页见下页3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义 8 第第3 3章章 栈和队列栈和队列InitStack(&S)/初始化栈初始化栈DestroyStack(&S)/销毁栈销毁栈ClearStack(&S)/清空栈清空栈StackEmpty(S)/判栈空判栈空StackLength(S)/求栈长度求栈长度GetTop(S,&e)/取栈顶元素取栈顶元素Push(&S,e)/入栈入栈Pop(&S,&e)/出栈出栈StackTravers(S,visit()/遍历栈遍历栈p栈的基本操作栈的基本操作3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义 9 第第3 3章章 栈和队列栈和队列 3.1 栈栈 3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义 3.1.2 栈的表示和实现栈的表示和实现 10 第第3 3章章 栈和队列栈和队列3.1.2 栈的表示和实现栈的表示和实现 /-栈的顺序存储表示栈的顺序存储表示-#define STACK_INIT_SIZE 100;/存储空间初始分配量存储空间初始分配量#define STACKINCREMENT 10;/存储空间分配增量存储空间分配增量 typedef struct SElemType *base;/栈底指针栈底指针 SElemType *top;/栈顶指针栈顶指针 int stacksize;/当前可使用最大容量当前可使用最大容量 SqStack;SqStack S;p顺序栈的顺序栈的C语言实现语言实现 11 第第3 3章章 栈和队列栈和队列3.1.2 栈的表示和实现栈的表示和实现p栈初始化过程演示栈初始化过程演示(1)给栈给栈S申请栈空间申请栈空间(2)设置基地址设置基地址S.base和栈顶地址和栈顶地址S.topS.topS.base(3)设置栈容量设置栈容量S.stacksize=STACK_INIT_SIZE 12 第第3 3章章 栈和队列栈和队列 Status InitStack(SqStack&S)/构造一个空栈构造一个空栈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;3.1.2 栈的表示和实现栈的表示和实现p栈初始化算法栈初始化算法 13 第第3 3章章 栈和队列栈和队列3.1.2 栈的表示和实现栈的表示和实现p入栈操作演示入栈操作演示(1)如果栈满，给栈增加容量如果栈满，给栈增加容量abcdef(2)将数据存入栈顶位置，栈顶后移一位将数据存入栈顶位置，栈顶后移一位S.topS.baseeS.top 14 第第3 3章章 栈和队列栈和队列 Status Push(SqStack&S,SElemType e)if(S.top-S.base=S.stacksize)S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType);if(!S.base)exit(OVERFLOW);/存储分配失败存储分配失败 S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;3.1.2 栈的表示和实现栈的表示和实现p入栈操作演示入栈操作演示 15 第第3 3章章 栈和队列栈和队列3.1.2 栈的表示和实现栈的表示和实现DestroyStack(&S)/销毁栈销毁栈ClearStack(&S)/清空栈清空栈StackEmpty(S)/判栈空判栈空StackLength(S)/求栈长度求栈长度GetTop(S,&e)/取栈顶元素取栈顶元素Pop(&S,&e)/出栈出栈StackTravers(S,visit()/遍历栈遍历栈p其它栈操作讨论其它栈操作讨论 16 第第3 3章章 栈和队列栈和队列 Typedef struct SNode ElemType data;/数据域数据域 struct Snode*next;/链域链域 SNode,*LinkStack;3.1.2 栈的表示和实现栈的表示和实现p链栈的链栈的C语言类型定义语言类型定义 链栈的实现与链表的实现基本相同，头结链栈的实现与链表的实现基本相同，头结点作为栈顶位置。点作为栈顶位置。LinkStack*top;/栈顶指针栈顶指针 17 第第3 3章章 栈和队列栈和队列InitStack(&S)/初始化栈初始化栈DestroyStack(&S)/销毁栈销毁栈ClearStack(&S)/清空栈清空栈StackEmpty(S)/判栈空判栈空StackLength(S)/求栈长度求栈长度GetTop(S,&e)/取栈顶元素取栈顶元素Push(&S,e)/入栈入栈Pop(&S,&e)/出栈出栈StackTravers(S,visit()/遍历栈遍历栈p讨论链栈基本操作的实现讨论链栈基本操作的实现3.1.2 栈的表示和实现栈的表示和实现 18 第第3 3章章 栈和队列栈和队列3.2 栈的应用举例栈的应用举例3.2.1 数制转换数制转换3.2.2 括号匹配的检验括号匹配的检验3.2.3 行编辑程序问题行编辑程序问题3.2.4 迷宫求解迷宫求解3.2.5 表达式求值表达式求值 19 第第3 3章章 栈和队列栈和队列3.2.1 数制转换数制转换 任何任何X进制数进制数N转换成转换成Y进制数其结果都是要化进制数其结果都是要化成如下形式。成如下形式。p进制转换原理：进制转换原理：转换的过程就是通过取余运算求出转换的过程就是通过取余运算求出a0,a1,an，而先求出的是个位，十位而先求出的是个位，十位，与我们写数的习惯先，与我们写数的习惯先从高位写正好相反，通过栈先进后出的特点，很容从高位写正好相反，通过栈先进后出的特点，很容易实现倒过来的过程。易实现倒过来的过程。20 第第3 3章章 栈和队列栈和队列过程如下：过程如下：N N div 8 N mod 81348 168 4168 21 021 2 52 0 2输输出出顺顺序序计计算算顺顺序序3.2.1 数制转换数制转换例例将将10进制进制1346转换成转换成8进制进制 21 第第3 3章章 栈和队列栈和队列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);/conversion3.2.1 数制转换数制转换p10进制数进制数N转换成转换成8进制的算法进制的算法 22 第第3 3章章 栈和队列栈和队列 一个表达式中，包含三种括号一个表达式中，包含三种括号“(”和和“)”，“”和和“”和和“”和和“”，这三种括号可以按任意的，这三种括号可以按任意的合法次序使用。合法次序使用。设计算法检验表达式中所使用括号的合法性。设计算法检验表达式中所使用括号的合法性。3.2.2 括号匹配的检验括号匹配的检验p问题描述问题描述 讨论：讨论：如果第一次遇到的右括号是如果第一次遇到的右括号是“”，那么前，那么前面出现的左括号有什么特点。面出现的左括号有什么特点。p问题讨论问题讨论 结论：结论：如果第一次遇到的右括号是如果第一次遇到的右括号是“”，那么前，那么前面出现的左括号最后一个必然是面出现的左括号最后一个必然是“”，否则不合法。，否则不合法。23 第第3 3章章 栈和队列栈和队列p算法过程算法过程3.2.2 括号匹配的检验括号匹配的检验(1)当遇到左括号时，进栈，遇到右括号时出栈；当遇到左括号时，进栈，遇到右括号时出栈；(2)当遇到某一个右括号时，栈已空，说明到目前当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；为止，右括号多于左括号；(3)从栈中弹出的左括号与当前检验的右括号类型从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；不同，说明出现了括号交叉情况；(4)算术表达式输入完毕，但栈中还有没有匹配的算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。左括号，说明左括号多于右括号。24 第第3 3章章 栈和队列栈和队列Status check()char ch;InitStack(S);while(ch=getchar()!=#)switch(ch)case(ch=(|ch=|ch=):Push(S,ch);break;case(ch=):if(StackEmpty(S)retrun FALSE;else Pop(S,e);if(e!=()return FALSE;break;p括号匹配检验算法括号匹配检验算法3.2.2 括号匹配的检验括号匹配的检验 25 第第3 3章章 栈和队列栈和队列 case(ch=):if(StackEmpty(S)retrun FALSE;else Pop(S,e);if(e!=)return FALSE;break;default:break;if(StackEmpty(S)return TRUE;else return FALSE;p括号匹配检验算法括号匹配检验算法3.2.2 括号匹配的检验括号匹配的检验 26 第第3 3章章 栈和队列栈和队列3.2.3 行编辑程序问题行编辑程序问题 设立一个输入缓冲区，用以接受用户输入的设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设一行字符，然后逐行存入用户数据区，并假设“#”为退格符，为退格符，“”为退行符。为退行符。在用户输入一行的过程中，允许用户输入出差在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。错，并在发现有误时可以及时更正。p解决办法解决办法p问题描述问题描述 27 第第3 3章章 栈和队列栈和队列假设从终端接受了这样两行字符：假设从终端接受了这样两行字符：whli#ilr#e（s#*s)outchaputchar(*s=#+);则实际有效的是下列两行：则实际有效的是下列两行：while(*s)putchar(*s+);例例3.2.3 行编辑程序问题行编辑程序问题 28 第第3 3章章 栈和队列栈和队列 DestroyStack(S);void LineEdit()/利用字符栈利用字符栈S，从终端接收一行并传送至调，从终端接收一行并传送至调 /用过程的数据区用过程的数据区 InitStack(S);ch=getchar();.3.2.3 行编辑程序问题行编辑程序问题p行编辑问题算法行编辑问题算法while(ch!=EOF)/EOF为全文结束符为全文结束符 while(ch!=EOF&ch!=n)29 第第3 3章章 栈和队列栈和队列 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();栈中字符传送至调用过程的数据区；栈中字符传送至调用过程的数据区；3.2.3 行编辑程序问题行编辑程序问题p行编辑问题算法行编辑问题算法 30 第第3 3章章 栈和队列栈和队列入口入口出口出口3.2.4 迷宫求解迷宫求解如图表示一个迷宫，有一个入口，一个出口，从一个如图表示一个迷宫，有一个入口，一个出口，从一个位置可以向位置可以向4个方向个方向(东、南、西、北东、南、西、北)走，白方块表示走，白方块表示通道，蓝方块表示墙，求从入口到出口的路径。通道，蓝方块表示墙，求从入口到出口的路径。p问题描述问题描述1234567812345678 31 第第3 3章章 栈和队列栈和队列3.2.4 迷宫求解迷宫求解p求解方法求解方法“穷举求解穷举求解”方法：方法：从入口出发，顺某一方向向前探从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到一个方向再继续探索，直至所有可能的通路都探索到为止。为止。为了保证在任何位置上都能沿原路退回，需要一个后为了保证在任何位置上都能沿原路退回，需要一个后进先出的结构来保存从入口到当前位置的路径。因此，进先出的结构来保存从入口到当前位置的路径。因此，求解迷宫通路算法需要应用求解迷宫通路算法需要应用“栈栈”来保存当前路径。来保存当前路径。32 第第3 3章章 栈和队列栈和队列3.2.4 迷宫求解迷宫求解p 四周墙壁解决办法如图四周墙壁解决办法如图012345678901234567891234567812345678 33 第第3 3章章 栈和队列栈和队列p当前位置：当前位置：在搜索过程中某一时刻所在图中某个方在搜索过程中某一时刻所在图中某个方块位置。块位置。p当前位置可通：当前位置可通：未承走到过的通道块，该方块既不未承走到过的通道块，该方块既不在在当前路径上当前路径上，也不是曾经，也不是曾经纳入过路径的通道块纳入过路径的通道块。3.2.4 迷宫求解迷宫求解01234567890123456789p下一位置：下一位置：当前位当前位置四周置四周4个方向个方向(东、东、南、西、北南、西、北)上相邻上相邻的方块。的方块。当前位当前位置置(3,3)(3,2)(2,2)(1,2)(1,1)当前路径当前路径 34 第第3 3章章 栈和队列栈和队列3.2.4 迷宫求解迷宫求解p 算法思想算法思想(1)若当前位置若当前位置“可通可通”，则纳入，则纳入“当前路径当前路径”，并继，并继续朝续朝“下一位置下一位置”探索，即切换探索，即切换“下一位置下一位置”为为“当当前位置前位置”，如此重复直至到达出口；，如此重复直至到达出口；(2)若当前位置若当前位置“不可通不可通”，则应顺着，则应顺着“来向来向”退回到退回到“前一通道块前一通道块”，然后朝着除了，然后朝着除了“来向来向”之外的其他之外的其他方向继续探索；方向继续探索；(3)若该通道块的四周若该通道块的四周4个方块均个方块均“不可通不可通”，则应从，则应从“当前路径当前路径”上删除该通道块。上删除该通道块。35 第第3 3章章 栈和队列栈和队列设定当前位置的初值为入口位置；设定当前位置的初值为入口位置；do 若当前位置可通，若当前位置可通，则将当前位置插入栈顶；则将当前位置插入栈顶；若该位置是出口位置，则算法结束；若该位置是出口位置，则算法结束；否则切换当前位置的东邻方块为否则切换当前位置的东邻方块为 新的当前位置；新的当前位置；否则否则.while(栈不空）；栈不空）；p迷宫路径求解算法迷宫路径求解算法3.2.4 迷宫求解迷宫求解 36 第第3 3章章 栈和队列栈和队列 若栈不空且栈顶位置尚有其他方向未被探索，若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为则设定新的当前位置为:沿顺时针方向旋转找沿顺时针方向旋转找到的栈顶位置的下一相邻块；到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则若栈不空但栈顶位置的四周均不可通，则 删去栈顶位置；删去栈顶位置；若栈不空，则重新测试新的栈顶位置，若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；直至找到一个可通的相邻块或出栈至栈空；若栈空，则表明迷宫没有通路。若栈空，则表明迷宫没有通路。p迷宫路径求解算法迷宫路径求解算法3.2.4 迷宫求解迷宫求解 37 第第3 3章章 栈和队列栈和队列012345678901234567893.2.4 迷宫求解迷宫求解p求解过程示例求解过程示例 38 第第3 3章章 栈和队列栈和队列3.2.5 表达式求值表达式求值 一个表达式由操作数一个表达式由操作数(operand)、运算符、运算符(operator)、界限符、界限符(delimiter)组成。写出组成。写出“算符优算符优先法先法”求值的算法。求值的算法。p问题描述问题描述例例求求3*(2+3*5)+6的值的值 39 第第3 3章章 栈和队列栈和队列 设置两个栈，一个存操作数，栈名为设置两个栈，一个存操作数，栈名为OPND，一个存操作符，栈名为一个存操作符，栈名为OPTR栈。栈。(1)首先置操作数栈为空，表达式起始符首先置操作数栈为空，表达式起始符#为运为运算符栈的栈底元素；算符栈的栈底元素；(2)依次读入表达式中每个字符，若是操作数则依次读入表达式中每个字符，若是操作数则进进OPND栈，若是运算符则和栈，若是运算符则和OPTR栈的栈顶运算栈的栈顶运算符比较优先权后作相应操作，直到整个表达式操作符比较优先权后作相应操作，直到整个表达式操作完毕。完毕。3.2.5 表达式求值表达式求值p算法求解过程算法求解过程 40 第第3 3章章 栈和队列栈和队列 (1)若栈顶运算符小于输入运算符，输入运算符若栈顶运算符小于输入运算符，输入运算符进栈进栈OPTR；(2)若栈顶运算符等于输入运算符（只有栈顶是若栈顶运算符等于输入运算符（只有栈顶是“（”，输入是，输入是“）”，或者栈顶是，或者栈顶是“#”，输入是，输入是“#）”两种情况，分别去除一对括号，或结束。两种情况，分别去除一对括号，或结束。(3)若栈顶运算符大于输入运算符，弹出栈顶运若栈顶运算符大于输入运算符，弹出栈顶运算符，从算符，从OPND中弹出两个操作数与弹出运算符计算中弹出两个操作数与弹出运算符计算后再存入后再存入OPND栈，继续。栈，继续。3.2.5 表达式求值表达式求值p算法求解过程算法求解过程 41 第第3 3章章 栈和队列栈和队列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)3.2.5 表达式求值表达式求值p表达式求值算法表达式求值算法 42 第第3 3章章 栈和队列栈和队列case:Pop(OPTR,theta);Pop(OPND,a);Pop(OPND,b);Push(OPND,Operate(a,theta,b);break;/switch语句结束语句结束 /while 语句结束语句结束 return(GetTop(OPND);/算法结束算法结束p表达式求值算法表达式求值算法 43 第第3 3章章 栈和队列栈和队列 3.1 栈栈 3.2 栈的应用举例栈的应用举例 3.3 队列队列 44 第第3 3章章 栈和队列栈和队列p队列的定义队列的定义3.4.1 抽象数据类型队列的定义抽象数据类型队列的定义 队列队列(Queue)是一种运算受限的特殊的线性表，是一种运算受限的特殊的线性表，它只允许在表的一端进行插入，而在表的另一端进它只允许在表的一端进行插入，而在表的另一端进行删除。行删除。队尾队尾(rear)是队列中允许插入的一端。是队列中允许插入的一端。队头队头(front)是队列中允许删除的一端。是队列中允许删除的一端。p队列的术语队列的术语 45 第第3 3章章 栈和队列栈和队列p队列的特点队列的特点p队列示意图队列示意图3.4.1 抽象数据类型队列的定义抽象数据类型队列的定义a1a2a3 an队头队头队尾队尾出队出队出队出队 先进先出先进先出(First In First Out，简称，简称FIFO)。又称队列为先进先出表。又称队列为先进先出表。46 第第3 3章章 栈和队列栈和队列 ADT Queue 数据对象：数据对象：数据关系：数据关系：p抽象数据类型栈抽象数据类型栈基本操作：基本操作：ADT Queue见下页见下页3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义Dai|aiElemSet,i=1,2,.,n,n0R1|ai-1,ai D,i=2,.,n约定其中约定其中a1 端为队列头端为队列头，an 端为队列尾端为队列尾 47 第第3 3章章 栈和队列栈和队列InitQueue(&Q)/初始化队列初始化队列DestroyQueue(&Q)/销毁队列销毁队列QueueEmpty(Q)/判队列是否空判队列是否空QueueLength(Q)/求队列长度求队列长度GetHead(Q,&e)/取队头元素取队头元素ClearQueue(&Q)/清空队列清空队列EnQueue(&Q,e)/入队列入队列DeQueue(&Q,&e)/出队列出队列QueueTravers(Q,visit()/遍历队列遍历队列p队列的基本操作队列的基本操作3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义 48 第第3 3章章 栈和队列栈和队列3.4.2 链队列链队列 typedef struct QNode /结点类型结点类型 QElemType data;struct QNode *next;QNode,*QueuePtr;p链队列结点实现链队列结点实现typedef struct /链队列类型链队列类型 QueuePtr front;/队头指针队头指针 QueuePtr rear;/队尾指针队尾指针 LinkQueue;p链队列数据类型实现链队列数据类型实现 49 第第3 3章章 栈和队列栈和队列Q.frontQ.rearp带头结点的链队列示意图带头结点的链队列示意图3.4.2 链队列链队列头结点头结点空队列空队列a1a2anQ.frontQ.rear 50 第第3 3章章 栈和队列栈和队列 Status InitQueue(LinkQueue&Q)/构造一个空队列构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);/存储分配失败存储分配失败 Q.front-next=NULL;return OK;3.4.2 链队列链队列p带头结点的链队列初始化带头结点的链队列初始化 51 第第3 3章章 栈和队列栈和队列 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 链队列链队列p带头结点的链队列入队算法带头结点的链队列入队算法 52 第第3 3章章 栈和队列栈和队列 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;3.4.2 链队列链队列p带头结点的链队列出队算法带头结点的链队列出队算法 53 第第3 3章章 栈和队列栈和队列DestroyQueue(&Q)/销毁队列销毁队列QueueEmpty(Q)/判队列是否空判队列是否空QueueLength(Q)/求队列长度求队列长度GetHead(Q,&e)/取队头元素取队头元素ClearQueue(&Q)/清空队列清空队列QueueTravers(Q,visit()/遍历队列遍历队列3.4.2 链队列链队列p带头结点的链队列其它操作讨论带头结点的链队列其它操作讨论 54 第第3 3章章 栈和队列栈和队列3.4.3 循环队列循环队列 循环队列属于顺序队列的一种，讨论在采用一般顺循环队列属于顺序队列的一种，讨论在采用一般顺序队列时出现的问题。序队列时出现的问题。p顺序队列讨论顺序队列讨论43210空队列空队列AA入队入队BAB入队入队EDCBAC,D,E相继相继入队入队Sq.rearSq.frontSq.rearSq.frontSq.rearSq.frontSq.rearSq.front 55 第第3 3章章 栈和队列栈和队列EDCBA队列满队列满EDCBA被删除被删除(出队出队)EDCB被删除被删除讨论结论：在采用一般顺序队列时出现假上溢现象？讨论结论：在采用一般顺序队列时出现假上溢现象？C,D,E相继相继被删除被删除p顺序队列讨论顺序队列讨论3.4.3 循环队列循环队列43210Sq.rearSq.frontSq.frontSq.rearSq.rearSq.frontSq.frontSq.rear 56 第第3 3章章 栈和队列栈和队列p循环队列示意图循环队列示意图3.4.3 循环队列循环队列01234CDESq.frontSq.rear01234CDESq.frontSq.rearFF入队入队01234CDESq.frontSq.rearFGG入队入队 57 第第3 3章章 栈和队列栈和队列3.4.3 循环队列循环队列#define MAXQSIZE 100 /最大队列长度最大队列长度 typedef struct QElemType *base;/动态分配存储空间动态分配存储空间 int front;/头指针，若队列不空，头指针，若队列不空，/指向队列头元素指向队列头元素 int rear;/尾指针，若队列不空，指向尾指针，若队列不空，指向 队列尾元素队列尾元素 的下一个位置的下一个位置 SqQueue;SqQueue Sq;p链队列数据类型实现链队列数据类型实现 58 第第3 3章章 栈和队列栈和队列 循环队列是顺序队列的一种特例，它是把顺序队循环队列是顺序队列的一种特例，它是把顺序队列构造成一个首尾相连的循环表。指针和队列元素之列构造成一个首尾相连的循环表。指针和队列元素之间关系不变。间关系不变。3.4.3 循环队列循环队列p循环队列的定义循环队列的定义01maxsize-1Sq.frontSq.rear 59 第第3 3章章 栈和队列栈和队列3.4.3 循环队列循环队列p循环队列空状态和满状态的讨论循环队列空状态和满状态的讨论讨论结论：讨论结论：循环队列空状循环队列空状态和满状态都态和满状态都满足满足Q.front=Q.rear01234CDESq.frontSq.rearFG满队列满队列01234Sq.frontSq.rear空队列空队列 60 第第3 3章章 栈和队列栈和队列 (1)另设一个标志区别队列是空还是满；另设一个标志区别队列是空还是满；3.4.3 循环队列循环队列p循环队列空状态和满状态的判别循环队列空状态和满状态的判别 例如：设一个变量例如：设一个变量count用来记录队列中元素个用来记录队列中元素个数，当数，当count=0时队列为空，当时队列为空，当count=MAXQSIZE时队列为满。时队列为满。61 第第3 3章章 栈和队列栈和队列 (2)队队满满条条件件：以以队队头头指指针针在在队队列列尾尾指指针针的的下下一一位位置置作作为为队队列列呈呈满满状状态态的的标标志志，牺牺牲牲一一个个存存储储空间；空间；3.4.3 循环队列循环队列p循环队列空状态和满状态的判别循环队列空状态和满状态的判别 队满条件为：队满条件为：(sq.rear+1)mod maxsize=sq.front 队空条件为：队空条件为：sq.rear=sq.front 62 第第3 3章章 栈和队列栈和队列01234CDESq.frontSq.rearF满队列满队列3.4.3 循环队列循环队列p循环队列空状态和满状态的判别循环队列空状态和满状态的判别队列满队列满 63 第第3 3章章 栈和队列栈和队列 Status InitQueue(SqQueue&Q)/构造一个空队列构造一个空队列Q Q.base=(ElemType*)malloc (MAXQSIZE*sizeof(ElemType);if(!Q.base)exit(OVERFLOW);/存储分配失败存储分配失败 Q.front=Q.rear=0;return OK;3.4.3 循环队列循环队列p队列初始化算法队列初始化算法 64 第第3 3章章 栈和队列栈和队列Status EnQueue(SqQueue&Q,ElemType e)/插入元素插入元素e为为Q的新的队尾元素的新的队尾元素 if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;/队列满队列满 Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;3.4.3 循环队列循环队列p入队列算法入队列算法 65 第第3 3章章 栈和队列栈和队列 Status DeQueue(SqQueue&Q,ElemType&e)/若队列不空，则删除若队列不空，则删除Q的队头元素，的队头元素，/用用e返回其值，并返回返回其值，并返回OK;否则返回否则返回ERROR if(Q.front=Q.rear)return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;3.4.3 循环队列循环队列p出队列算法出队列算法 66 第第3 3章章 栈和队列栈和队列分析以下两种状态如何求队列长度分析以下两种状态如何求队列长度 3.4.3 循环队列循环队列01234CDSq.frontSq.rear01234CDSq.frontSq.rear 67 第第3 3章章 栈和队列栈和队列int QueueLength(SqQueue Q)return(Q.rear-Q.front+MaxSize)%MaxSize;3.4.3 循环队列循环队列p求队列长度算法求队列长度算法 68 第第3 3章章 栈和队列栈和队列本章小结本章小结 熟练掌握熟练掌握：(1)栈、队列的定义、特点和性质；栈、队列的定义、特点和性质；(2)ADT栈、栈、ADT队列的设计和实现以及基本操作及队列的设计和实现以及基本操作及 相关算法。相关算法。重点学习：重点学习：ADT栈和队列在表达式求值、括号匹配、数制转换、栈和队列在表达式求值、括号匹配、数制转换、迷宫求解中的应用，提高利用栈和队列解决实际问题的迷宫求解中的应用，提高利用栈和队列解决实际问题的应用水平。应用水平。
展开阅读全文