第三章 栈和队列 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列.

Presentation on theme: "第三章 栈和队列 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列."— Presentation transcript:

1 第三章 栈和队列 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列

2 3.1 栈(Stack) 3.1.1 栈的定义及基本运算 栈是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当栈中没有元素时称为空栈。 假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出 (LIFO)表。

3 例、一叠书或一叠盘子。 栈顶 a n a n-1 a2 a1 …… 栈底

4 抽象数据类型——栈 ADT Stack{ 数据对象: D={ai |ai ElemSet, i=1,2,…,n (n>=0) }
数据关系：R={<ai-1,ai>| ai-1,ai D,i=2,3,…,n } 约定an端为栈顶，a1端为栈底。 基本操作: InitStack(&S) 操作结果: 建立一个空栈S DestroyStack(&S) 初始条件：栈S已存在 操作结果: 栈S被销毁

5 ClearStack(&S) 初始条件：栈S已存在 操作结果: 将S栈清空 StackEmpty(S) 操作结果：若栈S为空栈，返回true,否则返回false StackLength(S) 操作结果: 返回S的元素个数 GetTop(S,&e) //读栈顶元素 初始条件：栈S已存在且非空 操作结果: 用e返回栈顶元素

6 Push(&S,e) //入栈 初始条件：栈S已存在 操作结果: 将元素e插入到栈顶 Pop(&S,&e) //出栈 初始条件：栈S已存在且非空 操作结果: 删除S的栈顶元素，用e返回 StackTraverse(S,visit()) 操作结果: 从栈底到栈顶依次对S的每个元素调用visit() }ADT Stack

7 栈的表示和实现 由于栈的逻辑结构与线性表相同，因此线性表的存储结构对栈也适应。 顺序栈 链栈

8 顺序栈 栈的顺序存储结构简称为顺序栈，由于栈底位置是固定不变的，所以可以将栈底位置设置在数组两端的任何一端；而栈顶位置是随着入栈和出栈操作而变化的.

9 顺序栈的类型定义如下： #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct { SElemType *base; //栈底指针，base=NULL表明栈不存在 SElemType *top; //栈顶指针,top==base为栈空的标志 int stacksize; //栈当前可以使用的最大容量 }SqStack;

10 顺序栈的入栈与出栈 base base base 栈空 栈满 top top 1 2 3 4 5 A B C D E F top top 1
A B C D E F base top top 1 2 3 4 5 栈空 base 1 2 3 4 5 base top F top top E top top D top top C top top B top A 出栈 入栈 设数组大小为stacksize top==base,栈空，此时出栈，则下溢（underflow) top== stacksize,栈满，此时入栈，则上溢（overflow) 栈顶指针top,指向栈底 位置

11 在一个程序中同时使用两个栈 M-1 栈1底 栈1顶 栈2底 栈2顶

