第三章_栈和队列

1、重点重点：栈和队列的基本特征、表示：栈和队列的基本特征、表示与实现与实现难点难点：递归、循环队列：递归、循环队列第三章第三章 栈和队列栈和队列-2-第三章第三章 栈和队列栈和队列3.1 栈栈3.2 栈的应用举例栈的应用举例3.3 栈与递归的实现栈与递归的实现3.4 队列队列-3-3.1 栈栈n定义定义特殊的线性表特殊的线性表：操作受限：操作受限的线性表的线性表是限定仅在是限定仅在表尾进行插入或删除表尾进行插入或删除操作的线性表操作的线性表允许插入允许插入,删除的一端称为删除的一端称为栈顶栈顶(top),另一端称为另一端称为栈底栈底(bottom) n逻辑特征逻辑特征后进先出后进先出( (LIF

2、O) )nADT Stack初始化空栈、判断栈空、判断栈满初始化空栈、判断栈空、判断栈满取栈顶取栈顶 vs. GetElem(L, i, &e)入栈入栈 vs. ListInsert(&L, i, e)出栈出栈 vs. ListDelete(&L, i, &e)topbottom进栈进栈 出栈出栈an.a1-4-栈的类型定义栈的类型定义nADT Stack 数据对象：数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：数据关系： R1 | ai-1, aiD, i=2,.,n 约定约定an 端为栈顶，端为栈顶，a1 端为栈底。端为栈底。 基本操作：（后续）基

3、本操作：（后续） ADT Stack -5-基本操作基本操作nInitStack(&S)nDestroyStack(&S)nStackEmpty(S)nStackLength(S)nGetTop(S, &e)nClearStack(&S)nPush(&S, e)nPop(&S, &e)-6-基本操作（基本操作（1） InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈S已存在。 操作结果：栈S被销毁。-7-基本操作（基本操作（2） StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALE。 Stack

