第3章栈和队列

1第三章栈和队列2

第三章栈和队列

3.1栈

3.2栈的应用举例

3.3

栈与递归

3.4队列3

3.1栈3.1

.1栈的概念3.1

.2栈的顺序存储和实现3.1

.3栈的链式存储和实现43.1栈栈是限定仅能在表尾一端进行插入、删除操作的线性表（a1,a2,...,ai-1,ai,ai+1,…,an

）插入删除3.1.1栈的概念一

什么是栈?53.1栈

将表中允许进行插入、删除操作的一端称为栈顶(Top)，栈顶的当前位置是动态变化的，由一个栈顶指针指示其位置。表的另一端称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作称为进栈或入栈，删除操作称为出栈或退栈。

6栈

栈的特点后进先出(LIFO)第一个进栈的元素在栈底，

最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素7Question一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（

）。

A.23415

B.54132

C.23145

D.154328Question一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（

B

）。

A.23415

B.54132

C.23145

D.1543293.1栈栈的基本操作数据元素：可以是任意类型的数据，但必属于同一个数据对象。关系：栈中数据元素之间是线性关系。1）

构造一个空栈S；2）进栈操作Push3）出栈操作Pop4)取栈顶元素top103.1栈topbasebasetopbasetopbasetopAABCDEAB

栈操作图示空栈

A进栈

BCDE进栈EDC出栈113.1栈3.1.2栈的顺序存储和实现

如何存储栈?进栈、出栈等操作如何实现？？#defineMAX50intstack[MAX];inttop=0;123.1栈约定栈顶指针指向栈顶元素的下一个位置当栈用顺序结构存储时，栈的基本操作如建空栈、进栈、出栈等操作如何实现？？

顺序栈的图示topMAX-1nn-1n-210anan-1a2a1133.1栈1)进栈操作主要语句if(top>=MAX)printf(“overflow”);else{stack[top]=x;top++;}

MAX-1nn-1n-210anan-1a2a1x进栈前top

x进栈后MAX-1nn-1n-210xanan-1a2a1top143.1栈2）出栈操作主要语句if(top==0){printf(“underflow”);return(NULL);}top--;return(stack[top]);

出栈操作前

出栈操作后MAX-1nn-1n-210anan-1a2a1MAX-1nn-1n-210anan-1a2a1toptop15教材中顺序栈的数据类型定义：typedefstructSqStack{SElemType*base;//栈底指针

SElemType*top;//栈顶指针

intstacksize；//当前已分配的存储空间}SqStack;#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;基本操作如下：16

StatusInitStack(Stack&S)

{//

构造一个空栈S

S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S.base)exit(OVERFLOW);

//

存储分配失败

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOk;

}

StatusGetTop(StackS,ElemType&e)

{

//

若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR

if(S.top==S.base)return

ERROR;

e=*(S.top-1);

//

返回非空栈中栈顶元素

returnOK;

}17StatusPush(Stack&S,ElemTypee){插入元素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;}

18StatusPop(Stack&S,ElemType&e)

{

//

若栈不空，则删除S的栈顶元素，用e返回其值，

//

并返回OK；否则返回ERROR

if(S.top==S.base)returnERROR;

e=*--S.top;

//

返回非空栈中栈顶元素

returnOK;

}

193.1栈3.1.3

栈的链式存储和实现栈的链式存储结构，也称链栈，如图所示：栈顶元素为链首栈尾元素为链尾不设头结点，直接用头指针指向链首，即栈顶元素Datanexttop栈顶栈底an-1a1an203.1栈(1)进栈算法主要语句

p=(NODE*)malloc(sizeof(NODE));p->data=x;p->next=top;top=p;Datanexttop栈顶栈底an-1a1anan+1p213.1栈(2)出栈算法主要语句

if(top==NULL)return(NULL);p=top;top=p->next;return(p);若带头结点L的链栈进栈、出栈算法主要语句？Datanexttop栈顶栈底an-1a1anp22Question输入序列为ABC，输出序列为CBA时，经过的栈操作为（

）A.push,pop,push,pop,push,pop

