数据结构 第四章 栈和队列

主要内容

4.1栈

4.2栈的应用举例

4.3队列

4.4队列的应用举例栈和队列是软件设计中最常用的两种数据结构,它们的逻辑结构与线性表相同,其特点是运算受到限制:栈按“后进先出”的规则进行操作，队列按“先进先出”的规则进行操作，故称它们是运算受限制的线性表。4.1栈4.1.1栈的结构特点和操作1.定义

栈是限定仅在表的一端(表尾)进行插入和删除操作的线性表。栈中允许插入和删除的一端叫栈顶top，表尾称为栈顶；栈中不允许插入和删除的一端叫栈底bottom，表头称为栈底；不含数据元素的空表称为空栈。

栈的插入操作称为进栈或入栈，栈的删除操作称为出栈或退栈。每次入栈的元素总放在原栈顶元素之上成为新的栈顶，而每次出栈的元素总是当前栈中的最新的元素，也就是最后进栈的元素。栈又称为先进后出或后进先出表。（FILO或LIFO）。2.栈的基本操作1）InitStack(&S)将S初始化为空栈2）DestroyStack(&S)将栈S销毁3）ClearStack(&S)将栈S置成空栈

4）StackEmpty(S)

若栈S为空栈返回TRUE否则返回FALSE5）StackFull(S)若栈S已满返回TRUE，否则返回FALSE6）StackLength(S)

栈S存在则返回S的元素个数,即栈的长度7）GetTop(S,&e)栈S存在且非空则返回S的栈顶元素8）Push(&S,e)栈S存在且不满则插入元素e为新的栈顶元素9）Pop(&S,&e)栈S存在且非空则删除S的栈顶元素并用e返回其值，GetTop(S,&e)与Pop(&S,&e)不同在于GetTop(S,&e)不改变栈顶的位置。a1a2an……a1a2ane……10）StackTraverse(S)栈S存在且非空则从栈底到栈顶依次输出栈S中的每个数据元素4.1.2栈的表示和实现栈的存储方式：顺序栈和链栈1.顺序栈:

利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置。通常用top=-1表示空栈。//---顺序栈的存储表示---a1a2anan-1

……constSTACK_INIT_SIZE=100;constSTACKINCREMENT=10;typedef

struct{

SElemType*elem;

inttop;

int

stacksize;

intincrement;}SqStack;1).初始化栈voidInitStack(SqStack&S,int

maxsize=STACK_INIT_SIZE,int

incresize

=STACKINCREMENT){S.elem=newSElemType[STACK_INIT_SIZE];

S.top=-1;

S.stacksize=maxsize;S.increment=incresize;}//InitStack2).得到栈顶元素bool

GetTop(SqStackS,SElemType&e){

if(S.top==-1)returnfalse;e=S.elem[S.top];returntrue;}//GetTop3).让栈顶元素出栈bool

Pop(SqStack&S,SElemType&e){

if(S.top==-1)returnfalse;e=S.elem[S.top];

S.top--;returntrue;}//Pop4).入栈一个元素voidPush(SqStack&S,SElemTypee){

if(S.top==S.stacksize-1){

S.stacksize=S.stacksize+STACKINCREMENT;

SElemType*elem=newSElemType[S.stacksize];for(inti=0;i<=S.top;i++)

elem[i]=S.elem[i];delete[]S.elem;

S.elem=elem;}

S.top++;S.elem[S.top]=e;}//Push5).输出栈中的元素voidStackTraverse(SqStackS){for(inti=0;i<=S.top;i++)

cout<<S.elem[i])<<“”;

cout<<endl;}6).栈中元素的个数

int

StackLength(SqStackS){return(S.top+1);}7).判栈空

bool

StackEmpty(SqStackS){if(S.top==-1)returntrue;elsereturnfalse;}2.链栈若栈中元素的个数无法确定可以使用链栈(利用链式分配实现的栈),链栈中指针的方向是从栈顶指向栈底。结构定义：typedef

struct

LNode{SElemTypedata;

struct

LNode*next;}LNode,*LinkList;typedef

LinkList

