第三章 栈和队列课件

§3.1栈----线性表应用例一

§3.1.1栈的ADT定义

§3.1.2栈的表示和实现

§3.2栈的应用举例

1.数制转换2.括号匹配的检验

3.行编辑4.算术表达式求值

§3.3栈与递归的实现

§3.4队列----线性表应用例二

§3.4.1队的ADT定义

§3.4.2链队

§3.4.3循环队

第三章栈和队列

要点栈—递归，队，运算实现

栈和队列是在软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同。其特点在于运算受到了限制：栈按“后进先出”的规则进行操作，队按“先进先出”的规则进行操作，故称运算受限制的线性表。总述从数据结构的角度看:它们和线性表相同从数据类型的角度看:它们和线性表不同

插入删除线性表Insert(L,i,x)Delete(L,i)

(1<=i<=n+1)(1<=i<=n)

栈Insert(S,n+1,x)Delete(S,n)队列Insert(Q,n+1,x)Delete(Q,1)§3.1.1栈的ADT定义

解决某种问题特别好用【定义】是限定仅在表尾进行插入或删除操作的线性表

栈----线性表应用例一

定义仅是在线性表上规定了操作点操作受限的﹑线性的后进先出线性表

LIFO

允许插入、删除的这一端称为栈顶top

另一个固定端称为栈底bottom。

当表中没有元素时称为空栈§3.1栈Top

〖例1〗3个元素，其入栈次序为A,B,C，有多少种可能的出栈序列？〖例2〗

5个元素，其入栈次序为A,B,C,D,E，在各种可能的出栈序列中，第一个出栈元素为C且第二个出栈为D的出栈序列中有哪几种？

a1

a2a3a4a5

a6a6a5a6a5base

Top

To

其它没有，因为仅在线性表的一头操作，运算少了许多。⑴栈初始化InitStack(&s)

栈S不存在,构造一个空栈⑵销毁栈DstoryStack(&s)栈S存在,将S销毁(3)清为空栈ClearStack(&s)

栈S存在,将S清空⑷判栈空StackEmpty(s)

栈S已存在,若S为空栈返回TRUE

否则返回FALSE(5)求栈长Stacklength(s)

栈S存在,返回S的元素个数(6)读栈顶元素GeTop(s,&e)栈S存在且非空,返回栈顶元素e(7)入栈Push(&s,e)

栈S已存在,在S顶部插入新栈元e(8)出栈Pop(&s,&e)

栈S存在且非空,删除栈S顶元,

用e返回其值(9)遍历栈StackTraverse(s,visit())依次对栈调用visit()§3.1栈对于栈，常做的基本运算有9个P45一、栈的顺序存储结构

P46

由于栈是运算受限的线性表，因此线性表的存储结构对栈也是适用的，只是操作点不同而已。#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{SElemType*base;

SElemType*top;intstacksize；}sqstack;

说明

top指向栈顶元素的下一个位置，即待接收数据的位置

top=base空栈

top=base+stacksize栈满补添存储补10top

base

初始100

§3.1.2栈的表示和实现IO顺序栈约定与类型定义：top的含义#defineSTACK_INIT_SIZE100//存储空间的初始分配量typedefstruct{ ElemType base[STACK_INIT_SIZE100]; //栈底指针

int top; //栈顶指针(栈顶元素的下一个位置) }SqStack;base空栈a进栈b进栈atopbasetopbasetopabbasee进栈f进栈溢出e出栈edcbatopbasetopbasetopedcbadcba约定：top指向栈顶元素的下一个位置一、栈的顺序存储结构

P46顺序栈的初始化首先建立栈空间，然后初始化栈顶指针。§3.1.2栈的表示和实现statusInitStack(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;returnOk;}//

InitStack顺序栈的取栈顶元

statusGetTop(SqStacks,SElemType&e){if(s.top==s.base)returnERROR;e=*(S.top-1);returnOk;}//

GetTop

出栈和取栈顶元，先判栈是否为空为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件顺序栈入栈statusPush(SqStack&s,SElemTypee){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;

returnOK;}//Push}

对于顺序栈，入栈时先判栈是否满了，栈满时不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。§3.1.2栈的表示和实现顺序栈出栈statusPop(SqStack&s,SElemTypee){if(s.top==s.base)returnERROR;e=*--s.top;returnOK;}//Pop顺序栈判空

statusStackEmpty(SqStacks){if(s.top==s.base)return1;elsereturn0;}return(s.top==s.base)§3.1.2栈的表示和实现

