《数据结构》课件1第3章 栈与队列

3.1栈的类型定义3.3栈的应用举例3.2栈类型的实现3.4队列的类型定义3.5队列类型的实现总目录知识点：重点：难点：2、在顺序栈、循环队列上基本操作的实现。1、栈与队列的特点；栈的应用顺序栈、链栈、循环队列、链队列

通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。

线性表栈队列Insert(L,

i,x)

Insert(S,

n+1,x)Insert(Q,

n+1,x)

1≤i≤n+1

Delete(L,

i)Delete(S,

n)Delete(Q,

1)

1≤i≤n

栈和队列是两种操作受限的线性表，是两种常用的数据类型1.栈是限制仅在表尾进行插入和删除操作的特

殊线性表，限制操作的表尾端称为“栈顶”,

另一端称为“栈底”3.1

栈的类型定义一、栈的逻辑结构定义及特性2.栈是“后进先出”的线性表（LIFO）或“先进后出”的线性表（FILO）a1a2a3…an栈底栈顶进出

如下图所示的铁路调度站形象地表示栈的“后进先出”特点。

思考题：

设有编号为1，2，3，4的四辆列车，顺序进一个栈式结构的站台，具体写出这四辆列车开出车站的所有可能的顺序。解答：四辆车出站的所有可能顺序为：1）1、2、3、4；2）1、2、4、33）1、3、2、4；4）1、3、4、25）1、4、3、2；6）2、1、3、47）2、1、4、3；8）2、3、4、19）2、3、1、4；10）2、4、3、111）3、2、1、4；12）3、2、4、113）3、4、2、1；14）4、3、2、1ADTStack

{

数据对象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

数据关系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

约定an

端为栈顶，a1端为栈底。基本操作：

}ADTStack二、栈的抽象数据类型定义1、构造空栈操作：DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())2、判栈空操作：InitStack(&S)3、取栈顶元素操作：4、进栈（插入）操作：5、出栈（删除）操作：6、置栈空操作：7、求栈中元素个数操作：8、栈销毁操作：9、栈遍历操作：最常用的操作

GetTop(S,&e)

初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。a1a2an……Push(&S,e)

初始条件：栈S已存在。

操作结果：插入元素e为新的栈顶元素。

a1a2ane……Pop(&S,&e)

初始条件：栈S已存在且非空。

操作结果：删除S的栈顶元素，并用e返回其值。a1a2anan-1

……顺序栈链栈3.2

栈类型的实现//-----栈的顺序存储表示

-----

#defineSTACK_INIT_SIZE100;//存储空间初始分配量

#defineSTACKINCREMENT10;//存储空间分配增量

typedefstruct{

SElemType

*base;//栈底指针

SElemType

*top;//栈顶指针

intstacksize;

}

SqStack;SqStacks;

类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。一.顺序栈栈空条件：栈满条件：

s.tops.base空栈DCBAs.tops.base当stacksize=4时是满栈s.top=s.base

s.top-s.base=s.stacksize二.顺序栈基本操作的实现1.构造一个空栈操作：InitStack(&S)：操作思路：1）用malloc标准函数分配一个适当大小的连续空间；2）使其满足空栈条件。S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType))s.top=s.base3）确定其它值s.stacksize=STACK_INIT_SIZE

StatusInitStack(SqStack&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;P47statusStackempty(SqStackS)

{

}2、判栈空操作：

StackEmpty(S)if(S.top==S.base)returnTRUE;

elsereturnFALSE;要求：若栈S为空，则返回TRUE值，否则返回

FALSE值。算法：（同学先自己做）3.压（进或入）栈操作push(&s,e)：要求：将元素e插入到栈顶，作为新的栈顶元素。操作步骤：1）若栈满，则追加空间,若追加成功则修正有关栈的值，若追加失败则结束操作。2）将新元素e压栈，栈顶指针后移。S.base=(SElemtype*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType))；S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMEN;*S.top++=e*S.top=e;S.top=s.top+1;a1a2ane……

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;}//if*S.top++=e;returnOK;P474.退（出）栈操作pop(&S,&e)：要求：将栈顶元素删除，并用e保留其值。操作步骤：1）若栈空，则结束操作。2)若栈不空，则删除栈顶元素，并用e返回其值If(S.top=S.base)returnERRORe=*--S.tops.top=s.top-1;e=*s.top;a1a2an……an-1es.topStatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，

