数据结构课件(栈和队列)

数据结构

第三章栈和队列1/13/2023第三章栈和队列3.1栈栈和队列也是线性表，只不过是操作受限的线性表。栈是限定在表尾进行插入或删除操作的线性表。表尾端称栈顶，表头端称栈底。如图。an...a2a1栈底栈顶出栈进栈栈顶（TOP）--允许插入和删除的一端。栈底(bottom)--不允许插入和删除的一端。空栈--表中没有元素。进栈---最先插入的元素放在栈的底部。退栈---最后插入的元素最先退栈。 所以栈又称为后进先出的线性表（LIFO表，LastInFirstOut）3.1栈3.1.1栈的类型定义ADTStack{数据对象：D＝{ai|ai

∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}约定an

端为栈顶，a1端为栈底。基本操作：InitStack(&S) 操作结果：构造一个空栈S。DestroyStack(&S)

初始条件：栈S已存在。

操作结果：栈S被销毁。ClearStack(&S) 初始条件：栈S已存在。

操作结果：将S清为空栈。StackEmpty(S)

初始条件：栈S已存在。

操作结果：若栈S为空栈，则返回TRUE，否则FALSE。3.1栈3.1.1栈的类型定义StackLength(S) 初始条件：栈S已存在。

操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e) 初始条件：栈S已存在且非空。

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

操作结果：插入元素e为新的栈顶元素。Pop(&S,&e) 初始条件：栈S已存在且非空。

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

}ADTStack3.1栈3.1.2栈的表示和实现----顺序表示#defineSTACK_INIT_SIZE100//栈内存的初始分配量，以sizeof(ElemType)为单位

#defineSTACKINCREMENT10//栈内存的分配增量，以sizeof(ElemType)为单位

typedef

struct{

SElemType*base; //存储空间的基址，数据元素的数据类型约定为SElemType

SElemType*top; //表示栈顶，如果top==base，表示空栈

int

stacksize; //当前分配的存储容量，以sizeof(ElemType)为单位

}SqStack

3210Top=base空栈TopbaseA

3210TOP

A进栈base

3210DCBAB、C、D依次进栈TOPbase

3210BATOPD、C依次退栈base

3210B、A退栈baseTOP3.1栈3.1.2栈的表示和实现----顺序表示顺序栈基本操作的实现StatusInitStack(SqStack&S)

{

//为栈S分配存储空间，并置S为空栈

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

sizeof(SElemType));if(!S.base) exit(OVERFLOW);S.top=S.base;//置栈S为空栈

S.stacksize=STACK_INIT_SIZE;

returnOK;

}//InitStack

3.1.2栈的表示和实现----顺序表示顺序栈基本操作的实现StatusGetTop(SqStack

S,SElemType&e)

{

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

if(S.top==S.base)returnERROR; e=*(S.top-1);

returnOK;

}

//GetTop

3.1.2栈的表示和实现----顺序表示顺序栈基本操作的实现StatusPush(SqStack&S,SElemTypee)

//将e插入栈S中并使之成为栈顶元素

if(S.top-S.base>=S.stacksize)

{

//栈满，追加存储空间

S.base=(SElemType*)realloc(S.base,

(S.stacksize+STACKINCREMENT)*sizeof(ElemType)); if(!S.base) exit(OVERFLOW);

//存储分配失败

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;returnOK;

}//Push3.1.2栈的表示和实现----顺序表示顺序栈基本操作的实现StatusPop(SqStack&S,SElemType&e)

{

//若栈S不空，则删除S的栈顶元素，用e返回其值并返回OK，否则返回ERROR

if(S.top==S.base)returnERROR; e=*--S.top;

returnOK;

}

//Pop

3.1.2栈的表示和实现----顺序表示顺序栈基本操作的实现

StatusDestroyStack(SqStack&S)

{

//释放栈S所占据的存储空间

if(!S.base)returnERROR;

free(S.base);

S.base=NULL;

S.top=NULL;

returnOK;

}//DestroyStackStatusClearStack(SqStack&S)