LinkStack;LinkStackS;∧a1anan-1栈顶指针S1).初始化栈voidInitStack(LinkStack&S){S=NULL;//构造一个空的链栈,设栈顶指针为空}2).入栈一个元素,新定义一个结点放在链栈的开头voidPush(LinkStack&S,SElemTypee){

LNode*p=newLNode;p->data=e;p->next=S;//插入新的栈顶元素

S=p;//修改栈顶指针}//Push3).让栈顶元素出栈bool

Pop(LinkStack&S,SElemType&e){//若栈不空,则删除栈顶元素,以e返回其值,并返回true,否则返回false

if(S){LNode*p=S;S=S->next;e=p->data;deletep;returntrue;

}//ifelsereturnfalse;}//Pop4).得到栈顶元素bool

GetTop(LinkStack&S,SElemType&e){if(S){e=S->data;returntrue;}elsereturnfalse;}//GetTop5).栈中元素的个数int

StackLength(LinkStackS){intk=0;

LNode*p=S;

while(p){p=p->next;k++;}returnk;}//StackLength6).判栈空bool

StackEmpty(LinkStackS){if(S)returnfalse;returntrue;}//StackEmpty4.2栈的应用举例例4.1数制转换例4.2括号匹配的检验例4.3背包问题求解例4.4表达式求值例4.5实现递归例4.1

数制转换问题：输入一个非负十进制整数，打印输出与其等值的八进制数.例如：（1348)10=(2504)8

，其运算过程如下：

NNdiv8Nmod8

13481684

168210

2125

202计算顺序输出顺序//首先应定义栈中数据元素的类型为int类型typedef

int

SElemType;//算法4.1voidconversion(){SqStackS;intN;

SElemTypee;

InitStack(S);//构造空栈

cin>>N;while(N){Push(S,N%8);//"余数"入栈

N=N/8;//"商"继续运算

}while(!StackEmpty(S)){Pop(S,e);cout<<e;}//"求余"所得相逆的顺序输出八进制的各位数}//conversion主程序为voidmain(){conversion();}例4.2括号匹配：检验表达式中所含括弧是否正确嵌套，若是，则返回TRUE，否则返回FALSE.‘#’为表达式的结束符假设在表达式中允许包含两种括号:()和[]，其嵌套顺序随意，即（［］（））或［（［］［］）］等为正确的格式，[(])或（［（））或（（）］)均为不正确的格式。

检验括号是否匹配的方法可用“等待的急迫程度”这个概念来描述。例如：考虑下列括号序列：

[([][])]12345678分析可能出现的不匹配的情况:

到来的右括弧并非是所“期待”的；

到来的是“不速之客”；

直到结束，也没有到来所“期待”的括弧。算法的设计思想：1）凡出现左括弧，则进栈2）凡出现右括弧，首先检查栈是否空;若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配。3）表达式检验结束时，

若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。bool

matching(charexp[])//算法4.2{//检验表达式中所含括弧是否正确嵌套，若是，则返回true，

//否则返回flase.'#'为表达式的结束符

SqStackS;

InitStack(S);

intstate=1;chare;charch=*exp++;while(ch!='#'&&state){switch(ch){case'(':case'[':case'{':{Push(S,ch);break;}//左括弧入栈

case')':{if(!StackEmpty(S)&&GetTop(S,e)=='(')

Pop(S,e);elsestate=0;//说明右括弧多,不配对

break;}

case']':{if(!StackEmpty(S)&&GetTop(S,e)=='[')

Pop(S,e);elsestate=0;break;}case'}':{if(!StackEmpty(S)&&GetTop(S,e)=='{')

Pop(S,e);elsestate=0;break;}

default:break;//若为非括弧字符则直接跳过

}//switch

ch=*exp++;}//while

if(state&&StackEmpty(S))returntrue;elsereturnfalse;}//matching使用括号匹配应该将栈中数据元素的类型定义为chartypedefcharSElemType;voidmain(){chara[80];

cout<<"放入一个带括号()[]的表达式,以#作为结尾"<<endl;

cin>>a;