//用e返回其值，并返回OK；

//否则返回ERROR}if

(S.top

==

S.base)

returnERROR;e=*--S.top;

returnOK;P475.取栈顶元素操作GetTop(S,&e)：要求：读取栈顶元素并用e保留其值。操作步骤：1）若栈空，则结束操作。2)否则读取栈顶元素，并用e返回其值If(S.top==S.base)returnERRORe=*（S.top-1）a1a2an……an-1s.topeanStatusGetTop(SqStackS,SElemType&e){//若栈不空，则删除S的栈顶元素，

//用e返回其值，并返回OK；

//否则返回ERROR}if

(S.top

==

S.base)

returnERROR;

e=*(S.top-1);

returnOK;P47

栈的链式存储结构称为链栈，是运算受限的单链表，其插入和删除操作仅限制在链表的表头位置上进行，故链栈没有必要象单链表一样附加头结点，栈顶指针即为链表的头指针。二.链栈栈顶指针∧a1an注意:链栈中指针的方向an-1栈底

//-----栈的链式存储表示

-----

typedefstruckSNODE{SElemTypedata;structSNODE*next;}SNODE,*Linkstack;

Linkstacks;注意：若输入的数据是顺序输入a1,a2,...,an，则建链栈时一般用头插法,2.链栈的其它操作与链表的操作类似（因栈是线性表的特例）.作业11.分别写出对链栈的入栈和出栈操作的算法。

*2.P24/3.15

链栈的结点类型定义如下：TypedefstructSNODE{SElemTypedata;structSNODE*next;}SNODE，*Linkstack;1)链栈的入栈push(&top,x)的函数如下：statuspush(Linkstack&top,SElemTypex)

//在栈顶指针为top的链栈中插入一个值为x的结点{p=(node*)malloc(sizeof(node));if(p)//分配空间失败returnERROR;p->data=x;//产生一个值为x的新结点

p->next=top;top=p;//将p插入到栈顶

returnOK;}解答：2）链栈的出栈pop(&top,&e)函数如下：statuspop(Linkstack&top,SElemType&e)//将栈顶指针为top的链栈的栈顶元素出栈，并通过参数e返回{if(top==NULL)//如果栈空

returnERROR;e=top->data;//将栈顶元素值存入e中p=top;//p指向栈顶结点top=top->next;//修改指针，使栈顶结点从栈中脱离出来free(p);

//释放空间returnOK；}2、设共享栈的结构图如下：a1a2……

an…

bm……

b2b1C的元素序号12……n……….m-1m栈1底栈1顶栈2顶栈2底top1top2两栈的最多元素个数为m，假设top1是栈1的栈顶指针，top2是栈2的栈顶指针，分别指向栈顶元素注意：当top2=top1+1时，栈满；当top1=0时，栈1空；当top2=m+1时,栈2空.inttop1,top2,m,c[m+1];

//将其说明成全局变量Voidpush(x,i)Inti;elemtypex;{if(top2==top1+1)print(“overflow”);elseif(i==1)//对第一个栈进行入栈操作

{top1++;c[top1]=x;}else//对第二个栈进行入栈操作

