栈栈应用举例队列PPT课件.ppt

1 3.1 栈栈 3.2 栈的应用举例栈的应用举例 3.3 队列队列Ø第第3 3章章 栈和队列栈和队列 2 第第3 3章章 栈和队列栈和队列 重点重点: (1)栈、队列的定义、特点、性质和应用；栈、队列的定义、特点、性质和应用；(2)ADT栈、栈、ADT队列的设计和实现以及基本操作及队列的设计和实现以及基本操作及相关算法相关算法 难点难点: (1)循环队列中对边界条件的处理；循环队列中对边界条件的处理；(2)分析分析栈和队列在表达式求值、括号匹配、数制转换、迷栈和队列在表达式求值、括号匹配、数制转换、迷宫求解中的应用实例，提高利用栈和队列解决实际宫求解中的应用实例，提高利用栈和队列解决实际问题的应用水平问题的应用水平 本章重点难点 3 第第3 3章章 栈和队列栈和队列 3.1 栈栈 3.2 栈的应用举例栈的应用举例 3.3 队列队列Ø第第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结构结构) an……a2a1栈底栈底栈顶栈顶入栈入栈出栈出栈3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义 7 第第3 3章章 栈和队列栈和队列 ADT Stack { 数据对象：数据对象： 数据关系：数据关系： p抽象数据类型栈抽象数据类型栈基本操作：基本操作： } ADT StackR1＝＝{ | ai-1, ai∈∈D, i=2,...,n }约定约定an 端为栈顶，端为栈顶，a1 端为栈底端为栈底 D＝＝{ ai | ai ∈∈ElemSet, i=1,2,...,n, n≥0 }见下页见下页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) 设置基地址和栈顶地址设置基地址和栈顶地址(3) 设置栈容量设置栈容量=STACK_INIT_SIZE 12 第第3 3章章 栈和队列栈和队列 Status InitStack (SqStack &S){ // 构造一个空栈构造一个空栈S =(ElemType*)malloc(STACK_INIT_SIZE* sizeof(ElemType)); if (!) exit (OVERFLOW); //存储分配失败存储分配失败 = ; = STACK_INIT_SIZE; return OK;}3.1.2 栈的表示和实现栈的表示和实现p栈初始化算法栈初始化算法 13 第第3 3章章 栈和队列栈和队列3.1.2 栈的表示和实现栈的表示和实现p入栈操作演示入栈操作演示(1) 如果栈满，给栈增加容量如果栈满，给栈增加容量abcdef(2) 将数据存入栈顶位置，栈顶后移一位将数据存入栈顶位置，栈顶后移一位e 14 第第3 3章章 栈和队列栈和队列 Status Push (SqStack &S, SElemType e) { if ( - >= ) { = (ElemType *) realloc ( , ( + STACKINCREMENT) * sizeof (ElemType)); if (!) exit (OVERFLOW); //存储分配失败存储分配失败 = + ; += STACKINCREMENT; } *++ = 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.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) outcha@putchar(*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 ‘<‘: Push(OPTR,c);c=getchar();break;case ‘=’: Pop(OPTR,x);c=getchar;break;3.2.5 表达式求值表达式求值 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 队列队列Ø第第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 抽象数据类型栈的定义抽象数据类型栈的定义D＝＝{ai | ai∈∈ElemSet, i=1,2,...,n, n≥0}R1＝＝{ | 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章章 栈和队列栈和队列p带头结点的链队列示意图带头结点的链队列示意图3.4.2 链队列链队列^头结点头结点空队列空队列a1a2……an 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; ->next = p; = 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 循环队列循环队列 循环队列属于顺序队列的一种，讨论在采用一般顺循环队列属于顺序队列的一种，讨论在采用一般顺序队列时出现的问题。