{

//将栈S清为空栈

S.top=S.base;

returnOK;

}

//ClearStack

3.1.2栈的表示和实现----顺序表示顺序栈基本操作的实现StatusStackEmpty(SqStackS)

{

//如果栈为空栈，则返回TRUE，否则返回FALSE

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

elsereturnFALSE;

}

//StackEmptyStatusStackLength(SqStackS)

{

//返回栈S的长度

returnS.top-S.base;

}

//StackLength3.1.2栈的表示和实现----顺序表示顺序栈基本操作的实现StatusStackTraverse(SqStackS,Status(*visit)(SElemTypee))

{

//从栈底到栈顶依次对栈中每个元素调用visit函数，如果visit失败，则操作失败

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

for(i=0;i＜S.top-S.base;i++)

if(visit(S.base[i])==ERROR)

returnERROR;

returnOK;

}

//StackTraverse

3.1.2栈的表示和实现----链接表示链栈的表示structNode/*单链表结点结构*/{ElemTypeinfo;

structNode*link;

};struct

LinkStack/*链栈类型定义*/{structNode*top;/*指向栈顶结点*/

}LinkStack,*PLinkStack;batcateatmat^…headtopbottom3.1.2栈的表示和实现----链接表示链栈基本操作的实现PLinkStack

createEmptyStack_link()

{//创建一个空栈

PLinkStack

plstack;

plstack=(struct

LinkStack*)malloc(sizeof(struct

LinkStack)); if(plstack!=NULL)

plstack->top=NULL; else

printf("Outofspace!\n"); returnplstack;

}DataTypetop_link(PLinkStack

plstack)

/*对非空栈求栈顶元素*/{ returnplstack->top->info；}3.1.2栈的表示和实现----链接表示链栈基本操作的实现int

isEmptyStack_link(PLinkStack

plstack)

{//判单链形式栈是否为空栈

return(plstack->top==NULL);

}voidpush_link(PLinkStack

plstack,DataTypex)

/*在栈中压入一元素x*/{ structNode*p; p=(structNode*)malloc(sizeof(structNode)); if(p==NULL)

printf("Outofspace!\n"); else{ p->info=x; p->link=plstack->top;

plstack->top=p;}

}3.1.2栈的表示和实现----链接表示链栈基本操作的实现ElemTypepop_link(PLinkStack

plstack)

/*在栈中删除栈顶元素*/{ structNode*p; ElemType

elem; if(isEmptyStack_link(plstack))

printf("Emptystackpop.\n"); else{ p=plstack->top;

elem=p->info;

plstack->top=plstack->top->link; free(p);

} returnelem;

}3.2栈的应用举例3.2.1数制转换 将某十进制数N转换为其他d进制数是计算机实现计算的基本问题，其解决方案很多，其中一个简单算法基于下面的原理：

N=(Ndivd)×d+Nmodd(其中：div为整除运算，mod为求余运算)

比如，(1348)10=(2504)8，其运算过程如下：

N Ndiv8 Nmod8

1348 168 4 168 21 0 21 2 5 2 0 2所以：(1348)10=(2504)83.2栈的应用举例3.2.1数制转换假设现在要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。由于上述计算过程是从低位到高位顺序产生八进制数的各个数位。而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。因此，若将计算过程中得到的八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。3.2栈的应用举例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);

}

}

//conversion3.2栈的应用举例3.2.2 括号匹配的检验假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（［］（））或［（［］［］）］等为正确的格式，［（］）或（［（））或(()])均为不正确的格式。检验括号是否匹配的方法可用"期待的急迫程度"这个概念来描述。例如考虑下列括号序列：[ ( [ ] [ ] ) ]1 2 3 4 5 6 7 8分析可能出现的不匹配的情况:到来的右括弧不是所“期待”的;到来的是“不速之客”;直到结束，也没有到来所“期待”的。3.2栈的应用举例3.2.2 括号匹配的检验statusmatching(string&exp){//检验表达式中所含括弧是否正确嵌套，若是，则返回OK，否则返回ERRORInitStack(S);//构造空栈Sintstate=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;}3.2栈的应用举例3.2.3行编辑程序问题