if(matching(a))cout<<a<<"的括号匹配\n";elsecout<<a<<"的括号不匹配\n";}例4.3背包问题：假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,w3,…,wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使wi1+wi2+…+wik=T,要求找出所有满足上述条件的解。

例如，当T=10,各件体积为{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2），（1，4，5），（8，2）和（3，5，2）。方法：利用“回溯”的设计思想来解背包问题。过程：首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃置而继续选取下一件，直至背包装满为止。但如果在剩余物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃置一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足要求的解，或者“无解”为止。

回溯：从当前背包中取出物品再继续搜索的策略称之为“回溯”。由于回溯求解的规则为“后进先出”（在此问题中物品取出的顺序恰好和装入的顺序相反），因此要用到栈。具体做法：对物品进行顺序编号（从0号起），然后从0号物品起顺序选取，若可以装入背包，则将该物品号“入栈”，背包体积减小，有两种情况：1.若背包正好装满，则输出一组解（之后回溯找下一组解）2.若尚未求得解时已无物品可选，则从栈顶退出最近装入的物品号（假设为k）,之后继续从第k+1件物品起挑选。结束条件：栈S空并且物品号k为最后一件物品求解过程中栈的状态变化：

依次将“0”和“1”入栈(表示将体积为1的0号物品和体积为8的1号物品装入背包)，此时背包尚未装满，而其余编号为2,3,4,5的物品都因为体积“太大”而不能装入，则将栈顶的“1”退出(表示从背包中取出体积为8的1号物品)，之后依次将“2”和“3”入栈(表示将体积为4的2号物品和体积为3的3号物品装入背包)，此时因4号物品“太大”不能装入，则弃置一边，而装入5号物品，即“5”入栈，此时背包正好装满，至此求得一组解。为了继续求其它解，令“5”出栈，因没有其他可选物品，则“3”(从栈顶退出最近装入的“3”)继续出栈，之后“4”继续入栈，求得第2组解。依次类推，直至求得全部解。0102350240250340350450515235242534535455背包问题求解过程中栈的状态变化情况算法4.3已知n件物品的体积分别为w[0],w[1],…,w[n-1]，背包的总体积为T,本算法输出所有恰好能装满背包的物品组合解。184352012345voidknapsack(intw[],intT,intn){SqStackS;intm=0;

InitStack(S);intk=0;//从第0件物品考察起

do{while(T>0&&k<n){if(T-w[k]>=0){Push(S,k);T-=w[k];}

//第k件物品可选，则k入栈,背包剩余体积减少

k++;//继续考察下一件物品

}//whileif(T==0){m++;StackTraverse(S);}

//输出一组解，之后回溯寻找下一组解

Pop(S,k);T+=w[k];//退出栈顶物品背包剩余体积增w[k]k++;//继续考察下一件物品

}while(!StackEmpty(S)||k!=n);

cout<<"总共有"<<m<<"组装法"<<endl;}//knapsackvoidmain(){intw[10]; intt;

cout<<"放入背包的总重量\n";

cin>>t;

cout<<"放入10件物品各自的重量\n";

for(inti=0;i<10;i++)

cin>>w[i];knapsack(w,t,10);}//main例4.4表达式求值任何一个表达式都是由操作数、运算符和界限符组成。限于二元运算符的表达式定义:

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

操作数::=简单变量|表达式简单变量::=标识符|无符号整数在计算机中,表达式的三种标识方法：设Exp=S1+

OP

+S2则称

OP

S1

S2

为前缀表示法

S1

OP

S2

为中缀表示法

S1

S2

OP

为后缀表示法例如:

Exp=ab

+

(cd/e)f前缀式:+

ab

c/def中缀式:ab

+

cd/ef后缀式:ab

cde/f

+

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

每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。如何从后缀式求值？

先找运算符，再找操作数例如：

abcde/f+abd/ec-d/e(c-d/e)f//算法4.4：函数返回由后缀式suffix表示的表达式的运算结果//Operate(s1,op,s2):

返回s1和s2进行OP运算的结果//OpMember(char