B.push,push,push,pop,pop,popC.push,push,pop,pop,push,pop

D.push,pop,push,push,pop,pop23Question输入序列为ABC，输出序列为CBA时，经过的栈操作为（

B

）A.push,pop,push,pop,push,pop

B.push,push,push,pop,pop,popC.push,push,pop,pop,push,pop

D.push,pop,push,push,pop,pop24

小结

1栈是限定仅能在表尾一端进行插入、删除操作的线性表；

2栈的元素具有后进先出的特点；

3栈顶元素的位置由一个称为栈顶指针的变量指示，进栈、出栈操作要修改栈顶指针；

3.1栈25共享栈技术（最常用的是两个栈的共享）：主要利用栈“栈底位置不变，栈顶位置动态变化”的特性。为两个栈申请一个共享的一维数组空间S［M］，将两个栈的栈底分别放在一维数组的两端，分别是0，M-1。由于两个栈顶动态变化，形成互补，使得每个栈可用的最大空间与实际使用的需求有关。优点：两栈共享比两个栈分别申请M/2的空间利用率高。26设两个栈共享的数据结构定义如下：

＃defineM100typedefstructDqStack{SElemTypeStack［M］;inttop［2］;//top［0］和top［1］分别为两个栈顶指示器

}DqStack;27共享栈

28初始化操作。voidInitStack(DqStack*S){S.top［0］=0;S.top［1］=M-1;}以下三个操作具体算法自学29

进栈操作算法? intPush(DqStack*S,SElemTypex,inti) //把数据元素x压入i号栈30(2)进栈操作算法。intPush(DqStack*S,StackElementTypex,inti){//把数据元素x压入i号栈

if(S.top［0］+1==S.top［1］)//栈已满

return(FALSE);switch(i){case0:S.Stack［S.top［0］］=x;S.top［0］++; break;31

case1:S.Stack［S.top［1］］=x;S.top［1］--;break;default://i参数错误

return(FALSE)}return(TRUE);}32

出栈操作算法? intPop(DqStack*S,SElemType*x,inti) //从i号栈中弹出栈顶元素并送到x中33(3)出栈操作算法。intPop(DqStack*S,StackElementType*x,inti){switch(i){case0:if(S.top［0］==0)return(FALSE); S.top［0］--; *x=S.Stack［S.top［0］］;break;case1:if(S.top［1］==M-1)return(FALSE); S.top［1］++; *x=S.Stack［S.top［1］］;break;default:return(FALSE);}return(TRUE);}34

小结

1栈是限定仅能在表尾一端进行插入、删除操作的线性表；

2栈的元素具有后进先出的特点；

3栈顶元素的位置由一个称为栈顶指针的变量指示，进栈、出栈操作要修改栈顶指针；

3.1栈353.2栈的应用举例例1数制转换对于输入的任意一个非负十进制数，显示输出与其等值的八进制数数制转换方法

N=(Ndiv8)108+Nmod8N：十进制数，div：整除运算，mod：求余运算；

(1348)10=283+582+08+4=(2504)8N1348168212Ndiv81682120Nmod84052

计算时从低位到高位顺序产生八进制数的各个数位结果：2504显示时按从高位到低位的顺序输出363.2栈的应用举例voidconversion()

{InitStack(s);//建空栈

scanf(“%d”,&x);//输入一个非负十进制整数

while(x!=0)//x不等于零循环

{push(s,x%8);//x/8第一个余数进栈

x=x/8;//整除运算

}

while(!StackEmpty(s))//输出存放在栈中的八制数位

{x=pop(s);

printf(“%d”,x);

}

}杀鸡用牛刀仅作示例37

例2.括号匹配问题设表达式中包含三种括号：圆括号、方括号和花括号，它们可互相嵌套，如(［{}］(［］))或({(［］［()］)})。 算法思想：可设一个栈，每读入一个括号，若是左括号，直接入栈，等待相匹配的同类右括号；若是右括号，且与当前栈顶的左括号同类型，则二者匹配，将栈顶的左括号出栈，否则属于不合法的情况。 如果输入序列已读尽，而栈中仍有等待匹配的左括号，或者读入了一个右括号，栈中已无等待匹配的左括号，均属不合法的情况。当输入序列和栈同时变为空时，说明所有括号完全匹配。38voidBracketMatch(char*str)//str［］中为输入的字符串，利用栈来检查该字符串中的括号是否匹配{InitStack(&S);for(i=0;i<N;i++)//对字符串中的字符逐一扫描