一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。每接受一个字符即存入用户数据区“不恰当”。较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。例如，可用一个退格符“#”表示前一个字符无效；可用一个退行符“@”，表示当前行中的字符均无效。例如，假设从终端接受了这样两行字符：whli##ilr#e（s#*s)

outcha@putchar(*s=

#++);则实际有效的是下列两行：

while(*s)

putchar(*s++);3.2栈的应用举例3.2.3行编辑程序问题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();//从终端接收下一个字符}将从栈底到栈顶的字符传送至调用过程的数据区；ClearStack(S);//重置S为空栈if(ch!=EOF)ch=getchar();}DestroyStack(S);}表达式求值"算符优先法" 要想对算术表达式求值，首先要能正确解释表达式。比如，按照算术运算规则，表达式

4＋2×3－10／5

的计算顺序应为：

4＋2×3－10／5＝4＋6－10／5＝10－10／5

＝10－2＝8

算符优先法就是根据这个运算优先关系的规定来实现对表达式的编译或解释执行的。 任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。操作数可以是常数也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符三类；基本界限符有左右括号和表达式结束符等表达式求值"算符优先法" 为了叙述简洁，我们仅讨论表达式中只含有加、减、乘、除四种运算符，并且操作数都是小于10的整数(这样只需输入一个字符就可以了)。 我们将运算符和界限符统称为算符，它们构成的集合命名为OP。根据算术运算规则，在运算的每一步中，任意两个相继出现的算符θ1和θ2之间的优先关系至多有三种：

θ1<θ2,即θ1的优先权低于θ2 θ1=θ2,即θ1的优先权等于θ2 θ1>θ2,即θ1的优先权高于θ2表达式求值"算符优先法"+－*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<= 由于算术运算的规则要求先计算括号内，后算括号外，因此+、－、*、/作为θ1时的优先权都低于(，但高于)。 算术运算规则又规定要从左算到右，因此如果θ1=θ2时，规定θ1的优先权高于θ2。

'#'是表达式的结束符。为了算法简洁，在表达式的最左边也虚设一个'#'构成整个表达式的一对括号。表中'('=')'表示当左右括号相遇时，括号内的运算已经完成。同理，'#'='#'表示整个表达式求值完成。')'与'('、'#'与')'以及'('与'#'之间无优先关系，因为表达式中不允许相继出现，一旦遇到这种情况，则可以认为出现的语法错误。表达式求值"算符优先法"（1）若该单词是操作数则将它压入操作数栈中。（2）若该单词是运算符，则将它与运算符栈栈顶运算符的优先级进行比较：若当前运算符>栈顶运算符，则将其压入运算符栈；若当前运算符<栈顶运算符，则弹出栈顶运算符和操作数栈中的相应操作数，完成其运算，并把计算结果压入操作数栈中；若当前运算符=栈顶运算符，则弹出运算符栈的栈顶符号，并读入下一单词，什么计算也不进行。反复执行上述过程，直至句末符“#”，操作数栈中只剩下一个结果值，表明分析正确。否则出错处理。3.2.2表达式求值算符优先分析法（示例）：对3*(2+5)-6*2的分析输入串:#3*(2+5)-6*2#符号栈操作数栈符号寄存器##33**((22++55

7)

-

21-66**22#

12

9

结果为9输入串:#3*(2+5)-6*2#输入串:#3*(2+5)-6*2#输入串:#3*(2+5)-6*2#输入串:#3*(2+5)-6*2#输入串:#3*(2+5)-6*2#输入串:#3*(2+5)-6*2#输入串:#3*(2+5)-6*2#输入串:#3*(2+5)-6*2#输入串:#3*(2+5)-6*2#输入串:#3*(2+5)-6*2#输入串:#3*(2+5)-6*2#输入串:#3*(2+5)-6*2#3.2.2表达式求值OperandType

EvaluateExpression()