12 if(!S.base) exit(OVERFLOW); S.top=S.base;
基本操作的算法描述 1、构造一个空栈 Status InitSatck(SqStack &S) { S.base=(SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize= STACK_INIT_SIZE; }//end InitSatck

13 if (S.top==S.base) return ERROR; e=*(S.top-1); return OK;
2、返回栈顶元素 Status GetTop(SqStack S，SElemTtype &e) { if (S.top==S.base) return ERROR; e=*(S.top-1); return OK; }//end GetTop

14 3、入栈 Status Push(SqStack &S，SElemType e) { if(S. top-S. base>=S
3、入栈 Status Push(SqStack &S，SElemType 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; //end Push

15 4、出栈 Status Pop(SqStack &S，SElemType &e) { if(S. top==S
4、出栈 Status Pop(SqStack &S，SElemType &e) { if(S.top==S.base) return ERROR; e=*--S.top; return OK; }//end Pop

16 链栈 栈顶 栈底 top data next …... ^ 其操作与线性链表类似

17 3.2 栈的应用举例 数制转换 括号匹配的检验 行编辑程序 表达式求值

18 数制转换 十进制n和其它进制数d的转换是计算机实现计算的 基本问题,其解决方法很多,其中一个简单算法基于 下列原理: n=(n div d)*d + n mod d ( 其中:div为整除运算,mod为求余运算) 例如 (1348)10=(2504)8，其运算过程如下：

19 计算顺序 输出顺序 n n div 8 n mod 8 1348 168 4 例如：（1348)10 = (2504)8 ，
其运算过程如下： n n div 8 n mod 计算顺序 输出顺序

20 算法3.1 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); } //end conversion

21 { [ ( ) ( ) ] } 1 2 3 4 5 6 7 8 3.2.2 括号匹配的检验 分析出现的不匹配的情况:
括号匹配的检验 假设表达式中充许括号嵌套,则检验括号是否匹配的方法 可用“期待的急迫程度”这个概念来描述。例： { [ ( ) ( ) ] } 分析出现的不匹配的情况: 到来的右括号不是所“期待”的;

22 算法的设计思想： 1）凡出现左括号，则入栈； 2）凡出现右括号，首先检查栈是否空. 若栈空，则表明该“右括号”多余, 否则和栈顶元素比较， 若相匹配，则“左括号出栈”,否则表明括号不匹配. 3）表达式检验结束时， 若栈空，则表明表达式中括号匹配, 否则表明“左括号”有余

23 检验括号匹配的算法： Status matching(string &exp) { int state = 1; InitStack(S); while (i<=StrLength(exp) && state) switch of exp[i] { case “(” :{ Push(S,exp[i]); i++; break;} case “)”: { if(!StackEmpty(S) && GetTop(S)=“(”) { Pop(S,e); i++;} else { state = 0;} break; } if (StackEmpty(S) && state) return OK;}

24 3.2.3 行编辑程序 在用户输入程序或数据时，允许用户输入出差错，当发现有误时，可以及时更正。方法是：
行编辑程序 在用户输入程序或数据时，允许用户输入出差错，当发现有误时，可以及时更正。方法是： 设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。 假设退格符“#”表示前一个字符无效； 假设从终端接受了这样两行字符 whli##ilr#e（s#*s) 则实际有效的是下列两行： while (*s) putchar(*s++);

25 行编辑程序算法： void LineEdit( ) { InitStack(S); //栈S设为输入缓冲区 ch=getchar( ); while(ch!=eof){ while(ch!=eof && ch!=‘\n’){ switch(ch){ case ‘#’ : Pop(S,ch); //书上为c case : ClearStack(S); default : Push(S,ch); }//end switch }//end while 将从栈底到栈顶内的字符传送到用户数据区； ClearStack(s); if(ch!=eof) ch=gethar( ); } //end while DestroyStack(s); }//end LineEdit

26 3.2.5 表达式求值 例如：3*（7 – 2 ） （1）算术四则运算的规则： 由此，此表达式的计算顺序为：
表达式求值 例如：3*（7 – 2 ） （1）算术四则运算的规则： a. 从左算到右 b. 先乘除，后加减 c. 先括号内，后括号外 由此，此表达式的计算顺序为： 3*（7 – 2 ）= 3 * 5 = 15

27 3.2.5 表达式求值 （2）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符1和2 ，都要比较优先权关系。
表达式求值 （2）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符1和2 ，都要比较优先权关系。 算符优先法所依据的算符间的优先关系见教材P53表3.1 由表可看出，右括号 ) 和井号 # 作为2时级别最低； 由c规则得出： * ，/， + ，-为1时的优先权低于‘（’，高于‘）’ 由a规则得出：‘（’==‘）’ 表明括号内运算，已算完。 ‘ # ’==‘ # ’ 表明表达式求值完毕。 令OP={+，-，*，/，（，），#}

28 3.2.5 表达式求值 （3）算法思想： 设两个栈：操作符栈 OPTR ，操作数栈 OPND
表达式求值 （3）算法思想： 设两个栈：操作符栈 OPTR ，操作数栈 OPND 栈初始化：设操作数栈 OPND 为空；操作符栈 OPTR 的栈底 元素为表达式起始符 ‘#’； 依次读入字符：是操作数则入OPND栈，是操作符则要判断： if 操作符(1)< 栈顶元素(2)，则出栈、计算，结果压入OPND栈 操作符== 栈顶元素且不为‘#’，脱括号（弹出左括号）； 操作符 > 栈顶元素，压入OPTR栈。

29 例 求表达式3*(7-2) OPTR OPND INPUT OPERATE 3*(7-2)# Push(opnd,’3’) #
例 求表达式3*(7-2) OPTR OPND INPUT OPERATE 3*(7-2)# Push(opnd,’3’) # *(7-2)# 3 # Push(optr,’*’) #, * 3 (7-2)# Push(optr,’(’) #, *, ( 3 7-2)# Push(opnd,’7’) #, *, ( 3,7 -2)# Push(optr,’-’) #, *, (, － 3,7 2)# Push(opnd,’2’) #, *, (, － 3,7,2 )# Operate(7-2) #, *, ( 3,5 )# Pop(optr) #, * 3,5 # Operate(3*5) # 15 GetTop(opnd)

30 Status EvaluateExpression( OperandType &result) {
InitStack(OPND); InitStack(OPTR); Push(OPTR ,’#’); c=getchar( ); while((c!=‘#’)&&(GetTop(OPTR)!=‘#’)) { if (!In(c,OP) { Push(OPND,c); c=getchar( );} else switch(compare(c,GetTop(OPTR))) { case ‘>’ : Push(OPTR , c); c=getchar( ); break; case ‘=’: Pop(OPTR,x); c=getchar( ); break; case ‘<’ : Pop(OPTR,tem); Pop(OPND,b ); a=Pop(OPND,a ); result=Operate(a,tem,b); Push(OPND,result); c=getchar( ); break; } //switch }//while result=GetTop(OPND);}//End EvaluateExpression

31 迷宫求解 入口 出口

32 求迷宫路径算法的基本思想是： 若当前位置“可通”，则纳入路径，继续前进; 若当前位置“不可通”，则后退，换方向继续探索; 若四周“均无通路”，则将当前位置从路径中删除出去。

33 求迷宫中一条从入口到出口的路径的算法思想：
设当前位置为入口位置 do{ if(当前位置可通){ 当前位置插入栈顶; if(该位置是出口位置) 结束 else 切换当前位置的东邻方块为新的当前位置; } else{ if(栈不空栈顶位置尚有其它方向未经探索) 设定新的当前位置为顺时针方向旋转找到的顶点 位置的下一个邻块; if(栈不空且栈顶位置的四周均不通){ 删去栈顶元素位置,直至找到一个可通的相邻块或 出栈或栈空; }while(栈不空);

34 PosType seat; //通道块在迷宫中的“坐标位置” int di; //从此通道块走向下一通道块的方向
Type struct{ int ord; //通道块在路径上的序号 PosType seat; //通道块在迷宫中的“坐标位置” int di; //从此通道块走向下一通道块的方向 }SElemType; //栈元素类型 Status MazePath(MazeType maze, PosType start, PosType end) { InitStack(S); curpos=start; //当前位置为入口位置 curstep=1; //探索第一步 do{ if(Pass(curpos)){ //当前位置可以通过 footprint(curpos); //留下足印 e=(curstep,curpos,1); Push(S,e); //加入路径 if(curpos==end) return(TRUE); //到达终点 curpose=NextPos(curpos,1); //下一个位置是当前位置的东邻 curstep++;

35 while(e.di==4 && !StackEmpty(S)){
else{ //当前位置不通 if(!StackEmpty(S)){ Pop(S,e); while(e.di==4 && !StackEmpty(S)){ MarkPrint(e.seat); Pop(S,e);//留下不能通过的标记并后退 }//end while if(e.di<4){ e.di++; Push(S,e); //换下一个方向探索 curpos=NextPos(e.seat, e.di);//新位置是旧位置的相邻块 }//end if } //end if }//end else }while(!StackEmpty(S)); return(FALSE); }//end MazePath

36 3.3 栈与递归的实现 一、函数的嵌套调用 r s t 子函数2 r s 子函数1 r s t 子函数3 r 主程序 r s r

37 3.3 栈与递归的实现 二、递归函数及其实现 递归：函数直接或间接的调用自身 实现：建立递归工作栈

38 3.3 栈与递归的实现 例1 递归的执行情况分析--n! int fact (int w) { if ( w==0) fact= 1;
else fact=w* fact ( w-1); } main() { int f; f=fact(3); print(f); }

39 3.3 栈与递归的实现 递归过程三要素: 1.定义出口 2.把一个大的问题划分成同类型的子问题 3.解的合成

40 递归调用执行情况如下： int fact (int w) {1if ( w==0) 2 fact= 1; 3else
4fact=w* fact( w-1); } top 地址 w

41 递归调用执行情况如下： w 3 3*fact(2); 4 w=3 int fact (int w) {1if ( w==0)
3else 4fact=w* fact( w-1); } w 3 3*fact(2); w=3 top 地址 w

42 递归调用执行情况如下： w w 2 3 2*fact(1); 3*fact(2); 4 w=2 4 w=3 int fact (int w)
{1if ( w==0) 2 fact= 1; 3else 4fact=w* fact( w-1); } w w 2 3 2*fact(1); 3*fact(2); 4 w=2 4 w=3 top 地址 w

43 递归调用执行情况如下： w 1 w w 1*fact(0); 2 3 2*fact(1); 3*fact(2); top 4 w=1
int fact (int w) {1if ( w==0) 2 fact= 1; 3else 4fact=w* fact( w-1); } w w 1*fact(0); 2 3 2*fact(1); 3*fact(2); top 4 w=1 4 w=2 4 w=3 地址 w

44 递归调用执行情况如下： w w 1 w w 1*fact(0); 2 fact(0)=1 3 2*fact(1); 3*fact(2);
w 1 int fact (int w) {1if ( w==0) 2 fact= 1; 3else 4fact=w* fact( w-1); } w w 1*fact(0); 2 fact(0)=1 3 2*fact(1); 3*fact(2); top 4 w=1 4 w=2 4 w=3 地址 w

45 递归调用执行情况如下： w w w 2 1 w 1*fact(0); fact(0)=1 3 2*fact(1); 3*fact(2);
w w w 2 1 int fact (int w) {1if ( w==0) 2 fact= 1; 3else 4fact=w* fact( w-1); } w 1*fact(0); fact(0)=1 3 2*fact(1); 3*fact(2); fact(1)=1 4 w=2 4 w=3 top 地址 w

46 递归调用执行情况如下： w w w 2 1 w 2*fact(1); 1*fact(0); fact(0)=1 3 fact(2)=2
w w w 2 1 int fact (int w) {1if ( w==0) 2 fact= 1; 3else 4fact=w* fact( w-1); } w 2*fact(1); 1*fact(0); fact(0)=1 3 fact(2)=2 3*fact(2); fact(1)=1 4 w=3 top 地址 w

47 递归调用执行情况如下： w w w 2 1 w 2*fact(1); 1*fact(0); fact(0)=1 3 fact(2)=2
w w w 2 1 int fact (int w) {1if ( w==0) 2 fact= 1; 3else 4fact=w* fact( w-1); } w 2*fact(1); 1*fact(0); fact(0)=1 3 fact(2)=2 3*fact(2); fact(1)=1 fact(3)=6 top 地址 w

48 例2：Tower of Hanoi问题 问题描述：有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3……n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则： 每次只能移一个圆盘 圆盘可在三个塔座上任意移动 任何时刻，每个塔座上不能将大盘压到 小盘上

49 解决方法 执行情况 递归工作栈保存内容：形参n,x,y,z和返回地址 返回地址用行编号表示 n=1时，直接把圆盘从A移到C
n>1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题 执行情况 递归工作栈保存内容：形参n,x,y,z和返回地址 返回地址用行编号表示 n x y z 返回地址

50 printf("Input number of disks "); scanf("%d",&n);
main() { int m; printf("Input number of disks "); scanf("%d",&n); printf(" Steps : %3d disks ",n); hanoi(n,‘A',‘B',‘C'); (0) } void hanoi(int n,char X,char Y,char Z) (1) { (2) if(n==1) (3) move(1,X,Z); (4) else{ (5) hanoi(n-1,X,Z,Y); (6) move(n,X,Z); (7) hanoi(n-1,Y,X,Z); (8) } (9) } A B C 1 2 3 3 A B C 0 3 A B C 0 2 A C B 6 3 A B C 0 2 A C B 6 1 A B C 6 A B C 3 A B C 0 2 A C B 6

51 printf("Input the number of disks scanf("%d",&n);
3 A B C 0 2 A C B 6 main() { int n; printf("Input the number of disks scanf("%d",&n); printf("The steps to moving %3d hanoi(n,'X','Y',‘Z'); (0) } void hanoi(int n,char X,char Y,char Z) (1) { (2) if(n==1) (3) move(1,X,Z); (4) else{ (5) hanoi(n-1,X,Z,Y); (6) move(n,X,Z); (7) hanoi(n-1,Y,X,Z); (8) } (9) } A B C 3 A B C 0 2 A C B 6 1 C A B 8 A B C 3 A B C 0 2 A C B 6 3 A B C 0

52 printf("Input the number of disks scanf("%d",&n);
main() { int n; printf("Input the number of disks scanf("%d",&n); printf("The steps to moving %3d hanoi(n,'X','Y','Z'); (0) } void hanoi(int n,char X,char Y,char Z) (1) { (2) if(n==1) (3) move(1,X,Z); (4) else{ (5) hanoi(n-1,X,Z,Y); (6) move(n,X,Z); (7) hanoi(n-1,Y,X,Z); (8) } (9) } 3 A B C 0 A B C 3 A B C 0 2 B A C 8 3 A B C 0 2 B A C 8 1 B C A 6 A B C 3 A B C 0 2 B A C 8

53 printf("Input the number of disks scanf("%d",&n);
3 A B C 0 2 B A C 8 A B C main() { int n; printf("Input the number of disks scanf("%d",&n); printf("The steps to moving %3d hanoi(n,'X','Y','Z'); (0) } void hanoi(int n,char X,char Y,char Z) (1) { (2) if(n==1) (3) move(1,X,Z); (4) else{ (5) hanoi(n-1,X,Z,Y); (6) move(n,X,Z); (7) hanoi(n-1,Y,X,Z); (8) } (9) } 3 A B C 0 2 B A C 8 1 A B C 8 A B C 3 A B C 0 2 B A C 8 3 A B C 0 栈空

54 3.4 队列 3.4.1 抽象数据类型队列的定义 队列的定义及特点 定义：队列是限定只能在表的一端进行插入，
而在表的另一端进行删除的线性表。 队尾(rear)——允许插入的一端 队头(front)——允许删除的一端 队列特点：先进先出(FIFO)

55 抽象数据类型队列的定义 ADT Queue{ 数据对象： D={ ai|ai QElemSet, i=1,2,…,n ,n>=0 } 数据关系： R={<ai-1,ai>|ai-1,ai D,i=2,…,n} 基本操作: InitQueue(&Q) 操作结果:构造一个空队列Q DestroyQueue(&Q) 初始条件:队列已存在 操作结果:队列Q被销毁，不再存在

56 操作结果:若Q为空队列，返回true,否则返回false QueueLength(Q) 操作结果:返回Q的元素个数
ClearQueue(&Q) 初始条件:队列已存在 操作结果:将Q清为空队列 QueueEmpty(Q) 操作结果:若Q为空队列，返回true,否则返回false QueueLength(Q) 操作结果:返回Q的元素个数 GetHead(Q,&e) 初始条件:队列Q非空 操作结果:用e返回队头元素

57 QueueTraverse(Q,visit()) 初始条件: 队列Q非空
EnQueue(&Q,e)//入队 初始条件: 队列已存在 操作结果: 插入元素e为Q的新队尾元素 DeQueue(&Q,&e) //出队 初始条件: 队列Q非空 操作结果: 删除Q的队头元素，用e返回 QueueTraverse(Q,visit()) 初始条件: 队列Q非空 操作结果: 从队头到队尾，依次对Q的每个数据元素调 用函数visit().一旦visit()失败，则操作失败 }ADT Queue

58 3.4.2 链队列 typedef struct{ typedef struct QNode{ QueuePtr front;
队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，将链队列的类型LinkQueue定义为一个结构类型： typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue; typedef struct QNode{ QElemType data; struct QNode *next; }QNode,*QueuePtr;

59 链队列上实现的基本运算： 1.构造一个空队列 void InitQueue(LinkQueue &Q) { Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); //if(!Q.front) exit(OVERFLOW); Q.front->next=NULL; }//end InitQueue

60 2.销毁队列 void DestoryQueue(LinkQueue &Q) { while(Q.front){ Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; }//end while }//end DestoryQueue

61 3.入队 void EnQueue(LinkQueue &Q, QElemType e){ p=(QueuePtr )malloc(sizeof(QNode)); p–>data=e; p–>next=null; Q.rear->next=p; Q.rear=p; }// end EnQueue

62 4. 出队 Status DeQueue(LinkQueue &Q, QElemType &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); }//end DeQueue 注意：在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。

63 3.4.3 循环队列的顺序存储结构和实现 （用一维数组实现sq[M]） 空队列条件：front==rear J4,J5,J6入队 rear
1 2 3 4 5 J4 J5 J6 front front=0 rear=0 1 2 3 4 5 队空 1 2 3 4 5 front J1,J2,J3入队 rear J1,J2,J3出队 J1 J2 J3 rear 1 2 3 4 5 front front rear rear J3 front rear J2 front J1 设两个指针front,rear, 约定： front指示队头元素； rear指示队尾元素的下一个位置； 初值front=rear=0 入队列：sq[rear++]=x; 出队列：x=sq[front++];

64 存在问题 解决方案 设数组维数为M，则： 当front=0,rear=M时，再有元素入队发生溢出——真溢出
队首固定，每次出队后剩余元素向下移动——浪费时间 循环队列 基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M, 则令rear=0; 实现：利用“模”运算 入队： rear=(rear+1)%M; sq[rear]=x; 出队： front=(front+1)%M; x=sq[front]; M-1 1 front rear …...

65 队尾指针加1追上队头，队列中有一个空额，但避免判断标志的时间上的损失
1 2 3 4 5 rear front 队空：front==rear 队满：front==rear J4 J5 J6 1 2 3 4 5 rear front 初始状态 J4,J5,J6出队 J4 J5 J6 1 2 3 4 5 rear front J9 J8 J7 J7,J8,J9入队 解决方案： 1.另外设一个标志以区别队空、队满 2.少用一个元素空间 队空：front==rear 队满：(rear+1)%M==front 队尾指针加1追上队头，队列中有一个空额，但避免判断标志的时间上的损失

66 循环队列类型说明： #define QueueSize 100 typedef Struct{ int front; int rear;
QElemType *base; 或QElemType data[QueueSize]; }SqQueue;

67 基本操作的算法描述 1. 构造空队列 void InitQueue(SqQueue &Q){
Q.base=(QElemType*)malloc(QueueSize*sizeof(QElemType)); if(!Q.base) exit(OVERFLOW); Q.front=Q.rear=0; }

68 2. 返回队列长度 int QueueLength(SqQueue Q){
Return (Q.rear-Q.front+ QueueSize )% QueueSize; }

69 基本操作的算法描述 3. 入队 Status EnQueue(SqQueue &Q,QElemType e){
if((Q.rear+1)% QueueSize ==Q.front ) return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)% QueueSize; return OK; }

70 基本操作的算法描述 4. 出队 Status DeQueue(SqQueue &Q,QElemType &e) {
if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)% QueueSize; return OK; }

71 本章小结 理解栈和队列这两种抽象数据类型的特点及与线性表的异同 熟悉顺序栈和链栈的组织方法以及基本运算的实现 理解递归算法
掌握链队列和循环队列的组织方法、简单算法实现 队满、队空的判断条件及其描述

72 作业 书面作业: p21: 3.1题, p22: 3.4题 p23: 3.12题，p24: 3.13题 p25: 3.29题 上机作业:
迷宫求解