{switch(str［i］){case′(′,′［′,′{′: Push(&S,str［i］);break;case′)′,′］′,′}′:if(IsEmpty(S)){printf(″\n右括号多余!″);return;}39else{GetTop(&S,&ch);if(Match(ch,str［i］))//Match（该函数需要另外定义）判断两个括号是否匹配Pop(&S,&ch);//已匹配的左括号出栈

else{printf(″\n对应的左右括号不同类!″);return;}}}//switch}//forif(IsEmpty(S))printf(″\n括号匹配!″);elseprintf(″\n左括号多余!″);}40例3表达式求值以表达式A*B+C\D为例说明利用栈的求值过程：操作数：常数、变量或常量标识符运算符：**/*+-

界限符：()#运算符分为算术运算符、关系运算符和逻辑运算符三类界限符有左右括号和表达式结束符等。

运算符和界限符统称算符。41表达式运算顺序：由于某些运算符可能有更高的优先级，因此表达式不可能严格的从左到右进行运算。#代表开始或结束符42表达式的求值：例5+6(1+2)-4

按照四则运算法则，上述表达式的计算过程为：

5+6(1+2)-4=5+63-4=5+18-4=23-4=19

3.2栈的应用举例1234如何确定运算符的运算顺序？？43带括号算术表达式假设操作数是整型常数，运算符只含加、减、乘、除界限符有左右括号和表达式起始、结束符“＃”，如：＃（7+15）*（23-28/4）＃。引入表达式起始、结束符是为了方便。算术四则运算的规则，即：(1)从左算到右；(2)先乘除，后加减；(3)先括号内，后括号外。

44

运算符和界限符统称为算符，它们构成的集合命名为OP。根据上述三条运算规则，在运算过程中，任意两个前后相继出现的算符θ1和θ2之间的优先关系必为下面三种关系之一：θ1<θ2，θ1的优先权低于θ2θ1=θ2，θ1的优先权等于θ2θ1>θ2，θ1的优先权高于θ2

45算符之间的优先关系

46算符优先算法需要两个工作栈：存放算符的optr；存放操作数或中间结果的opnd。算法的基本思想：1、初始化操作数栈opnd和运算符栈optr，并将表达式起始符“＃”压入运算符栈optr；2、依次读入表达式中的每个字符，若是操作数则入操作数栈opnd，若是运算符，则与运算符栈optr的栈顶运算符进行优先权比较：47

(1)若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进optr栈；

(2)若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入θ，同时将操作数栈opnd出栈两次，得到两个操作数a、b，对a、b进行θ运算，将运算结果作为中间结果入opnd栈；

(3)若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，将栈顶运算符（左括号）退栈。483.2栈的应用举例5算符优先算法

从左向右扫描表达式：

遇操作数——保存；遇运算符号cj——与前面的刚扫描过的运算符ci比较

若ci<cj则保存cj，（因此已保存的运算符的优先关系为c1<c2<c3<c4。。）

若ci>cj

则说明ci是已扫描的运算符中优先级最高者，可进行运算；

若ci=cj则ci为“（”，cj为“）”，说明括号内的式子已计算完，需要消去括号；5+4(1+2)-6后面也许有优先级更高的算符用两个栈分别保存扫描过程中遇到的操作数和运算符49表达式求值示意图：5+6(1+2)-4

topbaseOPTR栈#OPND栈topbase5toptop+top6top×top(top1top+top2toptoptoptop3toptoptoptoptop18toptoptop23top-top4toptoptoptop19toptoptop读入表达式过程：#5+6（1+2）-4#=191+2=36×3=185+18=2323-4=19503.2栈的应用举例表达式求值算法intexpress(){//OP为运算符集合。

InitStack(OPTR);Push(OPTR,‘#‘);InitStack(OPND);w=Getchar();

While(w!=‘#’||GetTop(OPTR)!=‘#’){if(!In(w,OP))//判断W是否是运算符

{Push(OPND,w);w=getchar();}//不是运算符则进栈

else51switch(Precede(GetTop(OPTR),w){case‘<‘://新输入的算符w优先级高，w进栈

Push(OPTR,w);w=getchar();break;case‘=‘://去括号并接收下一字符

Pop(OPTR，x);w=getchar();break;case‘>’://新输入的算符优先级低，取栈顶算符运算

Pop(OPTR，T);Pop(OPND，b);Pop(OPND，a);Push(OPND,Operate(a,T,b));break;}//switch}//whilereturnGetTop(OPND);}523.3栈与递归

栈非常重要的一个应用是用来实现调用与递归。

533.3栈与递归一般函数的调用机制

A(){…B();…}C(){……}B(){…C();…}调用调用返回返回函数调用顺序ABC函数返回顺序CBA后调用的函数先返回

函数调用机制可通过栈来实现计算机正是利用栈来实现函数的调用和返回的543.3栈与递归

1．什么是递归在数学和程序设计等许多领域中都用到了递归。递归定义：一个用自己定义自己的概念,称为递归。例

n!=1*2*3*4*(n-1)*nn!递归定义n!=1当n=1时

n!=n(n-1)!当n>1时用(n-1)!定义n!553.3栈与递归2递归函数：如果一个函数在其定义体内直接调用自己，则称为直接递归函数；如果一个函数通过其它函数间接调用自己，则称其为间接递归函数。

A（

）{

…

A();

…}B(){C(){……

C();B();……}}A直接调用自己B间接调用自己563.3栈与递归3．递归算法的编写1）将问题用递归的方式定义（包括两项：终止项、递归项）2）根据问题的递归定义编写递归算法

终止项：递归终止时问题的求解；递归项：问题分解为与原问题性质相同，但规模较小的问题；例

n!的递归定义： 终止项：n!=1当n=1

递归项：n!=n(n-1)!

当n>1用(n-1)!定义n!573.3栈与递归例n!的递归算法intfact(intn){//求解并返回n的阶乘

if（n=1）return（1）；

elsereturn（n*fact(n-1)）；}58

很多数学函数是递归定义的，如二阶Fibonacci数列：

59斐波那契数列的递归算法Fib(n)：

Fib(intn){if（n==0||n==1）returnn;//递归出口

elsereturnFib(n-1)+Fib(n-2);//递归调用

}6061递归调用过程的实现递归调用时系统需要做三件事：

(1)将所有的实在参数、返回地址等信息传递给被调用函数保存；

(2)为被调用函数的局部变量分配存储空间；

(3)将程序转移到被调函数的入口。

62从被调用函数返回调用函数之前，系统也完成三件工作：

(1)保存被调函数的计算结果；

(2)释放被调函数所占空间；

(3)依照被调函数保存的返回地址，将控制转移回调用函数。63

例：n阶Hanoi塔问题：设有三个分别命名为X、Y和Z的塔座，在塔座X上插有n个直径大小各不相同、依小到大编号为1，2,…，n的圆盘。现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排。圆盘移动时必须遵循下列原则：

(1)每次只能移动一个圆盘；

(2)圆盘可以插在X、Y和Z中的任何一个塔座上；

(3)任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。XYZ12364

如何实现移动圆盘的操作呢？当n=1时，将编号为1的圆盘从塔座X直接移动到塔座Z上。当n>1时，需利用塔座Y辅助，（1）将上面n-1个圆盘从塔座X(依照上述原则)移至塔座Y上，（2）将编号为n的圆盘从塔座X移至塔座Z上，（3）将塔座Y上的n-1个圆盘(依照上述原则)移至塔座Z上。而将n-1个圆盘从一个塔座移至另一个塔座问题是和原问题具有相同特征属性的问题，只是问题的规模小1，可以用同样方法求解。65voidhanoi(intn,charx,chary,charz)//将塔座x上按直径由小到大且至上而下编号为1至n//的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1{2if(n==1)3move(x,1,z);//将编号为１的圆盘从x移到z4else{5hanoi(n-1,x,z,y);//将x上编号为１至n-1的

//圆盘移到y,z作辅助塔6move(x,n,z);//将编号为n的圆盘从x移到z7hanoi(n-1,y,x,z);//将y上编号为１至n-1的

//圆盘移到z,x作辅助塔8}9}66xyzxyzxyzxyzhanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);67递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0,3,a,b,cabc主函数：执行调用语句hanoi(3,a,b,c)，入栈。层1：执行1,2,4,5语句，产生向下调用，进层2。68递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0,3,a,b,cabc6,2,a,c,b层2

入栈，记录层1的返回地址6等信息；执行2层的1,2,4,5语句，执行到语句５再向下调用，进入层3。69递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0,3,a,b,cabc6,2,a,c,b6,1,a,b,c层3

入栈，记录层2的返回地址6等信息；执行1,2,3,9语句，过程执行完。70层２第３层调用结束，出栈，返回第2层；从第2层的断点语句６执行；执行到语句７，又开始向下递归调用到第3层。递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0,3,a,b,cabc6,2,a,c,b6,1,a,b,c71层3

入栈,记录层2的返回地址8等信息；执行语句1,2,3,9,过程执行完。出栈，返回第2层断点语句8。递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0,3,a,b,cabc6,2,a,c,b8,1,c,a,b72层２从第3层返回后，从断点８开始执行，执行语句8,9，过程执行完，出栈，返回第1层。层１从第2层返回后，从断点６开始执行；执行到语句７，又开始向下递归调用到层2，入栈，记录第1层的返回地址8等信息。递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0,3,a,b,cabc6,2,a,c,b8,2,b,a,c73层２执行到语句５，向下递归调用。层３执行语句１,2,3,9，结束，返回第2层。递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0,3,a,b,cabc8,2,b,a,c6,1,b,c,a74层２从断点语句6开始执行，执行到语句7，向下递归调用，到层3。递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0,3,a,b,cabc8,2,b,a,c6,1,b,c,a75层３执行语句１,2,3,9，结束，返回第2层。层２从第3层返回后，从断点８开始执行，过程执行完，返回第1层。层1

从第2层返回后，从断点８开始执行，过程执行完，返回主函数。递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0,3,a,b,cabc8,2,b,a,c8,1,a,b,c76Hanoi塔的递归函数运行示意图

77三个盘子搬动时hanoi(3,A,B,C)递归调用过程：hanoi(2,A,C,B):hanoi(1,A,B,C)move(A->C)1号搬到Cmove(A->B) 2号搬到Bhanoi(1,C,A,B)move(C->B)1号搬到Bmove(A->C) 3号搬到Chanoi(2,B,A,C):hanoi(1,B,C,A)move(B->A) 1号搬到Amove(B->C)2号搬到Chanoi(1,A,B,C)move(A->C) 1号搬到C78

递归算法的特点：

(1)递归算法是一种分而治之、把复杂问题分解为简单问题的求解问题方法，对求解某些复杂问题，递归算法的分析方法是非常有效的。（2）递归算法的时间效率、空间效率较低，因为递归执行时需要系统提供隐式栈实现递归。

79

小结

1设计递归算法的方法：

(1)寻找方法，将问题化为原问题的子问题求解（例n!=n*(n-1)!）。

(2)设计递归出口，确定递归终止条件

(例当n=1时，n!=1)。

2调用三件事：传递本层参数、返回地址； 分配局部变量空间;控制转移。 调用结束三件事：恢复上层；传递结果； 转断点执行。

3.3栈与递归80

3.4队列3.4

.1队列的概念3.4

.2队列的链式存储和实现3.4

.3循环队列

——队列的顺序存储和实现813．4队列3.4.1队列的概念一什么是队列队列是限定仅能在表头进行删除，表尾进行插入的线性表（a1,a2,...,ai-1,ai,ai+1,…,an

）插入删除823．4队列

a1a2a3

an入队列队头队尾出队列队列的示意图队列的特点先进先出第一个入队的元素在队头，

最后一个入队的元素在队尾，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素833．4队列

队列的基本操作1）初始化操作

2）销毁操作

3）置空操作4）判空操作5）取队头元素操作

6）入队操作

7）出队操作843.4.3链队列——队列的链式存储结构和实现队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。3.4队列rearfront∧…∧frontrear

853.4队列二链队列的类型定义typedef

structQNode{QElemTypedata;

structQNode*next;}Qnode,*QueuePtr;Typedefstruct{QueuePtrfront;//队头指针

QueuePtrrear;//队尾指针}LinkQueue;86链队列图示

非空队rearfronta1an∧

…a2QrearfrontQa1∧

rearfrontQ

∧

空队

只有一个元素结点

头尾指针封装在一起的链队873.4队列入队算法StatusEnQueue(Queue&Q,ElemTypee)

{

//

在当前队列的尾元素之后，插入元素e为新的队列尾元素

p=(QueuePtr)malloc(sizeof(Qnode));

if(!p)exit(OVERFLOW);

//

存储分配失败

p->data=e;

p->next=NULL;

Q.rear->next=p;

//

修改尾结点的指针

Q.rear=p;

//

移动队尾指针

returnOK;

}

pa2an∧rear∧reara1efront883.4队列出队算法

boolDeQueue(Queue&Q,ElemType&e)

{

//若队列不空，则删除当前队列Q中的头元素，用e返回其值，并返回OK；否则返回ERROR

if(Q.front==Q.rear)

//

链队列中只有一个头结点

returnERROR;

p=Q.front->next;

e=p->data;

//

返回被删元素

Q.front->next=p->next;

//

修改头结点指针

if(Q.rear==p)Q.rear=Q.front;//队列中只有一个元素

free(p);

//

释放被删结点

returnOK;

}fronta1a2an∧rearp893．4队列顺序队列类型定义#defineMAXQSIZE100//最大队列长度

typedefstruct{QElemType*base;//初始化的动态分配存储空间

intfront;//头指针，若队列不空，指向队列头元素

intrear;//尾指针，若队列不空，指向队列尾元素的下一个位置}SqQueue90rearfrontJ2(c)J1出队（a)空队列rearfront0123453.4队列front,rear为整数

又有J7入队,怎么办？

？rearfrontJ1(b)J1,J2相继入队列J2(d)J3,J4,J5和J6相继入队之后,J2出队rearfrontJ5J4J3J6913.4队列3.循环队列frontrearJ6J4J5312405rear540312frontJ6J7J8J9J4J5frontrear540312(b)队空(a)队满队空、队满都是front=rear如何判断循环队列队空、队满？

？J7rear923.4队列判分队空、队满有两种方法：

1）另设一个标志位以区分队空、队满。

2）少用一个存储单元，队满条件： front=rear+1;队空：front=rear队列中元素的个数？（rear–front+MAXQSIZE

）%MAXQSIZEfront540312J6J7J8J4J5（c）rear933.4队列循环队列的基本操作算法

frontrear540312建一个空队列QStatusInitQueue(SqQueue&Q){Q.base=(QElemType*)malloc(sizeof(QElemType)*MAXSIZE);if(!Q.base)return(OVERFLOW);Q.front=Q.rear=0;returnOK;}//InitQueue943.4队列入队操作

：将元素x插入队尾

frontrear540312J1J3J2xfront540312J1J3J2队列满元素x入队后StatusEnQueue(SqQueue&Q,QelemTypee){if((Q.rear+1)%MAXSIZE==Q.front)return(ERROR);Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;returnOK;}//EnQueueJ4J5rear953.4队列入队操作

：将元素x插入队尾

frontrear540312J1J3J2xfrontrear540312J1J3J2元素x入队前元素x入队后StatusEnQueue(SqQueue&Q,QelemTypee){if((Q.rear+1)%MAXSIZE==Q.front)return(ERROR);Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;returnOK;}//EnQueue963.4队列出队操作

：删除队头元素；

frontrear540312J1J3J2出队操作前frontrear540312J1J3J2出队操作后StatusDeQueue(SqQueue&Q,Qe