{

//算术表达式求值的算符优先算法

//设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合

InitStack(OPTR);

Push(OPTR,'#');

InitStack(OPND);

c=getchar();

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

{

if(!In(c,OP)){//如果不是运算符则认为是操作数，进OPND栈

Push(OPND,c-'0');//真正的操作是c-'0'，而不是c

c=getchar();

}

else{

GetTop(OPTR,topc);

switch(Precede(topc,c))

{//比较OPTR栈顶运算符与c的优先权关系

3.2.2表达式求值

case‘<’://栈顶运算符优先权低

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

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

Pop(OPTR,x);

c=getchar();

break;

case‘>’://退栈并将运算结果入OPND栈

Pop(OPTR,theta);

Pop(OPND,b);

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

break;

}//switch

}//else

}//while

GetTop(OPND,result);

returnresult;

}//EvaluateExpression

3.2栈的应用举例3.2.6实现递归当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事:将所有的实在参数、返回地址等信息传递给被调用函数保存;为被调用函数的局部变量分配存储区;将控制转移到被调用函数的入口。从被调用函数返回调用函数之前，应该完成:保存被调函数的计算结果;释放被调函数的数据区;依照被调函数保存的返回地址将控制转移到调用函数。多个函数嵌套调用的规则是:后调用先返回。此时的内存管理实行“栈式管理”，递归过程占用的数据区称之为递归工作栈。每一层的递归参数合成一个记录，称之为递归工作记录。栈顶记录指示当前层的执行情况，称之为当前活动记录。栈顶指针，称之为当前环境指针。3.2栈的应用举例汉诺塔问题问题： 将X塔座上的N个圆盘移动到Z塔座上，移动规则如下：

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

2、圆盘可插在X、Y、Z任意一个塔座上

3、小圆盘必须在大圆盘之上3.2栈的应用举例如果只有一个盘，直接从X移动到Z即可;如果有N个盘，就要把N－1个盘先移到Y上，然后就可以把第N个盘移到Z上，再把N－1个盘从Y移到Z。voidhanoi(intn,charx,chary,charz)//将塔座x上按直径由小到大且至上而下编号为1至n的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1{if(n==1)2 move(x,1,z);//将编号为１的圆盘从x移到z3else{hanoi(n-1,x,z,y);//将x上编号为１至n-1的圆盘移到y,z作辅助塔4move(x,n,z);//将编号为n的圆盘从x移到z5 hanoi(n-1,y,x,z);//将y上编号为１至n-1的圆盘移到z,x作辅助塔}

6}多个栈的设计两个栈的设计与实现设有m个连续的存储单元，现分成两个栈使用。每个栈的容量不知且不相等。要求在任何时刻，只要两个栈中已存储的元素个数之和小于m，便能满足用户的进栈申请。其结构如下图所示：01234。。。。。。。。。。m-1

top1top2两个栈上的运算算法自己完成。3.3队列3.3.1.定义是一种先进先出的线性表（FIFO)，只允许在表的一端进行插入，另一端进行删除。在队列中，允许插入的一端叫做队尾(rear)，允许删除元素的一端则称为队头(front)。假设队列为q=(a1,a2,…,an)，那么，a1就是队头元素，an则是队尾元素。当队列中没有任何元素时，称为“空队列”。出队列入队列a1 a2 a3 ………… an队头队尾3.3.2队列的顺序表示和实现队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，它们的队列初始化时均应置为０。入队时将新元素插入所指的位置，然后将加１。出队时，删去所指的元素，然后将加１并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。3.3.2队列的顺序表示和实现队满的标志是rear=m，队空的标志是rear=front

Frontrear(a)队列初始为空cbaFrontrear（b）a,b,c入队cb（c)a出队frontrearfrontrear

(d)b,c出队，队为空3.3.3 队列的基本操作初始化：InitQueue(&Q)注销队列：DestroyQueue(&Q)清空队列：ClearQueue(&Q)入队列：EnQueue(&Q,e)出队列：OutQueue(&Q,&e)判断是否为空：QueueEmpty(Q)取队列头：GetHead(Q,&e)得到队列长度：QueueLength(Q)遍历队列：QueueTraverse(Q,visit())3.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

