第三章 栈和队列

第三章栈和队列第一页，共九十页，编辑于2023年，星期四纲要3.1栈的定义及其运算3.2栈的表示和实现3.2.1栈的顺序存储结构3.2.2栈的链式存储结构3.3栈的应用3.4队列3.5队列的表示和实现3.5.1队列的链式存储结构3.5.2队列的顺序存储结构3.6队列的运用第二页，共九十页，编辑于2023年，星期四从数据结构角度看，栈和队列是操作受限的线性表，他们的逻辑结构相同。栈只允许在表的一端进行插入或删除操作队列只允许在表的一端进行插入操作、而在另一端进行删除操作。

第三章栈和队列第三页，共九十页，编辑于2023年，星期四3.1栈的逻辑结构1．栈的定义栈的示意图栈：限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一个固定端称为栈底。（a1,a2,……,an）出栈a1a2an-1an……栈顶top

栈底base入栈第四页，共九十页，编辑于2023年，星期四3.1栈的逻辑结构设栈S=（a1

a1,a2,……,an）,则

a1为栈底元素，an为栈顶元素栈也称为后进先出（LastInFirstOut）的线性表（简称为LIFO表）出栈a1a2an-1an……栈顶top

栈底base入栈插入：入栈、进栈、压栈删除：出栈、退栈空栈：不含任何数据元素的栈。

栈的操作特性：后进先出栈的示意图第五页，共九十页，编辑于2023年，星期四3.1栈的逻辑结构注意：

栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？思考：第六页，共九十页，编辑于2023年，星期四3.1栈的逻辑结构2、栈的抽象数据类型定义ADTStackData栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系Operation

InitStack（&s）初始条件：栈不存在输入：无功能：栈的初始化输出：无操作结果：构造一个空栈

第七页，共九十页，编辑于2023年，星期四3.1栈的逻辑结构DestroyStack(&s)初始条件：栈已存在输入：无功能：销毁栈输出：无操作结果：释放栈所占用的存储空间Push(&s,x)初始条件：栈已存在输入：元素值x功能：在栈顶插入一个元素x输出：如果插入不成功，抛出异常操作结果：如果插入成功，栈顶增加了一个元素2、栈的抽象数据类型定义第八页，共九十页，编辑于2023年，星期四3.1栈的逻辑结构Pop(&s,&x)初始条件：栈已存在输入：无功能：删除栈顶元素输出：如果删除成功，返回被删元素值x，否则，抛出异常操作结果：如果删除成功，栈减少了一个元素GetTop(s,&x)初始条件：栈已存在输入：无功能：读取当前的栈顶元素输出：若栈不空，返回当前的栈顶元素值操作结果：栈不变2、栈的抽象数据类型定义第九页，共九十页，编辑于2023年，星期四3.1栈的逻辑结构StackEmpty(s)初始条件：栈已存在输入：无功能：判断栈是否为空输出：如果栈为空，返回TRUE，否则，返回FALSE操作结果：栈不变endADT2、栈的抽象数据类型定义第十页，共九十页，编辑于2023年，星期四3.2栈的顺序存储结构及实现因栈是一种特殊的线性表，同线性表类似，栈也有两种存储结构：顺序存储结构链表存储结构第十一页，共九十页，编辑于2023年，星期四3.2栈的顺序存储结构及实现顺序栈——栈的顺序存储结构如何改造数组实现栈的顺序存储？确定用数组的哪一端表示栈底。附设指示器top指示栈顶元素在数组中的位置。