用链式存储结构实现的栈称为链栈。通常链栈用单链表表示，其结点结构与单链表的结构相同二、链式栈存储结构

P47

单链表仅在一端操作。

§3.1.2栈的表示和实现【说明】top为栈顶指针：LinkStacktop;

typedefstructNode{elemtypedata;

structNode*next;}StackNode,*LinkStack;∧top

因为栈中的主要运算是在栈顶插入、删除，显然在链表的头部做栈顶是最方便的，而且没有必要象单链表那样为了运算方便附加一个头结点。voidpush(LinkStack&top,elemtypee){p=((LinkStack)malloc(sizeof(StackNode));p->data=e;p->next=top;top=p;}voidpop(LinkStack&top,elemtype&e){if(top!=NULL){e=top->data;q=top;top=top->next;free(q);}elseprintf(“error”);}voidinit(LinkStack&top){top=NULL;}§3.2栈的应用举例§3.2.1数制转换

P48

“十”

“八”

N=(Ndivd)×d+Nmodd

除留取余

N十进制d其他进制所转换的8进制数按低位到高位的顺序产生而通常的输出是从高位到低位的，恰与计算过程相反转换过程中每得到一位8进制数则进栈保存转换完毕后依次出栈则正好是转换结果。〖例〗数制转换问题将十进制数N转换为d进制的数，其转换方法利用辗转相除法：以N=1248，d=8为例转换方法如下：

NN/8（整除）N%8（求余）

13481684低

1682102125202高算法思想当N>0时重复1）、2）1）若N≠0，则将N%d压入栈s中，执行2）；若N=0，将栈s的内容依次出栈，算法结束。2）用N/d代替N（1348）10=（2504）8初学者往往将栈视为一个很复杂的东西，不知道如何使用，通过这个例子可以消除栈的“神秘”，当应用程序中需要一个与数据保存时相反顺序使用数据时，就要想到栈。通常用顺序栈较多，因为很便利。#defineL10;voidconversion(intN,intd){ints[L],top;/*定义一个顺序栈*/intx;top=0;/*初始化栈*/while(N){s[top++]=N%d;/*余数入栈*/N=N/d;//商作为被除数继续

}while(top!=0){x=s[--top];printf(“%d”,x);}}

算法bvoidconversion(intN,intd){SqStacks;intx;

InitStack(&s);while(N){Push(s,N%d);N=N/d;}while(!StackEmpty(s)){Pop(s,x);

printf(“%d”,x);}}

算法a算法a将对栈的操作抽象为模块调用使问题的层次更加清楚。算法b直接用int数组S和int变量top作为一个栈来使用§3.2.2括号匹配的检验P49§3.2栈的应用举例

假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（［］（））或［（［

］［

］）］等为正确的格式，［（

］）或（［（

））或

(()])均为不正确的格式。检验括号是否匹配的方法可用"期待的急迫程度"这个概念来描述。例如考虑下列括号序列：

[([][])]12345678分析可能出现的不匹配的情况:到来的右括弧非是所“期待”的;到来的是“不速之客”;(右括号多)直到结束，也没有到来所“期待”的。（左括号多）§3.2.2括号匹配的检验算法的设计思想：1）凡出现左括号，则进栈2）凡出现右括号，首先检查栈是否空若栈空，则表明“右括号”多了否则和栈顶元素比较，若相匹配，则“左括号出栈”否则不匹配3）表达式检查结束时，若栈空，则匹配正确否则表明“左括号”多了§3.2栈的应用举例status

matching(string&exp){

//检验表达式中所含括弧是否正确嵌套，若是，则返回

//OK，否则返回ERROR

intstate=1,i=1;while(i<=length(exp)&&state){swithofexp[i]{case左括弧:{Push(S,exp[i]);i++;break;}case")":{if(NOTStackEmpty(S)&&GetTop(S)="("){Pop(S,e);i++;}else{state=0}break;}……}}if(state&&StackEmpty(S))returnOKelsereturnERROR;}算法正确执行后，工作栈应是空的。kcats

§3.2.3行编辑程序P49§3.2栈的应用举例#

清前一字符/退一格\n

行结束@

清一句/退行eof

文件结束stack

ats

ydustudy…

设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。whli##ilr#e（s#*s)outcha@putchar(*s=#++);while(*s)putchar(*s++);算法思想：引入栈，保存终端输入的一行字符（逐行处理）；

遇‘#’退一格——出栈一次

遇‘@’退一行——清栈步骤：1）初始化栈S

2）读入字符ch