ch):为自定义bool型函数,若ch是运算符,则返回TRUE,否则返回FALSE.doubleevaluation(charsuffix[]){ch=*suffix++;

InitStack(S);//设置空栈Swhile(ch!='#'){if(!OpMember(ch))

Push(S,ch);//非"运算符"入操作数栈

else{Pop(S,b);Pop(S,a);//退出栈顶两个操作数

Push(S,Operate(a,ch,b));

//作相应运算，并将运算结果入栈

}//if

ch=*suffix++;//继续取下一字符

}//while

Pop(S,result);returnresult;}//evalution后缀式“35684/-7+#”的演算过程如下所示：35

684/-7

+#355533=1515684/48=2482-2266=4477744=2828+2815=4343result43如何从原表达式求得后缀式？分析“原表达式”和“后缀式”中的运算符:原表达式:

a+b

cd/e

f

后缀式:

abc+de/f

原表达式中的运算符在后缀式中出现的位置取决于它本身和后一个运算符之间的“优先关系”。按算术运算的规则，设置运算符优先数：运算符#（+-）/*↑(乘幂)优先数-10112223每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。从原表达式求得后缀式的规律为：1)设立运算符栈2)设表达式的结束符为“#”,预设运算符栈的栈底为#”；3)

若当前字符是操作数，则直接发送给后缀式。4)

若当前运算符的优先数高于栈顶运算符,则进栈；否则，退出栈顶运算符发送给后缀式；5)

若当前字符为结束符,则自栈顶至栈底依次将栈中所有运算符发送给后缀式；6)