012345678a1top第十二页，共九十页，编辑于2023年，星期四（a）空栈(top=base或top=-1)；（b）插入元素A后；（c）插入元素B、C、D、E后(栈满)；（d）删除元素E、D后（e）删除元素C、B、A后（栈空）top（b）栈中元素与栈顶指针的变化:3.2栈的顺序存储结构及实现顺序栈的几种状态topA（c）DCBEtop（d）CBAtopbase（e）topbase（a）43210A第十三页，共九十页，编辑于2023年，星期四“上溢”-----当s.top=stacksize-1表示栈满，此时，再做进栈运算必定产生空间溢出，简称“上溢”“下溢”-----当s.top=s.base(或s.top=-1）时表示栈空，此时再做退栈运算也将产生溢出，简称“下溢”。

上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。3.2栈的顺序存储结构及实现第十四页，共九十页，编辑于2023年，星期四---（简易版）#definemaxsize100typedefstruct{ //顺序栈定义

ElemTypeelem[maxsize];//栈数组

inttop; //栈顶指示器}SqStack;3.2栈的顺序存储结构及实现top(栈空:top=-1)elem顺序栈的顺序存储类型描述第十五页，共九十页，编辑于2023年，星期四顺序栈的顺序存储表示---（完整版）#definestack_Init_Size100#defineStackIncreament10typedefstruct{ //顺序栈定义

ElemType*base; //栈底指示器

ElemType*top;//栈顶示器

intStackSize;//当前已分配的存储空间}SqStack;3.2栈的顺序存储结构及实现Top(栈空：top=base)base第十六页，共九十页，编辑于2023年，星期四顺序栈的实现（1）初始化栈voidinitStack(SqStack&s){/*创建一个空栈由指针S指出*/s.base=(elemtype*)malloc(sizeof(elemtype);if(!s.base)returnFALSE;s.top=s.base;returnok;}3.2栈的顺序存储结构及实现第十七页，共九十页，编辑于2023年，星期四intPushStack(SqStack&s,Elemtypex){/*将元素x插入到栈s中，作为s的新栈顶*/if(s.top>=stacksize)returnFALSE;/*栈满*/s.elem[s.top]=x;

s.top++;returnTRUE;}（2）入栈操作3.2栈的顺序存储结构及实现时间复杂度？第十八页，共九十页，编辑于2023年，星期四intPopStack(SqStack&s,Elemtype&x){/*若栈s不为空，则删除栈顶元素*/if(s.top<0)returnNULL;/*栈空*/s.top--;/*栈顶下移*/x=s.elem[s.top];/*取出栈顶元素*/returnok;}（3）出栈操作3.2栈的顺序存储结构及实现时间复杂度？第十九页，共九十页，编辑于2023年，星期四IntGetStackTop(SqStacks,Elemtype&x){/*若栈s不为空，则返回栈顶元素*/if(s.top==s.base)returnNULL;/*栈空*/return(s.elem[s.top-1]);/*取出栈顶元素*/}（4）取栈顶元素操作3.2栈的顺序存储结构及实现取栈顶元素与出栈操作之间有什么不同第二十页，共九十页，编辑于2023年，星期四intEmpty(stack&s){/*栈s为空时，返回为TRUE；非空时，返回为FALSE*/if(s.top==s.base)returnTRUE;returnFALSE;}voidsetEmpty(stack&s){/*将栈s的栈顶指针top，置为base*/s.top=s.base;}（5）判栈空操作（6）置空操作3.2栈的顺序存储结构及实现第二十一页，共九十页，编辑于2023年，星期四3.2栈的顺序存储结构及实现两栈共享空间解决方案1：直接解决：为每个栈开辟一个数组空间。解决方案2：

顺序栈单向延伸——使用一个数组来存储两个栈在一个程序中需要同时使用具有相同数据类型的两个栈，如何顺序存储这两个栈？会出现什么问题？如何解决？第二十二页，共九十页，编辑于2023年，星期四3.2栈的顺序存储结构及实现两栈共享空间：使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。两栈共享空间第二十三页，共九十页，编辑于2023年，星期四3.2栈的顺序存储结构及实现栈1的底固定在下标为0的一端；栈2的底固定在下标为StackSize-1的一端。top1和top2分别为栈1和栈2的栈顶指示器；Stack_Size为整个数组空间的大小（图中用S表示）；a1

a2…aitop1012…

…S-1两栈共享空间top2bj

……b2