3）ch!=EOF3.1)ch!=EOF&&ch!=’\n’3.1.1）ch为‘#’：Pop(S,c),转3.1.4)

3.1.2）ch为‘@’：ClearStack(S),转3.1.4)

3.1.3）ch为其他：Push(S,ch),转3.1.4)

3.1.4）再读入字符ch，继续3.1)3.2)处理完一行，清空栈

3.3)如ch!=EOF，读入字符ch，继续3)§3.2.3行编辑程序P49§3.2栈的应用举例voidLineEdit(){//利用字符栈S，从终端接收一行并传送至调用过程的数据区。

InitStack(S);//构造空栈Sch=getchar();//从终端接收第一个字符

while(ch!=EOF){//EOF为全文结束符

while(ch!=EOF&&ch!='\n'){

switch(ch){case'#':Pop(S,c);break;//仅当栈非空时退栈

case'@':ClearStack(S);break;//重置S为空栈

default:Push(S,ch);break;//有效字符进栈，未考虑栈满情形

}ch=getchar();//从终端接收下一个字符

}§3.2.3

行编辑程序P50

将从栈底到栈顶的字符传送至调用过程的数据区；

ClearStack(S);//重置S为空栈

if(ch!=EOF)ch=getchar();}DestroyStack(S);}§3.2.3

行编辑程序P50§3.2栈的应用举例§3.2.5算术表达式求值

P52限于二元运算符的表达式定义:表达式::=(操作数)+(运算符)+(操作数)操作数::=简单变量|表达式简单变量::=标识符|无符号整数在计算机中，表达式可以有三种不同的标识方法设Exp=S1+OP+S2OP+S1+S2前缀表示法

S1+OP+S2中缀表示法

S1+S2+OP

后缀表示法

（以运算符所在不同位置命名）例如：Exp＝a*b

+

(c-d/e)*f前缀式（波兰式）：

+*ab

*-c/def

中缀式：

a*b+

c–d/e*f后缀式（逆波兰式）：ab*cde/-f*

+

1.操作数之间的相对次序不变;2.运算符的相对次序不同;3.中缀式丢失了括弧信息，致使运算的次序不确定;4.前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;5.后缀式的运算规则为:

运算符在式中出现的顺序恰为表达式的运算顺序;

每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式结论:§3.2.5算术表达式求值后缀表达式求值步骤：1、读入表达式一个字符2、若是操作数，压入栈，转43、若是运算符，从栈中弹出2个数，将运算结果再压入栈4、若表达式输入完毕，栈顶即表达式值；若表达式未输入完，转1top4top43top435top〖例〗

计算4+3*5后缀表达式：435*+top415top19§3.2.5算术表达式求值设立运算符栈和操作数栈;设表达式的结束符为“#”,予设运算符栈的栈底为“#”若当前字符是操作数，则进操作数栈;若当前运算符的优先数高于栈顶运算符，则进栈;

否则，退出栈顶运算符作相应运算。中缀表达式求值步骤：§3.2.5算术表达式求值算法思想引入OPTR和OPND两个栈初始：OPTR有一个元素'#'，OPND为空读入一字符cc=='#‘&&GetTop(OPTR)=‘#’

：return(GetTop(OPND))c非运算符：Push(OPND,c)c是运算符：t=GetTop(OPTR)，比较t和c的优先关系

t<c：Push(OPTR,c) t==c：Pop(OPTR,x) t>c：Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a); x=Operate(a,theta,b);Push(OPND,x);继续读入字符处理。§3.2.5算术表达式求值OperandTypeEvaluateExpression(){//算术表达式求值的算符优先算法。设OPTR和OPND//分别为运算符栈和运算数栈，OP为运算符集合。

InitStack(OPTR);

Push(OPTR,'#');InitStack(OPND);c=getchar();

while(c!='#'||GetTop(OPTR)!='#'){

if(!In(c,OP)){Push((OPND,c);c=getchar();}//不是运算符则进栈

else……..}//while

returnGetTop(OPND)}//EvaluateExpression§3.2.5算术表达式求值

P53switch(precede(GetTop(OPTR),c){

case'<'://栈顶元素优先权低

Push(OPTR,c);c=getchar();break;

case'='://脱括号并接收下一字符

Pop(OPTR,x);c=getchar();break;case'>'//退栈并将运算结果入栈

Pop(OPTR,theta); Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));

break;}//switch§3.2.5算术表达式求值

P53〖例〗

计算2+4-3*6操作数运算符24+操作数运算符6-操作数运算符6-36*操作数运算符6-18操作数运算符-12§3.2.5算术表达式求值