4、Length(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。-8- GetTop(S, &e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。基本操作（基本操作（3） ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。-9- Push(& &S, e) 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素基本操作（基本操作（4） Pop(&S, &e) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。-10-3.1 栈栈顺序栈的表示与实现顺序栈的表示与实现n顺序栈顺序栈n约定与类型定义：约定与类型定义：to

5、p的含义的含义#define STACK_INIT_SIZE 100/ 存储空间的初始分配量存储空间的初始分配量#define STACKINCREMENT 10/ 存储空间的分配增量存储空间的分配增量typedef structSElemType*base;/ 栈底指针栈底指针SElemType*top; / 栈顶指针栈顶指针(栈顶元素的下一个位置栈顶元素的下一个位置)intstacksize;/ 当前分配的存储容量当前分配的存储容量SqStack;-11-3.1 栈栈顺序栈的表示与实现顺序栈的表示与实现n顺序栈顺序栈n基本操作的实现基本操作的实现base空栈a 进栈b 进栈atopbase

6、topbasetopab约定：约定：top指向栈顶元素的下一个位置指向栈顶元素的下一个位置-12-3.1 栈栈顺序栈的表示与实现顺序栈的表示与实现basee 进栈f 进栈溢出e出栈edcbatopbasetopbasetop约定：约定：top指向栈顶元素的下一个位置指向栈顶元素的下一个位置edcban顺序栈顺序栈dcba-13-顺序栈的基本实现顺序栈的基本实现Status InitStack(SqStack &S)S.base=(SElemType *) malloc(STACK_INIT_SIZE * sizeof(SElemType);if (!S.base) exit(OVERFLOW)

7、;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;-14-顺序栈的基本实现顺序栈的基本实现Status GetTop(SqStack S,SElemType &e)if (S.top=S.base ) return ERROR;e=*(S.top-1);return OK;Status Pop(SqStack &S,SElemType &e)if (S.top=S.base ) return ERROR;e=*-S.top;return OK;-15-顺序栈的基本实现顺序栈的基本实现Status Push(SqStack &S,SElemT

8、ype e)if (S.top-S.base=S.stacksize)S.base=(SElemType *) realloc(S.base ,(S.stacksize+STACKINCREMENT )* sizeof(SElemType);if (!S.base) exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize=+STACKINCREMENT;*S.top+=e;return OK;-16-3.1 栈栈链栈的表示与实现链栈的表示与实现n链栈链栈n无栈满问题无栈满问题(除非分配不出内存除非分配不出内存), 空间可扩充空间可扩充n栈顶栈顶-

9、链表的表头链表的表头n可以不必引入头结点可以不必引入头结点(课件中的实例无头结点课件中的实例无头结点)Ntop-17-栈的链式存储结构和实现栈的链式存储结构和实现n链栈n栈的链式存储结构是运算受限的单链表n插入和删除操作仅限制在表头位置上进行n栈顶指针就是链表的头指针 n类型定义 typedef struct stacknodeSElemType elem;struct stacknode *next;stacknode,*StackList;nStackList s; 栈空条件s=NULL;-18-链栈基本运算的实现链栈基本运算的实现void InitStack(StackList S)S=

10、NULL;Status EmptyStack(StackList S)return (S=NULL);-19-链栈基本运算的实现链栈基本运算的实现void Push(StackList &S,SElemType x)p=(stacknode*) malloc(sizeof(stacknode);p-elem=x;p-next=S;S=p;SElemType Pop(StackList &S)if (EmptyStack(S) return (“link stack is underflow”); e=S-elem; p=S;S=p-next;free(p);return (e);-20-链栈基

11、本运算的实现链栈基本运算的实现SElemType GetTop(StackList S)if (EmptyStack(S) return (“stack list is underflow”);return (S-elem);void ClearStack(StackList S)while (!EmptyStack(S) Pop(S);int StackLength(StackList S)for (p=S,i=0;p;p=p-next,i+) ;return (i);-21-3.2 栈的应用举例栈的应用举例n数制转换数制转换n括号匹配的检验括号匹配的检验n行编辑程序行编辑程序n迷宫求解迷宫

12、求解n表达式求值表达式求值-22-数制转换数制转换十进制十进制N和其它进制数的转换是计算机实现计和其它进制数的转换是计算机实现计的基本问题，基于下列原理的基本问题，基于下列原理: N=(n div d)*d+n mod d ( 其中其中:div为整除运算为整除运算,mod为求余运算为求余运算) 例如例如 (1348)10=(2504)8，其运算过程如下：其运算过程如下：n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2低位低位高位高位-23-数制转换数制转换具体实现void convertion(void)/* 将输入的十进制数转换成八进制数并

13、打印输出*/InitStack(s);scanf( “%d”,N);while (N)Push(s,N%8); N=N/8;while (!EmptyStack(s)e=Pop(S);printf( “%d”,e);-24-括号匹配的检验括号匹配的检验n原则 n括号: () n正确格式:n()(),(),.n错误格式 n(),(),.n 实现思路n遇到(和 进栈n遇到)或 检查栈顶数据元素是否是(或n若不是出错 n若是弹出栈顶数据元素-25-括号匹配的检验括号匹配的检验/* 遇到遇到 ( 和和 进栈进栈 */if ( c = ( | c = )PushStack( s , c );/* 遇到遇

14、到 ) 或或 检查栈顶数据元素是否是检查栈顶数据元素是否是 ( 或或 */if ( c = ) | c = )e = GetStack( s ) ; /* 若不是：出错若不是：出错 若是弹：出栈顶数据元素若是弹：出栈顶数据元素 */if ( e = c)PopStack( s);else exit( “括号不匹配括号不匹配” );-26-行编辑程序行编辑程序n行编辑行编辑n正确地输入一行后存入用户数据区 n设立输入缓冲区n输入#删除前一个字符n输入删除一行n实现思路实现思路n用栈作为行输入缓冲区用栈作为行输入缓冲区n输入# 将栈顶数据元素弹出n输入 将整个栈清空 n输入“n” 将整个栈存入相应

15、用户数据缓冲区-27-行编辑程序行编辑程序void lineedit( )void lineedit( ) initstack(s); ch=getchar( ); initstack(s); ch=getchar( ); while(ch!=eof) while(ch!=eof) while(ch!=eof & ch!= while(ch!=eof & ch!=nn) ) switch(ch) switch(ch) case case # # : pop(s,c);break; : pop(s,c);break; case case : clearstack(s);break; : clea

16、rstack(s);break; default : push(s,ch); default : push(s,ch); ch=getchar( ); ch=getchar( ); clearstack(s); clearstack(s); if(ch!=eof) ch=gethar( ); if(ch!=eof) ch=gethar( ); destroystack(s); destroystack(s); -28-迷宫求解迷宫求解n设定当前位置的初值为入口位置设定当前位置的初值为入口位置do 若当前位置可通，则若当前位置可通，则将当前位置插入栈顶；将当前位置插入栈顶；若该位置是出口位置，则

17、结束；若该位置是出口位置，则结束；否则切换当前位置的东邻方块为新的当前位置；否则切换当前位置的东邻方块为新的当前位置；否则，否则，若栈不空且栈顶位置尚有其他方向未经探索，若栈不空且栈顶位置尚有其他方向未经探索， 则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，若栈不空但栈顶位置的四周均不可通， 则删去栈顶位置；则删去栈顶位置； 若栈不空，则重新测试新的栈顶位置，若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；直至找到一个可通的相邻块或出栈至栈空；while

18、（栈不空）（栈不空）迷宫问题迷宫问题#Q#穷穷举举求求解解1234#Q# 0 1 2 3 4 5 6 7 8 9 1001234567出口入口0 1 2 3 4 5 6 7 8 9 101 1 1 1 1 1 1 1 1 1 11 0 1 0 0 1 1 1 0 0 11 0 0 0 0 0 1 0 0 1 11 0 1 1 1 0 0 0 1 1 11 0 0 0 1 0 1 1 0 1 11 1 0 0 1 0 1 1 0 0 11 1 1 0 0 0 0 0 0 0 11 1 1 1 1 1 1 1 1 1 1迷宫的二维数组表示mazemn求解方法：从入口出发，沿某一方向搜索，若能走通，

19、则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索为止。(i,j)求迷宫中一条路径的方法求迷宫中一条路径的方法 （回溯法）（回溯法）把入口压入栈中；把入口压入栈中；while 栈不空时栈不空时 取栈顶元素；取栈顶元素；while 存在试探方向存在试探方向 求下一个位置求下一个位置mazegh；if （ mazegh 是出口块）是出口块） 打印路径上的每一个方块；打印路径上的每一个方块； return； if mazegh = 0） /可前进可前进 标记标记mazegh ； （g、h方向）进栈；方向）进栈； 前进到下一位置；前进到下一位置；-33-表达式求值表达式求值1

20、一些概念 算术表达式：由操作数、算术运算符和括号组：由操作数、算术运算符和括号组成的有意义的式子。成的有意义的式子。 二目运算符：对于运算符，参加运算的操作数必：对于运算符，参加运算的操作数必须有两个。须有两个。 中缀表达式：在算术表达式中，二目运算符位于：在算术表达式中，二目运算符位于参与运算的两个操作数中间。如：参与运算的两个操作数中间。如： a+b*c-d/e*f (a+b)*c-d/(e*f) a+b*(c-d/(e*f)-34-表达式求值表达式求值中缀表达式规定：（1）括号内的运算先执行。（2）运算符优先级由高（先执行）到低（后执行）为： /乘方 * / + -（3）相同优先级的运算

21、符，一般从左到右依次执行表达式求值表达式求值后缀表达式：把运算符放在参与运算的操作数后面的算术表达式。如： abc*+de/f*- 请比较 a+b*c-d/e*f ab+c*def*/- 请比较 (a+b)*c-d/(e*f) abcdef*/-*+ 请比较 a+b*(c-d/(e*f) 一旦遇运算符，即将紧靠它前面的两个操作数拿出来进行运算，结果作为操作数置于原来位置。 优点：后缀表达式中操作数的顺序与中缀表达式中操作数的顺序相同，但它更为简单，不使用括号，不考虑运算符的优先级别，操作单纯。表达式求值表达式求值2. 解决步骤（1）把中缀表达式转换成等价的后缀表达式（2）根据后缀表达式来求值这

22、两步都需要应用栈来解决问题 （1）把中缀表达式转换成等价的后缀表达式）把中缀表达式转换成等价的后缀表达式（1）把中缀表达式转换成等价的后缀表达式）把中缀表达式转换成等价的后缀表达式 建一个存放操作符的栈，栈底元素存放建一个存放操作符的栈，栈底元素存放字符字符“”。 扫描中缀表达式，若遇到操作数就将它扫描中缀表达式，若遇到操作数就将它直接输出到后缀表达式中；若遇到操作符，直接输出到后缀表达式中；若遇到操作符，则将其压到栈中，等待时机输出。则将其压到栈中，等待时机输出。 若要两个表达式等价，则后缀表达式要若要两个表达式等价，则后缀表达式要体现中缀表达式的运算优先次序。因此，要体现中缀表达式的运算优

23、先次序。因此，要在操作符进栈和出栈的时机，比较运算符的在操作符进栈和出栈的时机，比较运算符的优先级，并加以处理。优先级，并加以处理。规定规定同一优先级运算，同一优先级运算，从左向右依次进行从左向右依次进行在无括号或同层括号在无括号或同层括号的情况下，先做乘除的情况下，先做乘除运算，后做加减运算运算，后做加减运算先算括号内，先算括号内，再算括号外再算括号外（1）把中缀表达式转换成等价的后缀表达式）把中缀表达式转换成等价的后缀表达式具体做法：具体做法：逐个字符扫描中缀表达式，按下列情况分别处理：逐个字符扫描中缀表达式，按下列情况分别处理： （1）若为变量）若为变量(操作数操作数)，则立即输出。，则

24、立即输出。 （2）若为）若为“（”，则将其压入栈中。，则将其压入栈中。 （3）若为运算符，则将其优先级与栈顶字符的优先级）若为运算符，则将其优先级与栈顶字符的优先级进行比较。如果当前的运算符的优先级大于栈顶字符的优进行比较。如果当前的运算符的优先级大于栈顶字符的优先级先级,则将当前运算符进栈，若当前的运算符的优先级小则将当前运算符进栈，若当前的运算符的优先级小于或等于栈顶字符的优先级，则栈顶字符出栈并输出。于或等于栈顶字符的优先级，则栈顶字符出栈并输出。 （4）若为）若为“）”，则从栈中依次退出运算符并输出，则从栈中依次退出运算符并输出，直到将直到将“（”退出为止。退出为止。“（”不输出。不输

25、出。 （5）若为）若为“”，则从栈中依次退出所有运算符并输出，则从栈中依次退出所有运算符并输出，直到将直到将“”退出为止。退出为止。表达式求值表达式求值（1）把中缀表达式转换成等价的后缀表达式人工转换方法 a+b*c-(d+e) 第一步：按照运算符的优先级对所有的运算单位加括号：式子变成了：(a+(b*c)-(d+e) 第二步：把运算符号移动到对应的括号后面 ，则变成了：(a(bc)* )+ (de)+ )- 第三步：把括号去掉：abc*+de+- 后缀式子出现 例：3/（5*2+1） 352*1+/表达式求值表达式求值与后缀表达式相比，中缀表达式不容易被计算机解析，但仍被许多程序语言使用，因

26、为它符合人们的普遍用法。计算机处理后缀表达式的原理： 计算机处理后缀表达式求值问题是比较方便的，建立一个栈S 。从左到右读后缀表达式，如果读到操作数就将它压入栈S中，如果读到运算符则从栈中pop出两个操作数按操作符运算，再将运算的结果代替原栈顶，压入栈S中 。如果后缀表达式未读完，则重复上面过程，最后输出栈顶的数值则为结束。 表达式求值计算后缀表达式的算法 对后缀表达式求值比直接对中缀表达式求值简单。在后缀表达式中，不需要括号，而且操作符的优先级也不再起作用了。可以用如下算法对后缀表达式求值：1. 初始化一个空栈2. 从左到右读入后缀表达式3. 如果字符是一个操作数，把它压入栈。4. 如果字符

27、是个操作符，弹出两个操作数，执行恰当操作，然后把结果压入栈。如果不能够弹出两个操作数，表明后缀表达式的语法就不正确。5. 到后缀表达式末尾，从栈中弹出结果。若后缀表达式格式正确，那么栈应该为空。-47-3.3 栈与递归的实现栈与递归的实现n递归的定义递归的定义n递归的对象递归的对象：一个对象部分地包含它自己，或用它：一个对象部分地包含它自己，或用它自己给自己定义自己给自己定义。如某些数据结构的定义。如某些数据结构的定义树的定义树的定义:n有且只有一个根结点有且只有一个根结点n其余结点本身也是一棵树其余结点本身也是一棵树 n递归的过程递归的过程：一个过程直接或间接地调用自己：一个过程直接或间接地

28、调用自己如：如：0的阶乘是的阶乘是1，n(n0)的阶乘等于的阶乘等于n乘上乘上(n-1)的阶乘的阶乘-48-3.3 栈与递归的实现栈与递归的实现n递归的应用递归的应用n递归定义递归定义：如阶乘、：如阶乘、Fibonacci数列等数列等n数据结构数据结构：如表、树、二叉树等：如表、树、二叉树等n问题求解问题求解：如：如Hanoi塔塔-49-3.3 栈与递归的实现栈与递归的实现阶乘函数阶乘函数n定义是递归的定义是递归的时时当当时时当当 1 ,)!1( 0 , 1!nnnnn求解阶乘函数的递归算法求解阶乘函数的递归算法long fact ( long n ) if ( n = 0 ) return

29、1;/递归结束条件递归结束条件 else return n * fact (n- -1); /递归的规则递归的规则-50-3.3 栈与递归的实现栈与递归的实现阶乘函数阶乘函数 main( ): fact(4)参参数数传传递递结结果果返返回回 fact(4): fact(3): fact(2): fact(1): fact(0): 1直接定值为直接定值为1 1计算计算 4*fact(3)计算计算 3*fact(2)计算计算 2*fact(1)计算计算 1*fact(0)12624-51-3.3 栈与递归的实现栈与递归的实现Hanoi塔塔n问题求解是递归的问题求解是递归的Hanoi塔塔void h

30、anoi(int n, char a, char b, char c)n-圆盘数圆盘数 a-源塔座源塔座b-中介塔座中介塔座 c-目标塔座目标塔座n搬动方法搬动方法nn=1, a-cnn1:hanoi(n-1, a, c, b)a-chanoi(n-1, b, a, c)n注意注意用递归调用的结果，用递归调用的结果，不关注该结果如何不关注该结果如何获得的细节获得的细节-52-3.3 栈与递归的实现栈与递归的实现递归实现递归实现n调用函数与被调用函数调用函数与被调用函数-系统工作栈系统工作栈n执行被调用函数前执行被调用函数前n现场保护：现场保护：实在参数、返回地址实在参数、返回地址n为被调用函数

31、的局部变量分配存储区为被调用函数的局部变量分配存储区n将控制转移到被调函数的入口将控制转移到被调函数的入口 n从被调用函数返回调用函数前从被调用函数返回调用函数前n保存被调函数的计算结果保存被调函数的计算结果n释放被调函数的数据区释放被调函数的数据区n现场恢复：现场恢复：返回返回-53-3.3 栈与递归的实现栈与递归的实现递归实现递归实现n递归过程与递归工作栈递归过程与递归工作栈实际的系统中，一般综合考虑递归调用和非递归调用，统一处理实际的系统中，一般综合考虑递归调用和非递归调用，统一处理n递归工作栈递归工作栈n活动记录活动记录(栈帧栈帧stack frame)实在参数、局部变量、上一层的返回

32、地址实在参数、局部变量、上一层的返回地址n每进入一层递归，产生一个新的工作记录入栈每进入一层递归，产生一个新的工作记录入栈n每退出一层递归，就从栈顶弹出一个工作记录每退出一层递归，就从栈顶弹出一个工作记录n当前执行层的工作记录必是栈顶记录当前执行层的工作记录必是栈顶记录n例子：例子：P57 hanoi(3,a,b,c)-54-3.4 队列队列n定义定义特殊的线性表：操作受限的线性表特殊的线性表：操作受限的线性表只允许在一端进行插入，而在另一端删除元素只允许在一端进行插入，而在另一端删除元素允许插入的一端为允许插入的一端为队尾队尾(rear),允许删除的一端为允许删除的一端为队头队头(head)

33、 n双端队列双端队列：限定插入和删除操作在表的两端进行限定插入和删除操作在表的两端进行n逻辑特征：逻辑特征：先进先出先进先出( (FIFO) )nADT Queue：初始化空队初始化空队、入队、出队、判断队空、判断入队、出队、判断队空、判断队满、取队头队满、取队头队头队头入队入队 出队出队a1a2a3 an队尾队尾-55-抽象数据类型的定义抽象数据类型的定义nADT Queue 数据对象：数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系：数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头， an 端为队列尾。 基本操作：基本

34、操作： ADT Queue-56-基本操作基本操作 InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)-57-3.4 队列队列链队列的表示与实现链队列的表示与实现n链队列链队列n约定与类型定义：约定与类型定义：Q.front和和Q.rear的含义的含义n基本操作的实现基本操作的实现n无队满问题无队满问题(除非分配不出内存除非分配不出内存), 空间可扩充空间可扩充n引入头结点引入头结点topa1a2anQ.frontQ.r

35、ear-58-链队列的定义链队列的定义typedef struct QNode QElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct QueuePtr front; / 队头指针队头指针 QueuePtr rear; / 队尾指针队尾指针 LinkQueue;-59-队列运算指针变化状况队列运算指针变化状况空队列空队列-60-基本操作与实现基本操作与实现n初始化初始化 p62 Status InitQueue (LinkQueue &Q)n销毁队列销毁队列 p62 Status DestroyQueue (Lin

36、kQueue &Q)n入队入队 p62 Status EnQueue(LinkQueue &Q, QElemType e)n出队出队 p62 Status DeQueue(LinkQueue &Q, QElemType &e)n判队空判队空 Status QueueEmpty(LinkQueue Q)n取队头元素取队头元素 Status GetHead(LinkQueue Q,QElemType &e)-61-链队列初始化链队列初始化Status InitQueue (LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if (

37、!Q.front) exit(OVERFLOW);Q.front-next=NULL;return OK;-62-链队列的销毁链队列的销毁Status DestroyQueue (LinkQueue &Q)while (Q.front) Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; return OK;-63-Status EnQueue (LinkQueue &Q, QElemType e) p=(QueuePtr)malloc(sizeof(QNode); if (!p) exit(OVERFLOW); p-data = e; p-

38、next = NULL; Q.rear-next = p; Q.rear = p; return OK;链队列的插入（入队）链队列的插入（入队）-64-Status DeQueue (LinkQueue &Q, ElemType &e) 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;链队列的删除（出队）链队列的删除（出队）-65-Status QueueEmpty(LinkQueue Q)i

39、f (Q.front=Q.rear) return TRUE;return FALSE;判断链队列是否为空判断链队列是否为空-66-Status GetHead(LinkQueue Q,QElemType &e)if (QueueEmpty(Q) return ERROR;e=Q.front-next-data;return OK;取链队列的第一个元素结点取链队列的第一个元素结点-67-3. 循环队列循环队列队列的顺序存储结构队列的顺序存储结构n顺序队列顺序队列：n用一组地址连续的存储单元依次存放从队列头到队用一组地址连续的存储单元依次存放从队列头到队列尾的元素列尾的元素n设两个指针设两个指针

40、：nQ.front 指向队列头元素；指向队列头元素；nQ.rear 指向队列尾元素的下一个位置指向队列尾元素的下一个位置n初始状态（空队列）初始状态（空队列）：nQ.front = Q.rear=0n队列的真满与假满队列的真满与假满-68-类型定义类型定义 #define MAXQSIZE 100 /最大队列长度最大队列长度 typedef struct QElemType *base; / 动态分配存储空间动态分配存储空间 int front; / 头指针，若队列不空，头指针，若队列不空， /指向队列头元素指向队列头元素 int rear; / 尾指针，若队列不空，指向尾指针，若队列不空，指向 / 队列尾元素队列尾元素 的下一个位置的下一个位置 SqQueue-69-n n -70-n队列长度：队列长度：循环队列循环队列 (Circular Queue)-71-循环队列的进队和出队循环队列的进队和出队-72-说明说明n循环队列中要有一个元素空间浪费掉循环队列中要有一个元素空间浪费掉 - 约定队列头指针在队列尾指针的下一约定队列头指针在队列尾指针的下一位置上为位置上为“满满”的标志的标志n解决解决 Q.front=Q.rear不能判别队列不能判别队列“空空”还是还是“满满”的其他办法：的其他办法：n使用一个计数器记录队列中元素的总数（即使