b1栈1底栈2底第二十四页，共九十页，编辑于2023年，星期四3.2栈的顺序存储结构及实现top1=-1什么时候栈1为空？a1

a2…aitop1012…

…S-1两栈共享空间top2bj

……b2

b1top1第二十五页，共九十页，编辑于2023年，星期四3.2栈的顺序存储结构及实现top1=-1什么时候栈1为空？a1

a2…aitop1012…

…S-1两栈共享空间top2bj

……b2

b1什么时候栈2为空？top2top2=Stack_Size第二十六页，共九十页，编辑于2023年，星期四3.2栈的顺序存储结构及实现top1=-1什么时候栈1为空？a1

a2……aitop1012…

…S-1两栈共享空间top2bj

……b2

b1什么时候栈2为空？top2=Stack_Size什么时候栈满？top2=top1+1第二十七页，共九十页，编辑于2023年，星期四3.3栈的链式存储结构及实现链栈：栈的链接存储结构如何改造链表实现栈的链接存储？链栈需要加头结点吗？将哪一端作为栈顶？将链头作为栈顶，方便操作。链栈不需要附设头结点。a1a2anhead第二十八页，共九十页，编辑于2023年，星期四3.3栈的链式存储结构及实现链栈：栈的链接存储结构两种示意图在内存中对应同一种状态栈顶栈底栈顶栈底topanan-1a1∧a1an-1antop∧a1a2anheaddatanext结点结构第二十九页，共九十页，编辑于2023年，星期四链栈中数据元素与栈顶指针top的关系：（a）栈空top=null（b）含有两个元素A、B的栈；（c）插入元素C后的栈；（d）删除元素C、B后的栈（b）（a）AB∧top（c）A∧topAtopCB∧3.3栈的链式存储结构及实现第三十页，共九十页，编辑于2023年，星期四

链栈的类型说明如下：typedefstructsnode{elemtypedata;structsnode*next;}StackNode,*LkStack;3.3栈的链式存储结构及实现第三十一页，共九十页，编辑于2023年，星期四Voidinitstack(LkStack&ls){ls=null;}

----初始化链栈链栈的实现3.3栈的链式存储结构及实现第三十二页，共九十页，编辑于2023年，星期四Voidgetstacktop(lkstack&ls){if(ls==null)error(“stackisempty.”);return(ls–>data);}链栈的实现-----取栈顶元素3.3栈的链式存储结构及实现第三十三页，共九十页，编辑于2023年，星期四3.3栈的链式存储结构及实现lsanan-1a1∧xpls为什么没有判断栈满？算法描述：Voidpush(LkStack&ls,elemtypex)p=(snode*)malloc(sizeof(snode));p–>data=x;p–>next=ls;

ls=p;returnok;}链栈的实现-----入栈第三十四页，共九十页，编辑于2023年，星期四算法描述voidpop(LkStack&ls,elemtype&x)if(ls==NULL)returnNULL;p=ls;x=p->data;ls=ls->next;free(p);returnok;}链栈的实现-----出栈lsanan-1a1∧lsp

ls++可以吗？3.3栈的链式存储结构及实现第三十五页，共九十页，编辑于2023年，星期四3.3栈的链式存储结构及实现顺序栈和链栈的比较时间性能：相同，都是常数时间O(1)。空间性能：顺序栈：有元素个数的限制和空间浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空间时才会出现满的情况，但是每个元素都需要一个指针域，从而产生了结构性开销。

总之，当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。第三十六页，共九十页，编辑于2023年，星期四

由于栈结构具有后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。