递归:自己××自己，如（定义、调用）

递归的对象：一个对象部分地包含它自己，或用它自己给自己定义。如某些数据结构的定义

〖例〗线性表的另一种定义:若元素个数为0，则称为空表若元素个数大于0，则有且仅有一个第一个元素(即表头)，剩余元素形成一个表(即表尾)。§3.3栈与递归的实现

递归的过程：一个过程直接或间接地调用自己

〖例〗f(n)=n!=f(n-1)*n

递归的应用递归定义：如阶乘、Fibonacci数列等数据结构：如表、树、二叉树等问题求解：如Hanoi塔定义是递归的§3.3栈与递归的实现longfact(longn){

if(n==0)return1; //递归结束条件

else

returnn*fact(n-1); //递归的规则}过程的嵌套调用r主程序srrrs子过程1rst子过程2rst子过程3§3.3栈与递归的实现主程序

main():fact(4) 参数传递递归调用结果返回回归求值fact(4): fact(3): fact(2):fact(1): fact(0): 1直接定值为1计算4*fact(3)计算3*fact(2)计算2*fact(1)计算1*fact(0)12624§3.3栈与递归的实现数据结构是递归的--表空表非空表:(表头元素+除表头元素以外的剩余元素)查找表L中是否有元素值e§3.3栈与递归的实现LinkListsearch(LinkListL,ElemTypee)//L为不带头结点的单向非循环链表{

if(L==NULL)returnNULL;

else

if(L->data==e)returnL;

elsereturnsearch(L->next,e);}voidhanoi(intn,chara,charb,charc)

n-圆盘数 a-源塔座

b-中介塔座c-目标塔座搬动方法n=1,a->cn>1:

hanoi(n-1,a,c,b)

a->c

hanoi(n-1,b,a,c)注意

用递归调用的结果，

不关注该结果如何

获得的细节§3.3栈与递归的实现问题求解是递归的—Hanoi塔§3.3栈与递归的实现当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事:将所有的实在参数、返回地址等信息传递给被调用函数保存;（现场保护）为被调用函数的局部变量分配存储区;将控制转移到被调用函数的入口。

从被调用函数返回调用函数之前，应该完成:保存被调函数的计算结果;释放被调函数的数据区;依照被调函数保存的返回地址将控制转移到调用函数。（现场恢复）多个函数嵌套调用的规则是:后调用先返回此时的内存管理实行“栈式管理”递归过程指向过程中占用的数据区，称之为递归工作栈每一层的递归参数合成一个记录，称之为递归工作记录栈顶记录指示当前层的执行情况，称之为当前活动记录栈顶指针，称之为当前环境指针〖例〗Hanoi

递归工作栈保存内容：形参n,x,y,z和返回地址