端为队列尾。基本操作：InitQueue(&Q) 操作结果：构造一个空队列Q。DestroyQueue(&Q) 初始条件：队列Q已存在。

操作结果：队列Q被销毁，不再存在。ClearQueue(&Q)

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

操作结果：将Q清为空队列。3.3.4队列的类型定义QueueEmpty(Q) 初始条件：队列Q已存在。

操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。QueueLength(Q) 初始条件：队列Q已存在。

操作结果：返回Q的元素个数，即队列的长度。GetHead(Q,&e) 初始条件：Q为非空队列。

操作结果：用e返回Q的队头元素。EnQueue(&Q,e) 初始条件：队列Q已存在。

操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q,&e) 初始条件：Q为非空队列。

操作结果：删除Q的队头元素，并用e返回其值。}ADTQueue3.3.5链队列的定义

用链表表示的队列简称为链队列，如下图所示。一个链队列需要两个分别指向队头和队尾的指针(分别称为头指针和尾指针)才能唯一确定。Q.rear^Q.Front队头队尾3.3.5链队列的定义用C语言描述typedef

struct

QNode

{

QElemTypedata;

struct

QNode*next;

}

QNode,*QueuePtr;typedef

struct

{

QueuePtrfront;//队头指针

QueuePtrrear;//队尾指针

}

LinkQueue;3.3.5链队列的定义基本操作的函数原型说明StatusInitQueue(LinkQueue&Q){//构造一个空队列QStatusDestroyQueue(LinkQueue&Q){//销毁队列Q，Q不再存在StatusClearQueue(LinkQueue&Q){//将Q清为空队列StatusQueueEmpty(LinkQueueQ){//若队列Q为空队列，则返回TRUE，否则返回FALSEint

QueueLength(LinkQueueQ){//返回Q的元素个数，即为队列的长度StatusGetHead(LinkQueueQ,QElemType&e){//若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR

StatusEnQueue(LinkQueue&Q,QElemTypee){//插入元素e为Q的新的队尾元素StatusDeQueue(LinkQueue&Q,QElemType&e){//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR3.3.5链队列的定义---具体算法StatusInitQueue(LinkQueue&Q){

//构造一个空队列Q

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(OVERFLOW);//存储分配失败

Q.front->next=NULL;

returnOK;

}//InitQueue

StatusEnQueue(LinkQueue&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;

}//EnQueue

3.3.5链队列的定义---具体算法StatusDeQueue(LinkQueue&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;//如果最后一个元素出队，重置Q为空队

free(p);

returnOK;

}//DeQueue

3.3.6循环队列问题的提出和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。3.3.6循环队列问题的提出J3Q.rearQ.frontJ3J2J1Q.rearQ.frontJ6J5Q.rearQ.frontQ.rearQ.front054321产生假溢出3.3.6循环队列为充分利用向量空间。克服假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（CircularQueue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。3.3.6循环队列Q.rearQ.frontJ5J7J6队列0543213.3.6循环队列这种循环意义下的加1操作可以描述为：

if(Q.rear+1==MaxQSize)Q.rear=0;elseQ.rear++;利用模运算可简化为：Q.rear=(Q.rear+1)%MaxQSize3.3.6循环队列显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。3.3.6循环队列Q.rearQ.frontJ3J5J4（A）一般情况队列054321（B）队列满时Q.rearQ.frontJ3J5J4054321J6J7J8Q.rearQ.front（C）队列空时0543213.3.6循环队列解决此问题的方法至少有三种：一、另设一个布尔变量以区别队列的空和满；二、少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；三、使用一个计数器记录队列中元素的总数（实际上是队列长度）。下面我们用第二种方法实现循环队列上的六种基本操作，为此先给出循环队列的类型定义。3.3.6循环队列循环队列的类型定义#defineQueueSize100

typedef

Struct{

int front;

int rear;

QElemType *base}