3.4栈的应用第三十七页，共九十页，编辑于2023年，星期四3.4栈的应用1.借助栈来实现单链表逆置算法【分析】利用栈的特征，先沿着链表从头至尾扫描一遍，将链表的每个结点的data域的值依次进栈，然后再沿着链表从头至尾扫描一遍，同时栈中元素依次出栈，并填入到链表的每个结点的data域中。第三十八页，共九十页，编辑于2023年，星期四算法Statusreverse(LinkList&L){Lkstackls;elemtypex;initstack(ls);//初始化栈p=L->next;while(p!=null){push(ls,p->data);p=p->next;}p=L->next;while(!emptystack(ls)){pop(ls,x);p->data=x;p=p->next;}}第三十九页，共九十页，编辑于2023年，星期四2.行编辑程序一个简单的行编辑程序功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。由于用户在终端上进行输入时，不能保证不出差错,如原为输入：while(*s)却输成：whliilre(s)。在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。比如：whli##ilr#e(s#*s)outcha@putchar(*s=#++)实际上为：while(*s)putchar(*s++)3.4栈的应用第四十页，共九十页，编辑于2023年，星期四算法如下:

voidlineedit(){//利用字符栈S，从终端接收一行并传送至调用过程的数据区initstack(s);//构造空栈Sch=gether();//从终端接收一个字符while(ch!=eof){//若全文未结束while(ch!=eof&&ch!=‘\n’){

switch(ch){case‘#’:pop(s,c);break;//仅当栈非空时退栈case‘@’:clearstack(s);break;//重置s为空栈default:push(s,ch);break;//有效字符进栈，未考虑栈满情形}第四十一页，共九十页，编辑于2023年，星期四ch=getchar();//从终端接收下一个字符}//将从栈底到栈顶的栈内字符传送至调用过程的数据区clearstack(s);//重置s为空栈if(ch!=eof)ch=gethar();}destroystack(s);//结束字符输入后销毁栈}第四十二页，共九十页，编辑于2023年，星期四3.5队列定义队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表允许插入（也称入队、进队）的一端叫做队尾(rear)，允许删除（也称出队）的一端叫做队头(front)。空队列：不含任何数据元素的队列。

3.5.1队列的逻辑结构（a1,a2,……,an）队尾队头第四十三页，共九十页，编辑于2023年，星期四3.5队列队列的操作特性：先进先出(FIFO,FirstInFirstOut)a1a2a3入队队尾队头出队队头队列的逻辑结构（a1,a2,……,an）队尾队头栈与队列有什么异同点？第四十四页，共九十页，编辑于2023年，星期四3.5.1队列的逻辑结构队列的抽象数据类型定义ADTQueueData队列中元素具有相同类型及先进先出特性，相邻元素具有前驱和后继关系Operation

InitQueue(&Q)初始条件：队列Q不存在输入：无功能：初始化队列输出：无操作结果：创建一个空队列第四十五页，共九十页，编辑于2023年，星期四3.5.1队列的逻辑结构

DestroyQueue(&Q)初始条件：队列Q已存在输入：无功能：销毁队列输出：无操作结果：释放队列所占用的存储空间

EnQueue(&Q,e)初始条件：队列Q已存在输入：元素值e功能：在队尾插入一个元素输出：如果插入不成功，抛出异常操作结果：插入元素e为新的队尾元素队列的抽象数据类型定义第四十六页，共九十页，编辑于2023年，星期四3.5.1队列的逻辑结构

DeQueue(&Q,&e)初始条件：队列Q已存在输入：无功能：删除队头元素输出：如果删除成功，返回被删元素值操作结果：删除Q的队头元素，并用e返回其值

GetQueue(Q)初始条件：队列Q已存在输入：无功能：读取队头元素输出：若队列不空，返回队头元素操作结果：队列不变队列的抽象数据类型定义第四十七页，共九十页，编辑于2023年，星期四3.5.2队列的链式存储结构及实现

链队列：队列的链式存储结构队头指针即为链表的头指针如何改造单链表实现队列的链式存储？rearfronta1a2anhead1、队列的链队列链队列是否需要附设头结点吗？第四十八页，共九十页，编辑于2023年，星期四3.5.2队列的链式存储结构及实现

Q.fronta1a2anQ.rear带头结点的链队列非空链队列空链队列 Q.front Q.rear第四十九页，共九十页，编辑于2023年，星期四3.5.2队列的链式存储结构及实现

2、链队列的类型定义typedefstructQnode

{ /*定义队列的结点结构*/

ElemTypedata; //队列结点数据

structQnode*next;//结点链指针}QNode,*QueuePtr;typedef

struct{/*链队列结构*/QueuePtrfront;/*队头指针*/

QueuePtrrear;/*队尾指针*/}LkQueue;定义一个指向链队列的指针：LkQueue*q;第五十页，共九十页，编辑于2023年，星期四intinitLkqueue(Lkqueue&q){/*创建一个空链队列q*/q.front=(Queueptr)malloc(sizeof(Qnodeif(!q.front)returnFALSE;q.front->next=NULL;//头结点无后继q.rear=q.front;//队尾也指向头结点returnok;}3.5.2队列的链式存储结构及实现

Q.rear Q.front3、链队列的实现----初始化队列第五十一页，共九十页，编辑于2023年，星期四3.5.2队列的链式存储结构及实现

xs链队列的实现——入队fronta1an∧rear∧rearfrontxs∧∧rearrear算法描述：s->next=NULL;rear->next=s;rear=s;（一）带头结点的链队列插入元素x为Q的新的队尾元素第五十二页，共九十页，编辑于2023年，星期四3.5.2队列的链式存储结构及实现

xs链队列的实现——入队fronta2an∧rear∧rear算法描述：s->next=NULL;rear->next=s;rear=s;如何没有头结点会怎样？a1（二）无头结点的链队列第五十三页，共九十页，编辑于2023年，星期四3.5.2队列的链式存储结构及实现

xs链队列的实现——入队fronta2an∧rear∧rearfront=rear=NULLxs∧rear算法描述：s->next=NULL;rear=s;front=s;如何没有头结点会怎样？a1front（二）无头结点的链队列第五十四页，共九十页，编辑于2023年，星期四voidEnQueue(LkQueue&Q,Elemtypex){/*将元素x插入到链队列Q中，作为Q的新队尾*/if((s=(Queueptr)malloc(sizeof(Qnode)))==NULL)returnFALSE;s->data=x;s->next=NULL;Q.rear->next=s;Q.rear=s;returnOK;}链队列的实现——入队3.5.2队列的链式存储结构及实现

第五十五页，共九十页，编辑于2023年，星期四3.5.2队列的链式存储结构及实现

链队列的实现——出队fronta1a2an∧rearp算法描述：p=front->next;front->next=p->next;第五十六页，共九十页，编辑于2023年，星期四3.5.2队列的链式存储结构及实现

链队列的实现——出队fronta1a2an∧rearp考虑边界情况：队列中只有一个元素？fronta1p∧rear∧rear算法描述：if(p->next==NULL)rear=front;如何判断边界情况？第五十七页，共九十页，编辑于2023年，星期四VoidDeQueue(LkQueue&Q,Elemtypex){/*若链队列q不为空，则删除队头元素，返回其元素值*/if(Q.front->next==NULL)returnNULL;P=Q.front->next;x=p->data;Q.front->next=p->next;If(p->next==null)Q.rear=Q.front;free(p);returnx;}链队列的实现——出队3.5.2队列的链式存储结构及实现

也可用Q.rear==p描述第五十八页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现01234入队出队顺序队列：队列的顺序存储结构如何改造数组实现队列的顺序存储？例：a1a2a3a4依次入队a1a2a3a4rearrearrearrear入队操作时间性能为O(1)第五十九页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现如何改造数组实现队列的顺序存储？例：a1a2依次出队队列的顺序存储结构01234入队出队a1a2a3a4rear第六十页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现如何改造数组实现队列的顺序存储？例：a1a2依次出队队列的顺序存储结构01234入队出队a2a3a4rear第六十一页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现如何改造数组实现队列的顺序存储？例：a1a2依次出队01234入队出队a3a4rear出队操作时间性能为O(n)队列的顺序存储结构第六十二页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现队列的顺序存储结构如何改进出队的时间性能？放宽队列的所有元素必须存储在数组的前n个单元这一条件，只要求队列的元素存储在数组中连续的位置。设立两个指示器：一个为指向队头元素位置的指示器front，另一个为指向队尾的元素位置的指示器rear。a1a2

an-1，anfrontrear第六十三页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现队列的顺序存储结构01234入队出队例：a1a2a3a4依次入队a1a2a3a4rearrearrearrear入队操作时间性能仍为O(1)frontrear第六十四页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现例：a1a2依次出队队列的顺序存储结构01234入队出队a1a2a3a4rearfrontfrontfront出队操作时间性能提高为O(1)第六十五页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现例：a1a2依次出队队列的顺序存储结构01234入队出队a3a4rearfront队列的移动有什么特点？整个队列向数组下标较大方向移动单向移动性第六十六页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现假溢出：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。队列的顺序存储结构继续入队会出现什么情况？01234入队出队a3a4rearfronta5rear第六十七页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现循环队列：将存储队列的数组头尾相接。队列的顺序存储结构如何解决假溢出？01234入队出队a3a4fronta5rearreara6第六十八页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现如何解决假溢出？循环队列第六十九页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现第一种情况用队头指针Q.front指向队头元素所在的单元，用队尾指针Q.rear指向队尾元素所在的单元第七十页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现第二种情况---队头指针Q.front指向队头元素所在单元的前一个单元，队尾指针Q.rear指向队尾元素所在的单元第七十一页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现第三种情况---队尾指针Q.rear指向队尾元素所在单元的下一个单元，队头指针Q.front指向队头元素所在的单元第七十二页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现在循环数组中，不论用哪一种方式来指示队头与队尾元素，我们都要解决两个问题:1.当Q.rear或Q.front=maxsize-1时，再加1怎样回到“0”的位置？2.如何表示满队列和空队列？对于第一个问题，可采用“%”运算---取模(余数)运算来解决让队头、队尾指针加1后取余运算，就能实现自动回“0”，即Q.front=（Q.front+1）%maxsizeQ.rear=(Q.rear+1)%maxsize注：循环队列的下标序号为0..maxsize-1队满、队空第七十三页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现2.如何表示满队列和空队列？如图设MaxSize=6，队列中已有3个元素。我们用上述3种方法来指示队头和队尾元素，分别如图所示(1)(2)(3)第七十四页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现现在，另有3个元素a4,a5,a6相继入队，使队列呈"满"的状态队满：Q.rear=Q.front第七十五页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现如果3个元素a1,a2,a3相继出队，使队列呈“空”的状态队空：Q.rear=Q.front第七十六页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现队满、队空的解决办法通常有两种处理方法来解决这个问题。方法一：另设一个标志位以区别队列是“空”还是“满”。比如设一个布尔量来注明队列是空还是满。方法二：少用一个元素空间，约定以“以队尾指针加1等于队头指针”作为队列呈“满”状态的标志。

即（Q.rear+1）%maxsize=Q.front//队满Q.rear=Q.front//队空约定：采用第二种方法第七十七页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现改进后的队满情况第七十八页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现循环队列类型说明如下：#defineMAXSIZE100//最大队列长度typedefstruct{elemtypedata[MAXSIZE];//队列元素Intfront;//头指示器，若队列不空，指向队列头元素Intrear;//尾指示器，若队列不空，指向队列尾元素的下一个位置}cirqueue;第七十九页，共九十页，编辑于2023年，星期四statusinitqueue(cirqueue&Q){Q.front=Q.rear=0;returnok;}（1）队列初始化循环队列的实现3.5.3队列的顺序存储结构及实现第八十页，共九十页，编辑于2023年，星期四3.5.3队列的顺序存储结构及实现(2)入队列将一个新元素x插入到队尾步骤当(Q.rear+1）%maxsize<>Q.front时，按以下步骤：（1）Q.data[Q.rear]=x;(2)Q.rear=(Q.rear+1)%maxsize;

第八十一页，共九十页，编辑于202