返回地址用行编号表示nxyz返回地址§3.3栈与递归的实现main(){intm;printf("Inputnumberofdisks”);scanf("%d",&m);printf(”Steps:%3ddisks”,m);hanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(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)}ABC1233ABC03ABC02ACB63ABC02ACB61ABC6ABC3ABC02ACB6main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(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)}ABC3ABC02ACB61CAB8ABC3ABC02ACB63ABC03ABC02ACB6main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(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)}ABC3ABC02BAC83ABC02BAC81BCA6ABC3ABC02BAC83ABC0main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(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)}ABC3ABC02BAC81ABC8ABC3ABC02BAC83ABC0栈空3ABC02BAC83.4.1队列的定义及基本运算P58栈是一种后进先出LIFO的数据结构，而在实际问题中还经常使用一种“先进先出”

(FIFO--FirstInFirstOut)的数据结构：即插入在表一端进行，而删除在表的另一端进行，我们将这种数据结构称为队或队列，把允许插入的一端叫队尾(rear)

，把允许删除的一端叫队头(front)。〖例〗

买火车票；排队；过船闸…§3.4队列a1a2a3a4a5

入队出队

排头走掉，新来的排在队尾rearfront栈与队列的概念运用问题2：设栈S和队列Q的初态均为空，将元素1,2,3,4,5,6依次入栈S，一元素出栈后即进入队列Q，若这6个元素出队次序是4,6,5,3,2,1，则栈S至少应能容纳多少个元素？

654321123564123456答案：5在队列上进行的基本操作有P59⑴队初始化InitQueue(&Q)队Q不存在,构造一个空队Q⑵销毁队DestoryQueue(&Q)队Q存在,将Q销毁(3)清为空队ClearQueue(&Q)队Q存在,将Q清空⑷判队空QueueEmpty(Q)队Q已存在,若Q为空队返回

TRUE否则返回FALSE(5)求队长Queuelength(Q)队Q存在,返回Q的元素个数(6)取队首元GeTHead(Q,&e)队Q存在且非空,返回队首元素e(7)入队EnQueue(&Q,e)Q已存在,在Q尾部插入新队元x(8)出队DeQueue(&Q,&e)队Q存在且非空,删除队Q首元,

用e返回其值(9)遍历队QueueTraverse(Q,visit())依次对队调用visit()§3.4队列队的ADT定义a2a3a4a1a1a1a2

a2

栈结构只须记住顶元位置，不必记住栈底位置，

队结构既要记队首，又要记队尾。双端队列（两端均可入、出），受限队列：

一头可插删；另一头仅可插。

注意空队问题栈顶=底必空队f=r

必空?§3.4队列§3.4.2链队P61链式存储的队称为链队。用单链表来实现链队，设一个头指针和尾指针。typedefstructQNode{QElemTypedata;

structQNode*next;}QNode,

*Queueptr;∥链队结点的类型typedefstruct{Queueptrfront；∥队头指针

Queueptrrear；∥队尾指针

}LinkQueue;∥将头尾指针封装在一起的链队datanexttopa1a2an^Q.frontQ.rearfrontrearx入队^xfrontreary入队x^yfrontreary出队xfrontrear空队^frontrearx出队^§3.4.2链队§3.4队列队头指针：Q.front队尾指针：Q.rear创建一个带头结点的空队列StatusInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;returnQ;}

∧

空队Q.front=Q.rear§3.4队列入队出队StatusEnqueue(LinkQueue&Q,QElemTypee){

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

if(!p)exit(OVERFLOW);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;

returnOK;}StatusDequeue(LinkQueue&Q,QElemType&e){

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;/*只有1元素时出队后队空，

free(p);/*此时还要修改队尾指针

returnOK;}顺序队的类型定义§3.4队列顺序队

队头指针指向队头元素

队尾指针指向队尾元素的下一个位置#defineMAXSIZE100/*队列的最大容量*/typedefstruct{QElemType*base;

intrear,front;/*队头队尾指针*/}SeQueue;*base[MAXSIZE];/*队元的存储空间*/

顺序队列的数据区为Q.base[0]~Q.base[MAXSIZE-1]§3.4.3顺序队P63队中元素的个数

m=(Q.rear-Q.front)队满时m=MAXSIZE；队空时m=0顺序队的入队、出队§3.4队列

在不考虑溢出的情况下，入队操作队尾指针加1，指向新位置后，元素入队。

Q.base[Q.rear]=x;/*原队尾元素置入x*/Q.rear++;

在不考虑队空的情况下，出队操作队头指针加1，表明队头元素出队。

x=Q.base[Q.front];Q.front++;“假溢出”问题队尾指针已经移到了最后,再有元素入队就会出现溢出，而事实上此时队中并未真的“满员”。

这是由于“队尾入队头出”这种受限制的操作所造成的。解决假溢出的方法之一是将队列的数据区base[0..MAXSIZE-1]看成头尾相接的循环结构，头尾指针的关系不变，称其为“循环队列”front=5rear=8(c)一般情况9876543210rearrearrearfrontrearfrontfrontfronta3a2a1a6a10a9a8a7a6

?a6a5a4a8a7rearfrontfront=rear=0(a)空队front=5rear=10(d)假溢出现象front=5rear=6(b)变化情况§3.4队列§3.4队列循环队列

基本思想：把队列设想成环形，让Q[0]接在Q[M-1]之后，

若

rear+1==M,则令rear=0;

实现：利用“模”运算

〖例〗10MOD7=3

入队：Q[rear]=x;rear=(rear+1)%M;

出队：x=Q[front];

front=(front+1)%M;

队满、队空判定条件循环队列约定：Q.front和Q.rear(队尾的下一个)的含义队空：Q.front==Q.rear队满：Q.front==Q.rear01723456Q.frontQ.rear01723456Q.frontQ.reara1a2a3a4a5如何区分队空和队满？01723456Q.frontQ.reara1a2a3a4a5a6a7a8§3.4队列循环队列

区分队空和队满的方法设标志位(上次的更新动作)：0-创建/删除，1-插入引入队列长度少用一个元素空间：

队空：front==rear

队满：(rear+1)%M==front01723456Q.frontQ.rear01723456Q.frontQ.reara1a2a3a4a5a6a7有维护的代价§3.4队列#defineMAXSIZE50/*队列的最大长度*/typedefstr