“(”对它之前后的运算符起隔离作用，若当前运算符为“(”时进栈；7）“)”可视为自相应左括弧开始的表达式的结束符，则从栈顶起，依次退出栈顶运算符发送给后缀式直至栈顶字符为“(”止。算法4.5voidtransform(charsuffix[],charexp[]){//从合法的表达式字符串exp求得其相应的后缀式字符串suffix，

//precede(a,b)判别运算符的优先程度，当a的优先数≥b的优先

//数时，返回1，否则返回0

InitStack(S);Push(S,'#');//预设运算符栈的栈底元素为'#'p=exp;

ch=*p;k=0;while(!StackEmpty(S)){if(!OpMember(ch))

Suffix[k++]=ch;//操作数直接发送给后缀式

else

{switch(ch){case'(':Push(S,ch);break;//左括弧一律入栈

case')':{Pop(S,c);while(c!='(')

//栈顶至左括弧之前的运算符发送给后缀式

{Suffix[k++]=c;Pop(S,c)}break;}default:{while(GetTop(S,c)&&(precede(c,ch)))

{Suffix[k++]=c;Pop(S,c);}

//将栈中所有优先数不小于当前运算符优先数的运算符

//发送给后缀式

if(ch!='#')Push(S,ch);//优先数大于栈顶的运算符入栈

break;}//default

}//switch}//elseif(ch!='#')ch=*++p;}//while

Suffix[k]='\0';//添加字符串的结束符}//transform表达式“a(b(c+d/e)-f)#”转换成后缀式的演算过程如下所示：a(b(c+d/e)-f)##a(b(c+d/e//++-f-#int

precede(chara,charb)

//若a的优先数≥b的优先数则返回真,否则返回假{if(b=='#'||b=='(')return1;

if(a=='^') return1;

if((a==‘*’||a==‘/’)&&(b==‘-’||b==‘+’))return1;

if((a=='*'||a=='/')&&(b=='*'||b=='/'))return1;

if((a=='+'||a=='-')&&(b=='-'||b=='+'))return1;return0;}例4.5递归函数实现当在一个函数的运行期间调用另一个函数时,在运行该被调用函数之前，需先完成三项任务：

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

为被调用函数的局部变量分配存储区；

将控制转移到被调用函数的入口。

从被调用函数返回调用函数之前，应该完成下列三项任务：保存被调函数的计算结果；释放被调函数的数据区；

依照被调函数保存的返回地址将控制转移到调用函数.多个函数嵌套调用的规则是：后调用先返回此时的内存管理实行“栈式管理”例如：

voidmain()voida()voidb(){…{…{a();b();………}//main}//a}//bmain的数据区函数a的数据区函数b的数据区递归函数执行的过程可视为同一函数进行嵌套调用递归工作栈：递归程序执行过程中占用的数据区。递归工作记录：每一层的递归参数合成一个记录。当前活动记录：栈顶记录指示当前层的执行情况。当前环境指针：递归工作栈的栈顶指针。试利用栈编写计算下列递归函数的非递归形式的算法：例如:g(3,4)=g(2,8)+4=(g(1,16)+8)+4=((g(0,32)+16)+8)+4=((0+16)+8)+4=28从上述计算过程可以看出，为了计算g(3,4)首先应该先计算g(2,8),而g(2,8)的值也是未知的，接下来要求g(2,8)，类似的应先计算g(1,16),以此类推，计算g(0,32)的值为0，再将其值依次返回代入即可。

此时发现，先调用的函数，后得出结果，正好和栈的特性相符。为了便于管理，可将递归函数执行期间使用的数据存储区设成一个栈，栈顶的数据恰为当前层递归函数使用的参数。例如在此例中，只要在栈中保留2个参数值（m,n）即可。栈顶的任务是当前最迫切要完成的任务，其它任务需完成的“迫切程度”依自栈顶至栈底的次序排列。过程：首先将参数(m,n)入栈，表示当前要计算g(m,n)的值，如果这项任务比较简单，可以直接进行，则计算后出栈，并将计算结果返回。如果这项任务比较复杂，一时难以完成，则暂且搁置一边，先完成计算g(m-1,2n)+n的任务，即将参数(m-1,2n)入栈，依此类推。由此得出计算g(m,n)函数值的非递归形式的算法.首先定义栈的元素类型：typedef

struct{int

mval;

int

nval;}ElemType;int

g(intm,intn){ElemTypee;SqStacks;intu;

Initstack(s);

e.mval=m;e.nval=n;

Push(s,e);//m,n入栈

while(e.mval>0){e.mval--;e.nval*=2;

Push(s,e);//m-1,2n入栈

}Pop(s,e);u=0;//按定义计算u=g(m,n)

while(!StackEmpty(s)){Pop(s,e);u=u+e.nval;}returnu;}例题4.5:

利用栈S求Ackerman函数的值例如:A(3,1,1)=A(2,A(3,1,0),1)(A(3,1,0)=1)=A(2,1,1)=A(1,A(2,1,0),1)(A(2,1,0)=0)=A(1,0,1)=A(0,A(1,0,0),0)(A(1,0,0)=x=0)=A(0,0,0)(A(0,0,0)=x+1=1)=1定义栈的元素类型：typedef

struct{int

nval;

int

xval;

int

yval;}ElemType;算法4.6intAckerman(intn,intx,inty){//利用栈S求Ackerman函数的值，返回Ackerman(n,x,y)

SqStackS;ElemTypee;

intu;

InitStack(S);

e.nval=n;e.xval=x;e.yval=y;

Push(S,e);//(n,x,y)进栈

do{GetTop(S,e);while(e.nval!=0&&e.yval!=0){e.yval--;

Push(S,e);//新的参数值(n,x,y-1)进栈;}

Pop(S,e);//退出栈顶元素

u=value(e.nval,e.xval,e.yval);//按定义计算

if(!StackEmpty(S)){Pop(S,e);//退出栈顶元素

e.nval--;e.yval=e.xval;e.xval=u;Push(S,e);//新的参数值(n-1,u,x)进栈

}}while(!StackEmpty(S));returnu;//返回计算结果}//Ackermanintvalue(intn,intx,inty){if(n==0)return(x+1);elseswitch(n){case1:returnx;case2:return0;case3:return1;default:return2;}}//value320321计算A(3,2,1)栈的变化情况:210211212100101212110111000212n=3,y=0返回1n=2,y=0返回0n=1,y=0返回xn=0,y=0返回x+1011n=1,y=0返回xn=0返回x+1结果:24.3队列4.3.1队列的结构特点和操作1.队列的定义

队列(Queue)是一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，在队列中，允许插入的一端叫做队尾(rear)，队尾插入元素;允许删除的一端则称为队头(front)，队头删除元素。队列的图示：a1a2a3…an-1an出队列入队列队头元素队尾元素队列具有先进先出(FistInFistOut，缩写为FIFO)的特性。2.基本操作：

InitQueue(&Q)

构造一个空队列QDestroyQueue(&Q)

销毁QClearQueue(&Q)

将Q清为空队列QueueEmpty(Q)

若Q为空队列则返回TRUE,否则返回FALSEQueueLenght(Q)

返回Q的元素个数,即队列的长度GetHead(Q,&e)Q为非空队列,用e返回Q的队头元素EnQueue(&Q,e)

队列Q存在,插入元素e为Q的队尾元素a1a2ane……DeQueue(&Q,&e)Q为非空队列,删除Q的队头元素,并用e返回其值。a1a2an……

QueueTraverse(Q)

从队头到队尾,依次输出每个数据元素入队列：在队尾插入元素的操作；出队列：删除队头元素的操作。4.3.2队列的表示和操作的实现1.链队列用链表表示的队列简称为链队列。链表的表头可以作为队头（删除），链表的表尾可以作为队尾（插入）一个链队列显然需要两个分别指示队头和队尾的指针。由于队列中有队头和队尾的两个指针，为了操作方便，附加一个头结点。a1∧anfrontrear……队头指针始终指向这个附加的头结点；队尾指针始终指向真正的队尾元素结点。{非空队列空队列：只含一个头结点的队列，并且头尾指针均指向头结点。∧frontrear链队列的结点类型和链队列定义如下:typedef

struct

QNode

{QElemTypedata;

struct

QNode*next;}LNode,*QueuePtr;//结点类型typedef

struct

//链队列类型{QueuePtrfront;//队头指针

QueuePtrrear;//队尾指针}LinkQueue;LinkQueueQ;封装后的完整链队列图示如下:非空队列a1∧an…Q.frontQ.rear空队列Q.frontQ.rear∧链队列的基本操作实现:1)构造一个空队列QvoidInitQueue(LinkQueue&Q){Q.front=Q.rear=newLNode;

Q.front->next=NULL;}2)销毁队列QvoidDestroyQueue(LinkQueue&Q){LNode*p;

while(Q.front){p=Q.front->next;deleteQ.front;

Q.front=p;}}//DestroyQueue3)清空队列QvoidClearQueue(LinkQueue&Q){LNode*p,*q;p=Q.front->next;q=Q.front;

while(p){q->next=p->next;deletep;p=q->next;}

Q.rear=Q.front;}//ClearQueue4)入队一个元素插入元素e为Q的新的队尾元素voidEnQueue(LinkQueue&Q,QElemTypee){QueuePtrp=newLNode;p->data=e;p->next=NULL;

Q.rear->next=p;

Q.rear=p;}//EnQueue5)返回队头元素若队列不空，用e返回其值bool

GetHead(LinkQueueQ,QElemType&e){if(Q.front==Q.rear)returnfalse;e=Q.front->next->data;returntrue;}//GetHead6)出队一个元素,若队列不空,则删除Q的队头，用e返回其值bool

DeQueue(LinkQueue&Q,QElemType&e){QueuePtrp;if(Q.front==Q.rear)returnfalse;p=Q.front->next;e=p->data;

Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;//判断删除的是否队尾元素

deletep;returntrue;}//DeQueue7)从队头到队尾依次输出每个元素voidQueueTraverse(LinkQueueQ){QueuePtrp=Q.front->next;

while(p){cout<<p->data<<“”;p=p->next;}

cout<<endl;}8)求队列中元素个数int

QueueLength(LinkQueueQ){QueuePtrp=Q.front->next;

intk=0;

while(p){k++;p=p->next;}returnk;}2.循环队列—顺序映象利用顺序存储结构分配实现队列。顺序队列类型定义中:

用一维数组描述队列中数据元素的存储区域elem

数组的最大容量quenesize;

约定的扩充容量incrementsize

设立两个指针front和rear分别指示“队头”和“队尾”的位置。为了叙述方便，在此规定：初始化空队列时，令front=rear=0,每当插入一个新的队尾元素后,尾指针rear增1；每当删除一个队头元素之后，头指针front增1。在非空队列中，头指针始终指向队头元素，尾指针指向队尾元素的“下一个”位置。顺序队列中进行入队和出队运算时,队列中的元素及头尾指针的变化。图中队列的最大空间为6.rear空队列012345frontrearj1,j2,j3入队012345frontj1j2j3rearj1,j2相继出队012345j3rearfrontj4,j5,j6入队012345j3j6j5j4front(a)(b)(c)(d)假溢出：当队列处于(d)状态时,不能进行入队操作,而此时队列的实际可用空间并未占满，浪费空间。为了克服这个缺点，通常采用的方法是：设想顺序队列是一个首尾相接的环状空间，称为循环队列。循环队列(CircularQueue)Q.frontQ.rear6maxsize-1012345j6j3

j4

j5

…….front假设为循环队列：(e)状态下，队尾指针rear将指向循环队列的首址，即rear=0。则元素j7,j8,j9,j10入队，队尾指针rear依次增1，此时队满(rear==front)。若j5,j6相继出队，此时队空（rear==front）。rear一般情况012345rear队满012345frontj7j8j9rear空队列012345rearfront队满状态循环队列012345j9j6j5front(a)(b)(c)(d)j6j5j10j5j6j8j7问题：队空、队满的状态是头尾指针都相同。可见，对于循环队列不能以头尾指针是否相同来判别队列“满”或“空”。解决方法：1.附设一个标志位用以区别队空或队满。2.队列中少用一个元素空间，规定“队尾指针在队头指针的前一个位置（指环状队列中），为队列呈“满”状态的标志。循环队列中头尾指针的“依循环意义增1”的实现：用“模”运算来实现的。通过取“模”，头指针和尾指针就可以在顺序表空间内按头尾衔接的方式循环移动。模运算形式如下：假设循环队列的空间大小为m,头指针为front,尾指针为rear；头指针循环意义加1：front=(front+1)%m尾指针循环意义加1:rear=(rear+1)%m队满判断条件：front==(rear+1)%m队空判断条件：front==rear队中元素个数:(rear-front+m)%m循环队列类型定义：constQUEUE_INIT_SIZE=100;constQUEUEINCREMENT=10;typedef

int

QElemType;typedef

struct{QElemType*elem;

intfront;

intrear;

int

queuesize;

int

incrementsize;}SqQueue;SqQueueQ;//定义一个队列1)循环队列初始化voidInitQueue(SqQueue&Q,int

maxsize=QUEUE_INIT_SIZE,

int

incresize=QUEUEINCREMENT){Q.elem=newQElemType[maxsize+1];//多分配一个存储区

Q.front=Q.rear=0;

Q.queuesize=maxsize+1;Q.incrementsize=incresize;}//InitQueue2)判别空队列bool

QueueEmpty(SqQueueQ){if(Q.front==Q.rear)returntrue;elsereturnfalse;}3)判别满队列bool

QueueFull

(SqQueueQ){if(Q.front==(Q.rear+1)%Q.queuesize)returntrue;elsereturnfalse;}//QueueFull4)求队列长度int

QueueLength(SqQueueQ){return(Q.rear-Q.front+Q.queuesize)%Q.queuesize;}5)取队头元素bool