{top2--;c[top2]=x;}}根据上述原理得到如下函数：函数pop如下：Voidpop(i)inti;{if(i==1)//对第一个栈进行出栈操作

if(top1==0)print(“栈1为空\n”）;elsetop1--;else//对第二个栈进行出栈操作

top2++;}*补充实验1：

假设一个算术表达式中只包含圆括号，编写一个判别表达式是否正确配对的函数correct(exp,tag);其中，exp为字符串类型的变量，表示被判别的表达式，tag为标志变量，标志是否正确配对。解：引进一个顺序栈S，存放未配对的括号思想：扫描到‘（‘时，则入栈;当扫描到’）’时,

检查当前栈顶元素是否是对应的‘（’,

若是则退栈，否则，若栈为空及栈顶元素不是对应的‘（’，都属不配对;当整个算术表达式检查完毕时栈为空，表示括号正确配对；否则也属不配对。实现本题功能的函数如下：#definemaxsize100

//maxsize为算术表达式中最多字符个数

typedefstruct{charelem[maxsize];inttop;}stack;correct(charexp[maxsize],intflag){stackS//定义了一个顺序栈SS.top=0,i=0;flag=1;//标识是否配对

while(exp[i]==‘\0’&&flag){if(exp[i]==‘(‘)//遇‘（’，则入栈

S.elem[top++]=exp[i];if(exp[i]==‘)’)//遇‘）’，则判断栈顶情况

if(S.top==0)flag=0;elseif(s[top-1]==‘(‘)S.top--;elseflag=0;i++;}if(S.top>0)flag=0;//若栈不空，则不配对}例一、数制转换例二、括号匹配的检验例三、行编辑程序问题例四、迷宫求解例五、表达式求值例六、实现递归3.3

栈的应用举例

NNdiv8Nmod8

13481684

168210

2125

202计算顺序输出顺序例如：（1348)10=(2504)8

，其运算过程如下：

例一、数制转换

（十进制数N到d进制数的转换）

动画播放(3-2-1)voidconversion(){InitStack(S);

scanf("%d",N);

while(N){

Push(S,N%8);//“余数”入栈

N=N/8;//“非零商”继续运算

}

while(!StackEmpty(S)){

Pop(S,e);

printf("%d",e);

}}//conversionP48/算法3.1假设在表达式中（［］（））或［（［］［］）］等为正确的格式，［（］）或（［（）]或[（）］)均为不正确的格式。则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例二、括号匹配的检验

分析可能出现的不匹配的情况:到来的右括弧并非是所“期待”的；例如：考虑下列括号序列：

[([][])]12345678到来的是“不速之客”；直到结束，也没有到来所“期待”的括弧。这三种情况对应到栈的操作即为：

1．和栈顶的左括弧不相匹配；

2．栈中并没有左括弧等在那里

3．栈中还有左括弧没有等到和它相匹配的右括弧。

算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”

，否则表明不匹配。3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。Statusmatching(string&exp){

intstate=1,i=0;

while(i<Length(exp)&&state){

switchofexp[i]{

case

左括弧:{Push(S,exp[i]);i++;break;}

case”)”:{

if(NOTStackEmpty(S)&&GetTop(S)==“(“{Pop(S,e);i++;}

else{state=0;}

break;}……}

if(StackEmpty(S)&&state)returnOK;…...如何实现？“每接受一个字符即存入存储器”?

并不恰当！例三、行编辑程序问题

设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，现假设“#”为退格符，“@”为退行符。合理的作法是：假设从终端接受了这样两行字符：

whli##ilr#e（s#*s)

outcha@putchar(*s=#++);则实际有效的是下列两行：

while(*s)

putchar(*s++);

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

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();

while(ch!=EOF){//EOF为全文结束符}将从栈底到栈顶的字符传送至调用过程的数据区；P50/算法3.2通常用的是“穷举求解”的方法例四、迷宫求解动画3-3-1动画3-3-2求迷宫路径算法的基本思想是：若当前位置“可通”，则纳入路径，并继续朝“下一位置”探索

若当前位置“不可通”，则应顺着“来的方向”退回到“前一通道块”，然后朝着除"来向"之外的其他方向继续探索；若四周“均无通路”，则将当前位置从路径中删除出去。设定当前位置的初值为入口位置；

do｛

若当前位置可通，

则｛将当前位置压入栈顶；

若该位置是出口位置，则算法结束；

否则切换当前位置的东邻方块为新的当前位置；

｝

否则{

｝｝while(栈不空）；求迷宫中一条路径的伪码算法：

…

…详见P52/算法3.2若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为:沿顺时针方向旋转

找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则｛删去栈顶位置；//从路径中删去该通道块

若栈不空，则重新测试新的栈顶位置，

直至找到一个可通的相邻块或出栈至栈空；｝若栈空，则表明迷宫没有通路。

限于二元运算符的表达式定义:

表达式::=(操作数)+(运算符)+(操作数)

操作数::=简单变量|表达式简单变量::=标识符|无符号整数例五、表达式求值

在计算机中,表达式的三种标识方法：设

Exp=S1+

OP

+S2则称

OP

+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-3-4如何从后缀式求值？先找运算符，再找操作数例如：

ab

cde/

f

+a

bd/ec-d/e(c-d/e)

f动画3-3-6如何从原表达式求得后缀式？

每个运算符的运算次序要由它之后的一个运算符来定;在后缀式中，优先数高的运算符领先于优先数低的运算符。分析“原表达式”和“后缀式”中的运算符:原表达式:a+b

c

d/e

f

后缀式:abc

+de/f

为此我们先引进一个运算符的“优先数”的概念。给每个运算符赋以一个优先数的值，如下所列：

运算符#(+-X/**

优先数-1011223

从原表达式求得后缀式的规律为：1)设立运算符栈；2)设表达式的结束符为“#”，

予设运算符栈的栈底为“#”；3)若当前字符是操作数，则直接发送给后缀式。4)若当前字符为运算符时，当其优先数高于栈顶运算符，则进栈；5)否则，退出栈顶运算符发送给后缀式；

6)遇到左括号“（”时，将其压进运算符栈；遇到右括号“）”时，当栈顶符号不是左括号时，反复将栈顶符号弹出送给后缀式。7)扫描到“#”时，将运算符栈顶符号依次弹出送给后缀表达式，直到栈顶为“#”号，转换结束。

动画3-3-7如：3*（7-2）#转换成后缀表达式372-*的过程为：步骤后缀表达式运算符栈原表达式说明

1#3*（7-2）#23*(7-2)#*>#3#*(7-2)#4#*(7-2)#537#*(-2)#->(637#*(-2)#7372#*(-)#遇）

8372-#*(#)遇(9372-#*#10372-*##结束voidtransform(charsuffix[],charexp[]){InitStack(S);Push(S,

#

);p=exp;ch=*p;

while(!StackEmpty(S)){if(!IN(ch,OP))Pass(Suffix,ch);else{}

if(ch!=

#

){p++;ch=*p;}else{Pop(S,ch);Pass(Suffix,ch);}

}//while}//CrtExptree……switch(ch){

case

(

:Push(S,ch);break;

case

)

:

Pop(S,c);

while(c!=

(

)

{Pass(Suffix,c);Pop(S,c)}

break;

defult:while(Gettop(S,c)&&(precede(c,ch)))

{Pass(Suffix,c);Pop(S,c);}

if(ch!=

#

)Push(S,ch);

break;

}

//switch例六、实现递归

在程序设计中，经常会碰到多个函数的嵌套调用。和汇编程序设计中主程序和子程序之间的链接和信息交换相类似，在高级语言编制的程序中，调用函数和被调用函数之间的链接和信息交换也是由编译程序通过栈来实施的。将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。

当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，

需先完成三项任务：保存被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。从被调用函数返回调用函数之前，应该完成下列三项任务：多个函数嵌套调用的规则是：此时的内存管理实行“栈式管理”后调用先返回！例如：voidmain(){voida(){voidb(){………a();b();……}//main}//a}//bMain的数据区函数a的数据区函数b的数据区

再看P56递归工作栈：递归过程执行过程中占用的数据区。递归工作记录：每一层的递归参数合成一个记录。当前活动记录：栈顶记录指示当前层的执行情况。当前环境指针：递归工作栈的栈顶指针。递归函数执行的过程可视为同一函数进行嵌套调用，例如：voidhanoi(intn,charx,chary,charz){//将塔座x上按直径由小到大且至上而下编号为1至n//的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1if(n==1)2move(x,1,z);//将编号为１的圆盘从x移到z3else{4hanoi(n-1,x,z,y);//将x上编号为１至n-1的

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

//圆盘移到z,x作辅助塔7}8}汉诺塔问题61bca03abc返址nxyz62acb61abcvoidhanoi(intn,charx,chary,charz)1{2if(n==1)3move(x,1,z);4else{5hanoi(n-1,x,z,y);6move(x,n,z);7hanoi(n-1,y,x,z);8}9}运行见P57-58页的图3.7

81cab

汉诺塔问题动画播放一、队列的逻辑结构定义及特性1.队列是只允许在表的一端进行插入，而在表的另一端进行删除操作的一种特殊线性表。允许插入的一端称为“队尾”，允许删除的一端称为“队头（首）”。2.队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表a1a2a3…an队首队尾入队出队3.4队列的类型定义ADTQueue{

数据对象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

数据关系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

约定其中a1

端为队列头，an

端为队列尾基本操作：}

ADTQueue二、队列的抽象数据类型定义1、构造空队列操作：DestroyQueue(&Q)ClearQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)EnQueue(&Q,e)DeQueue(&Q,&e)QueueTraverse(Q,visit())2、判队空操作：InitQueue(&Q)3、取队头元素操作：4、入队（插入）操作：5、出队（删除）操作：6、置队空操作：7、求队列长度操作：8、销毁队列操作：9、队列遍历操作：最常用的操作GetHead(Q,&e)

初始条件：Q为非空队列。

操作结果：用e返回Q的队头元素。a1a2an……eEnQueue(&Q,e)

初始条件：队列Q已存在。

操作结果：插入元素e为Q的新的队尾元素。a1a2ane……

DeQueue(&Q,&e)

初始条件：Q为非空队列。

操作结果：删除Q的队头元素，并用e返回其值。a1a2an……

链队列——链式映象顺序与循环队列

——顺序映象3.5

队列类型的实现链队列一.链队列(链式映象)的结构描述二.链队列基本操作的实现

typedefstructQNode{//结点类型

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;typedefstruct{//链队列类型

QueuePtrfront;//队头指针

QueuePtrrear;//队尾指针}LinkQueue;LinkQueueQ;一.链队列(链式映象)的结构描述a1∧an…Q.frontQ.rearQ.frontQ.rear∧空队列链队的队空条件：Q.front=Q.rear1.构造一个空队列InitQueue(&Q)：操作思路：1）用malloc标准函数分配一个适当大小的空间作为队列的头结点，并使队头、队尾指针指向它；2）若分配空间成功则置头结点的指针域为空，否则结束算法。Q.front=Q.rear=(QueuePtr)malloc(sizeof(Qnode));Q.front->next=NULL;二.链队列基本操作的实现P62

StatusInitQueue(LinkQueue&Q){//构造一个空队列Q

returnOK;}Q.front=Q.rear=(QueuePtr)malloc(sizeof(Qnode));

//分配队的表头结点空间，并使队头、队尾指针指向它。if(!Q.front)exit(OVERFLOW);//存储分配失败Q.front->next=NULL;P622、链队列的插入操作：EnQueue(Q,e)：1）产生新的结点e，并使p指针指向它；2）将新结点插入链队的尾部（修改链）。p=(QueuePtr)malloc(sizeof(QNode));P->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;操作思路：要求：∧an…Q.frontQ.rear插入元素e为Q的新的队尾元素e∧pP62

StatusEnQueue(LinkQueue&Q,QElemTypee){//插入元素e为Q的新的队尾元素returnOK;}p=(QueuePtr)malloc(sizeof(QNode));

if(!p)exit(OVERFLOW);//存储分配失败

p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;P623、链队列的删除操作：DeQueue(&Q，&e)：1）若队列空，则结束算法；2）若队列非空，则将队头元素删除，并用e保留其值。if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;操作思路：要求：删除队首元素，并用e保留其值；∧an…Q.frontQ.reara1a2P4)释放空间：free(p);算法如下：3)若删除的是队尾元素，则修改队尾指针If(Q.rear==p)Q.rear=Q.front;

StatusDeQueue(LinkQueue&Q,QElemType&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;P62一、顺序与循环队列的结构描述顺序与循环队列二、循环队列基本操作的实现#defineMAXQSIZE100//最大队列长度

typedefstruct{QElemType*base;//动态分配存储空间

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

//指向队列头元素

intrear;//尾指针，若队列不空，指向

//队列尾元素的下一个位置

}SqQueue;QElemTypedata[MAXQSIZE];静态存储空间一、顺序与循环队列的结构描述SqQueueQ;Q.baseQ.frontQ.rear

空队列Q.baseQ.frontQ.rear序号值：012345Q.front=Q.rearQ.rear=MAXQSIZE假溢出现象入队EnQueue(&Q,e):

Q.base[Q.rear++]=e;出队DeQueue(&Q,e):e=Q.base[Q.front++];顺序队空条件：顺序队满条件：ea1a2a3a4a5循环队列：

将顺序队列看成是首尾相联的队列。3-3-13假设：MAXQSIZE=6054321Q.frontQ.reara1a2a3a4a5循环队空条件：循环队满条件：Q.front=Q.rearQ.front=Q.rear队空与队满的条件相同，无法判断，怎么办？a62、少用一个元素空间：如下图循环队空条件：循环队满条件：Q.front=Q.rear（Q.rear+1）%MAXQSIZE=Q.front1、设一个标志位以区分队列是“空”，还是“满”；处理方法有两种：054321Q.frontQ.reara1a2a3a4a5空1.构造一个空循环队列InitQ