GetHead(SqQueue

Q,QElemType&e){if(Q.front!=Q.rear){e=Q.elem[Q.front];returntrue;}elsereturnfalse;}6)出队操作bool

DeQueue(SqQueue&Q,QElemType&e){if(Q.front==Q.rear)returnfalse;e=Q.elem[Q.front];

Q.front=(Q.front+1)%Q.queuesize;returntrue;}7)输出队列中已有元素voidQueueTraverse(SqQueueQ){for(intk=0;k<(Q.rear-Q.front+Q.queuesize)%

Q.queuesize;k++)

cout<<Q.elem[(Q.front+k)%Q.queuesize]<<"";

cout<<endl;}8)入队操作voidincrementQueuesize(SqQueue&Q){intsize=Q.queuesize+Q.incrementsize;

QElemType*a=newQElemType[size];

for(intk=0;k<Q.queuesize;k++){a[k]=Q.elem[Q.front];

Q.front=(Q.front+1)%Q.queuesize;}deleteQ.elem;

Q.elem=a;

Q.front=0;Q.rear=Q.queuesize-1;Q.queuesize=size;}//incrementQueuesizevoidEnQueue(SqQueue&Q,QElemTypee){if(Q.front==(Q.rear+1)%Q.queuesize)

incrementQueuesize(Q);

Q.elem[Q.rear]=e;

Q.rear=(Q.rear+1)%Q.queuesize;}//EnQueue头指针加1：

Q.front=(Q.front+1)%Q.queuesize尾指针加1：

Q.rear=(Q.rear+1)%Q.queuesize队满判断条件：Q.front==(Q.rear+1)%Q.queuesize队空判断条件：Q.front==Q.rear队中元素个数：(Q.rear-Q.front+Q.queuesize)%Q.queuesize4.4队列应用举例二项式系数值（杨辉三角(a+b)i）第1行11第2行121第3行1331第4行14641分析第

i行元素与第i+1行元素的关系：除第1和最后一个数之外，其余的数为上一行中位其左右的两数之和。依次存储第i=3行的数据为了计算出下一行的数据，需保存本行数据。先保存的数据先取出计算，先进先出，可用队列。为计算方便，在两行之间添加一个“0”作为行界，则计算第k+1行时，头指针指向第k行的“0”，尾指针指向第k+1行的“0”。输出n行,队列的最大容量为n+2。1011201213013314014641初始队列：011利用“循环队列”计算二项式系数的过程0123450110s+e=Q.frontQ.rear011输出：Q.front11Q.rear11Q.front22Q.rear11Q.front011Q.rear0Q.rear0Q.front1111Q.rear1Q.front23223Q.rearQ.front1133Q.rear1Q.front011Q.rear0Q.reardo{

DeQueue(Q,s);

GetHead(Q,e);if(e!=0)

cout<<e;

EnQueue(Q,s+e);}while(e!=0);voidYanghui(intn){SqQueueQ; int

i,k;int

s,e;

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

cout<<'';

cout<<'1'<<endl;InitQueue(Q,n+2);

EnQueue(Q,0);

EnQueue(Q,1);EnQueue(Q,1);k=1;while(k<n){for(i=1;i<=n-k;i++)cout<<'';

EnQueue(Q,0);

do{//输出第k行，计算第k+1行

DeQueue(Q,s);GetHead(Q,e);if(e)cout<<e<<'';elsecout<<endl;

EnQueue(Q,s+e);}while(e!=0);k++;}

DeQueue(Q,e);while(!QueueEmpty(Q)){DeQueue(Q,e);cout<<e<<'';}//单独处理第n行的值的输出}011Q.frontQ.rear0121Q.frontQ.rear13310Q.frontQ.rear410146Q.frontQ.rear101510105Q.frontQ.rear10161520156Q.frontQ.rear

1112113311464115101051例4.7:为运动会比赛安排日程，即划分最小子集问题运动会设N个比赛项目,每位运动员可参加1-3个项目。问如何安排比赛日程,使每位运动员参加的项目不安排在同一时间进行，以使总的比赛日程最短。

划分子集:N个比赛项目构成大小为n的集合A，有同一运动员参加的项目抽象为“冲突”关系。设n=9,则A={0,1,2,3,4,5,6,7,8},7名运动员分别参加的项目为:(1,4,8)、(1,7)、(8,3)、(1,0,5)、(3,4)、(5,6,2)和(6,4)。则构成一个冲突关系的集合:R={(1,4)、(1,8)、(4,8)、(1,7)、(8,3)、(1,0)、(1,5)、(0,5)、(3,4)、(5,6)、(5,2)、(6,2)、(6,4)}。划分子集问题即为将集合A划分为k个互不相交的子集A1,A2,…,Ak(k≤n),