第4章 栈和队列

1数据结构及应用算法教程(修订版)配套课件2第4章栈和队列

栈和队列是对线性表的某些操作加以限定而派生出的结构。它们的操作本身并不难掌握，难点是理解栈和队列的应用思想、掌握其算法的设计技巧。讲授本章课程大约需6课时。

3

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

线性表栈队列Insert(L,

i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)

1≤i≤n栈和队列是两种常用的数据类型43.1栈3.2栈的应用举例3.3队列3.4队列应用举例53.1栈一、栈的结构特点和操作二、栈的表示和操作的实现6一、栈的结构特点和操作7栈(Stack)的定义a2a1a4a3栈底栈顶

栈(stack)是限定只能在表的一端进行插入和删除的线性表。在栈中,

允许插入和删除的一端称为“栈顶”(top),不允许插入和删除的一端称为“栈底”(bottom)。8InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S)栈的基本操作:(9个基本操作）

比一般线性表少了三种操作求前驱，求后继，定位(LocateElem)9

InitStack(&S)(初始化)

操作结果：构造一个空栈S。

DestroyStack(&S)

初始条件：栈S已存在。

操作结果：栈S被销毁。10

StackEmpty(S)（判空）

初始条件：栈S已存在

操作结果：若栈S为空栈，

则返回TRUE，

否则FALSE。11

StackLength(S)（栈长）

初始条件：栈S已存在。

操作结果：返回S的元素个数，

即栈的长度。12

GetTop(S,&e)（取栈顶元素）

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

操作结果：用e返回S的栈顶元素。a1a2an……13

ClearStack(&S)（清空）

初始条件：栈S已存在。

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

14

Push(&S,e)（入栈-插入）

初始条件：栈S已存在。

操作结果：插入元素e为

新的栈顶元素。

a1a2ane……15

Pop(&S,&e)（出栈-删除）

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

操作结果：删除S的栈顶元素，

并用e返回其值。a1a2anan-1

……16

顺序栈

链栈二、栈的表示和操作的实现17

顺序栈

类似于线性表的顺序表示法，指向表尾的指针可以作为栈顶指针。栈顶指针top---不是地址，而是数组的下标，其值是栈顶元素的下标。18//-----栈的顺序存储表示

-----

#defineSTACK_INIT_SIZE100;

#defineSTACKINCREMENT10;

typedefstruct{

SElemType

*elem;

inttop;----栈顶下标,顺序表是length

intstacksize;

intincrement;

}

SqStack;补充：length=top+1；19

void

InitStack_Sq(SqStack&S){

//构造一个空栈S

S.elem=newSElemType[maxsize];//表示栈已经存在

S.top=-1;//栈为空

S.stacksize=maxsize;S.incrementsize=incresize;

//对栈的其他成员附初值}20void

Push_Sq(SqStack&S,SElemTypee){

if

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

incrementStacksize(S);//如果顺序栈的空间已满，应为栈扩容

S.elem[++S.top]=e;//在栈顶插入数据元素}S.elem[++S.top]=e;可以改为如下两句：S.top++;S.elem[S.top]=e;总结：先改变top（top+1），再赋值。21bool

Pop_Sq(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，

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

//否则返回FALSE。

if

(S.top

==

-1)return

FALSE;e=S.elem[S.top-

-];

return

TRUE;}e=S.elem[S.top-

-];此语句可以改为：e=S.elem[S.top];S.top-

-；总结：先赋值再改变top（top-1）22栈顶指针∧a1an注意:链栈中指针的方向an-1

链栈top233.2栈的应用举例

栈在算法设计中占有重要的地位，运用的技巧也性也较高，本节安排五个例子来讨论栈的使用。24例一数制转换例二括号匹配的检验例三背包求解例四表达式求值例五递归函数的实现25

例一、数制转换

算法基于数制转换公式：

N=(Ndivd)×d+Nmodd

26

例如：（1348)10=(2504)8

其运算过程如下：

NNdiv8Nmod8

13481684

168210

2125

202计算顺序输出顺序27void

conversion()

{InitStack(S);

cin>>N;

while

(N)

{

Push(S,N%8);N=N/8;

}

while

(!StackEmpty(S)){

Pop(S,e);

cout<<e;

}}

//conversion28例二、括号匹配的检验假设在表达式中（［］（））或［（［］［］）］等为正确的格式，［（］）或（［（））或（（）］)均为不正确的格式。

则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。29分析可能出现的不匹配的情况:到来的右括弧并非是所“期待”的；例如：考虑下列括号序列：

[([][])]12345678到来的是“不速之客”；直到结束，也没有到来所“期待”的括弧。30算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”

，否则表明不匹配。3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。31boolmatching(charexp[]){

intstate=1;ch=*exp++;

while(ch!=‘#’&&state){

switchofch{

case

左括弧:{Push(S,ch);i++;break;}//左括弧进栈

case”)”:{//

匹配‘）’

if(!StackEmpty(S)&&GetTop(S)=‘(‘)Pop(S,e);

else

state=0;

break;}

case”]”:{……}//

匹配‘]’

}

ch=*exp++;

}

if(StackEmpty(S)&&state)

return

TRUE;

elsereturn

FALSE;

}32例三.背包问题:

假设有n件体积分别为w1,w2,…wn的物品和一个能装载体积为T的背包.能否从n件物品中选择若干件恰好装满背包,

即

wi1+wi2+…+wik=

T,则背包问题有解；否则无解.

以W(1,8,4,3,5,2),

T=10为例

(1,4,3,2

),

(1,4,5

),(8,2)和(3,5,2)是其解。3354381435822WT=101+4+3+2=10

利用回溯的算法思想求解背包问题

从背包中取出物品再继续搜索的策略称之为回溯，其规则是“后进先出”，即背包以栈的操作完成求解。34voidknapsack(intw[],intT,int

n){//T在算法中是剩余的容积，初值为背包的体积

InitStack(S);k=0;

do{

while(T>0&&k<n){

if

(T-w[k]>=0){

//第k件物品可以进栈

Push(S,k);T─

=w[k];

}k++;

}

if(T==0)StackTraverse(S);//输出一个解

Pop(S,k);

T+=w[k];//退出栈顶物品

k++;

}while

(!StackEmpty(S)||k<n);}35

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

表达式::=

操作数运算符操作数操作数::=

简单变量|

表达式简单变量::=

标识符|

无符号整数例四、表达式求值例如:exp=ab

+

(7d/e)f36

表达式的三种标识方法：设

Exp=S1OP

S2则称OP

S1S2

为前缀表示法

S1

OP

S2

为中缀表示法

S1

S2

OP

为后缀表示法

37例如:Exp=ab

+

(cd/e)f前缀式:+

ab

c/def中缀式:ab

+

cd/ef后缀式:ab

cde/f

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

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

abcde/f+abd/ec-d/e(c-d/e)f先找运算符，再找操作数:Exp=ab

+

(cd/e)f39后缀表达式：算法思想abcde/f+#1、遇到操作数入栈，2、遇到操作符就出栈（连续出两个栈顶元素），进行计算，将结果压栈3、直到表达式扫描完毕。难点：如何将中缀表达式转换为后缀表达式（树的知识。）40Computy(suffix[]){Stacks;i=0;InitStack(&x);while(suffix[i++]!=‘#’){ifsuffix

[i]是操作数吗？

push(&s,suffix[i]);else{x=pop(&s,&e);y=pop(&s,&e);N=operate(x,y,suffix[i]);push(&s,N);}//else//i++;}//whileret=pop(&s,&e);return(ret);}suffix[]=abcde/f+#41ifsuffix

[i]是操作数吗?if（‘0’<=suffix

[i]

<=‘9”）;扩展思考：如果是多位数的数字如何判断？42N=operate(x,y,suffix[i]);//是操作符进行运算=========================operate(x,y,suffix[i]){switch(suffix[i]){case’+’:N=y+x;returnN;break;case’-’:N=y-x;returnN;break;case’*’:N=y*x;returnN;break;case’\’:N=y\x;returnN;break;default:returnERROR;}//switch}43

如何从原表达式求得后缀式？

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

cd/e

f

后缀式:abc+de/f

44运算符优先数表

运算符#（+–）/^优先数-1011222345从原表达式求得后缀式的规律为：1)

设立操作符栈；2)设表达式的结束符为“#”，

予设运算符栈的栈底为“#”；3)

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

若当前运算符的优先数大于栈顶运算符,则进栈；5)

否则（小于等于），退出栈顶运算符发送给后缀式；6)“(”对它之前后的运算符起隔离作用，

“)”可视为自相应左括弧开始的表达式的结束符。46从原表达式求得后缀式的规律为：设立一数组放原表达式：exp[]=原表达式设立操作符栈；S

设立一个数组放后缀表达式suffix[]

2)设表达式的结束符为“#”，

予设运算符栈的栈底为“#”；//push（&s,“#”)准备工作：47从原表达式求得后缀式的规律为：3)

若当前字符是操作数，则直接发送给后缀式。if(ch)为操作数，suffix[k++]=ch;逐个读取原表达式的字符，进行对应处理：分别考虑操作数，操作符（考虑优先级），左括号（，右括号）的处理方法。若为操作符：48从原表达式求得后缀式的规律为：若为操作符：4)

若当前运算符的优先数高于栈顶运算符,则进栈；5)

否则，退出栈顶运算符发送给后缀式；几种情况：情况1：符号为+-*/:比较优先级，确定是进栈还是给后

缀表达式情况2：(-----进栈情况3：）---）不进栈，

自栈顶至（之前的运算符出栈并发给后缀式，

）出栈6)“(”对它之前后的运算符起隔离作用，

“)”可视为自相应左括弧开始的表达式的结束符。49从原表达式求得后缀式的规律为：1)

设立操作符栈；2)设表达式的结束符为“#”，

予设运算符栈的栈底为“#”；3)

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

若当前运算符的优先数高于栈顶运算符,则进栈；5)

否则，退出栈顶运算符发送给后缀式；6)“(”对它之前后的运算符起隔离作用，

“)”可视为自相应左括弧开始的表达式的结束符。50voidtransform(charsuffix[],charexp[]){InitStack(S);Push(S,#);p=exp;ch=*p;k=0；

while(!StackEmpty(S)){

if(!opmenber(ch))suffix[k++]=ch;

else

{

}

if(ch!=#){p++;ch=*p;}}//whilesuffix[k]=\0;}//transform……//如果为操作符看后面swich部分}51switch(ch)

{

case

(

:Push(S,ch);break;//左括号入栈

case

)

:

Pop(S,c);自顶到（全部出栈给后缀数组

while(c!=

()

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

break;

defult:{//其他情况比较优先级

while(Gettop(S,c)&&

(precede(c,ch)))

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

if(ch!=

#)Push(S,ch);

break;

}

}//switchC为栈顶操作符，ch为当前操作符precede（c,ch）return1为ch<=cintopermanber(ch){if(‘0’<=ch<=‘9’;}return0;elsereturn1;说明：为操作数，则返回0intprecede(c,ch)c为栈顶的运算符；ch为当前的运算符当ch<=c,则返回1，反之(ch>c)返回0{Switch(ch)case+:case–:{if（

栈顶c是#或者（），return0;//ch>celse返回1;//其他情况ch<=c;}case*:case/:{if（

栈顶c是*或者/）retrun1;//ch<=celseretrun0;//ch>c}}//switch如果表达式是：234+56/2*11-8怎么处理多位数？55例五、实现递归

将所有的实在参数、返回地址等信息传递给被调用函数保存；--保护现场为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。

当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：56保存被调函数的计算结果；释放被调函数的数据区；（局部变量）依照被调函数保存的返回地址将控制转移到调用函数。

从被调用函数返回调用函数之前，应该完成下列三项任务：57多个函数嵌套调用的规则是：此时的内存管理实行“栈式管理”后调用先返回！例如：voidmain(){voida(){voidb(){………

a();

b();

……}//main}//a}//bMain的数据区函数a的数据区函数b的数据区递归的定义：一个函数自己直接或间接调用自己。对计算机而言，某函数调用别的函数与调用自己本身，没有不同，至于难以理解，那是人的思维而已。59

递归函数执行的过程可视为同一函数进行嵌套调用，在执行递归函数的过程中也需要一个“递归工作栈”。作用：（1）将递归调用的实际参数、返回地址传递给下一层执行的递归函数；（2）保存本层的参数和局部变量，以便从下一层返回时重新使用它们。60A(n,x,y)=x+1,n=0x,n=1,y=00,n=2,y=01,n=3,y=02,n≥4,y=0A(n-1,A(n,x,y-1),x)，n≠0,y≠0Ackerman函数定义：用实例模仿编译程序解决递归问题的过程（无需掌握）61A(3,2,1)=A(2,A(3,2,0),2)=A(2,1,2)A(3,2,0)=1=A(1,A(2,1,1),1)=A(1,A(1,A(2,1,0),1),1)=A(1,A(1,0,1),1)A(2,1,0)=0=A(1,A(0,A(1,0,0),0),1)=A(1,A(0,0,0),1)A(1,0,0)=x=0=A(1,1,1)A(0,0,0)=x+1=1=A(0,A(1,1,0),1)=A(0,1,1)A(1,1,0)=x=1=2A(0,1,1)=x+1=2

Ackerman函数A(3,2,1)的递归运行模拟321320212211210101100000111110011

递归过程的实现递归进层（i→i+1层）系统需要做三件事：

(1)保留本层参数与返回地址（将所有的实在参数、返回地址等信息传递给被调用函数保存）；

(2)给下层参数赋值（为被调用函数的局部变量分配存储区）；

(3)将程序转移到被调函数的入口。

而从被调用函数返回调用函数之前，递归退层（i←i+1层）系统也应完成三件工作：

(1)保存被调函数的计算结果；

(2)恢复上层参数（释放被调函数的数据区）；(3)依照被调函数保存的返回地址，将控制转移回调用函数。设计递归的条件及方法：一、将问题化为原问题的子问题的求解（砍头去尾，中间切）假设n个规模问题，判断：1、砍头：取第一个元素，n-1个元素与原问题是否相似2、去尾：剩n-1个问题与原问题是否相似3、中间切：将原问题一分为2，Q1，Q2与原问题是否相似（排序大多用此）二、终止条件：设计递归出口，确定终止条件(能在最小值上有直接解，并作为终止条件条件，告知何时停止递归)例：1+2+3+…..+n条件满足否？(1)去尾1+2+…+(n-1)(2)终止条件：n==0，return0;

或n==1，retrun1;

或n==2，retrun3;intSum（n）{if(n==1)，total=1；

elsetotal=sum（n-1）+n

returntotal；}求阶乘：

n！=1*2*3*……*(n-1)*n去尾，与原问题相似终止条件：n=1时，result=1

intfunction（intn）{if（n==1）result=1；

elseresult=function（n-1）*n}Hanoi塔问题Hannoi的传说

相传在印度的贝纳雷斯有座大寺庙，寺庙内有一块红木板，上面插着三根钻石棒，在盘古开天地，世界刚创造不久之时，神便在其中的一根钻石棒上放了６４枚纯金的圆盘。

有一个叫婆罗门的门徒，不分日夜地向这座寺庙赶路，抵达后，就尽力将６４枚纯金的圆盘移到另一根钻石棒上。等到婆罗门完成这项工作，寺庙和婆罗门本身都崩溃了，世界在一声霹雳中也毁灭了。不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f⑴=1,f⑵=3,f⑶=7，且f(k+1）=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时，

f（64）=2^64-1=18446744073709551615

假如每秒钟一次，共需多长时间呢？一个平年365天有31536000秒，闰年366天有31622400秒，平均每年31556952秒，计算一下，18446744073709551615/31556952=584554049253.855年

这表明移完这些金片需要5845亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。汉诺塔问题：有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：每次只能移动一个圆盘；大盘不能叠在小盘上面。

提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。

问：如何移？最少要移动多少次？n个盘子,A->C去尾，前面n-1个盘子作为小问题，将n-1个盘子黏起来，就成了两个盘子，如何移呢？(D1是上面的小盘（假想成n-1个黏起来的盘），D2是下面的大盘)1、D1AB2.D2A->C3D1B->Chanoi(n,A,B,C)//A-C借助B{If（n=1）{

printf（“n从A移动C”）；return1；}else{hanoi（n-1，A,C,B）

printf（n,A-C）hanoi(n-1，B,A,C)}}723.3队列一、队列的结构特点和操作二、队列的表示和操作的实现73一、队列的结构特点和操作使用场合：用于仿真，服务窗口的设置是否合理74队列(Queue)的定义

队列(queue)是限定只能在表的一端进行删除，而在另一端插入的线性表。在队列中，允许删除的一端称为“队头”(front)，允许插入的一端称为“队尾”(rear)。

a1a2a3a4a5队头队尾75

InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q)队列的基本操作：76InitQueue(&Q)

操作结果：构造一个空队列Q。

DestroyQueue(&Q)

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

操作结果：队列Q被销毁，

不再存在。

77QueueEmpty(Q)

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

操作结果：若Q为空队列，

则返回TRUE，

否则返回FALSE。78

QueueLength(Q)

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

操作结果：返回Q的元素个数，

即队列的长度。79

GetHead(Q,&e)

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

操作结果：用e返回Q的队头元素。a1a2an……80

ClearQueue(&Q)

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

操作结果：将Q清为空队列。81

EnQueue(&Q,e)

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

操作结果：插入元素e为Q的

新的队尾元素。a1a2ane……82

DeQueue(&Q,&e)

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

操作结果：删除Q的队头元素，

并用e返回其值。a1a2an……83

链队列

循环队列二、队列的表示和操作的实现84

typedefstruct

QNode{//结点类型

QElemTypedata;

struct

QNode*next;

}QNode,*QueuePtr;

链队列85Q.frontQ.reartypedefstruct{//链队列类型

QueuePtrfront;//队头指针（指向头结点）

QueuePtrrear;//队尾指针（指向尾元素）}

LinkQueue;a1∧an…Q.frontQ.rear∧空队列86

void

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

Q.front=Q.rear=newQNode;

Q.front->next=

NULL;}产生一个空结点，并让front与rear都指向它。87

void

EnQueue_L(LinkQueue&Q,QElemTypee)

{//插入元素e为Q的新的队尾元素

p=

new

QNode;p->data=e;p->next=NULL;Q.rear->next=p;

Q.rear=p;}注意：链的变化；rear指向尾函数。88

bool

DeQueue_L(LinkQueue&Q,QElemType&e){//若队列不空，则删除Q的队头元素，

//用e返回其值,并返回TRUE；否则返回FALSE

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;//当原队列只有一个元素时，

要特殊处理

。

delete

p;

returnTRUE;}注意：释放删除的结点；只有一元素时的特殊处理；fornt始终指向头结点（不变）89#define

MAXQSIZE100//最大队列长度typedefstruct{

QElemType*elem;//动态分配存储空间

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

//指向队列头元素

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

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

int

queuesize;

int

incrementsize;}

SqQueue;

循环队列（顺序队列）少了队列长度queuelength，因为通过front与rear运算可得90由于插入删除分别在队尾和队头进行。思考：能否做到，用数组表示队列时，做到不频繁移动元素，并保持线性的特点？解决方法：移动front或者rear就可。问题：产生假溢（假满）解决方法：头尾相连，让数组形成一个环—循环数组（循环队列）。如何实现(取模实现)：rear=(rear+1)%queuesize(queuesize是队列/数组的最大容量)91循环队列：保留了数组存储的简单，且插入删除无须元素的移动。还有一个问题有待解决：队列满：front==rear;队列空：front==rear;按照算法的特性：算法要有确定性，不能出现歧义。92如何解决：1、设置标志当入队，使front==rear，则为满，当出队，使front==rear，则为空。2、牺牲一个内存单元，让空和满的判断条件都唯一。空：

front==rear满：（rear+1）%queuesize==front;93循环队列非循环队列入队rear=(rear+1)%queuesize;Rear=rear+1出队front==(front+1)%queuesize;Front=front+1队空rear==front；rear==front；队满(rear+1)%queuesize==front；rear==front；Rear+1=queuesize(rear-front+queuesize)%queuesize94abcdQ.elemQ.fronteQ.rearQ.front:

指向队头元素Q.rear:

指向队尾下一元素队列的入队和出队操作：95e01234567Q.frontQ.rear初态（空队）:Q.frontQ.rear队空:当头尾指针重合时:队为空9601234567acbQ.frontQ.rear队满状态的约定:acbQ.rear01234567Q.rearQ.frontabcdefg假满真满Q.rearQ.rear队满时还富裕一个单元的空间以区别“队空”和“队满”的条件9701234567abcQ.rearQ.frontQ.reard循环队列（按循环机制使用顺序空间）

front和rear都按逆时针操作98Q.rear=(Q.rear+1)Q.front=(Q.front+1)

通过头尾指针的循环使用,顺序空间即可当循环空间来使用，称循环队。循环使用指针在技术上是由取模实现的：%

MAXQSIZE;%

MAXQSIZE;99

void

InitQueue_Sq(SqQueue&Q){//构造一个空队列Q

Q.elem=

new

QElemType

[MAXQSIZE+1];

Q.queuesize=MAXQSIZE；

Q.front=Q.rear=0;

}100void

EnQueue_Sq(SqQueue&Q,ElemTypee){

//插入元素e为Q的新的队尾元素

if

((Q.rear+1)%MAXQSIZE==Q.front)

incrementQueuesize(Q);

//队列已满需扩容

Q.elem[Q.rear]=e;

Q.rear=(Q.rear+1)%

MAXQSIZE;}101void

DeQueue_Sq(SqQueue&Q,ElemType&e)

{

//若队列不空，则删除Q的队头元素，

//用e返回其值，并返回TRUE;否则返回FALSE

if(Q.front==Q.rear)

returnFALSE;e=Q.elem[Q.front];Q.front=(Q.front+1)%MAXQSIZE;

return

TRUE;}1023.4队列的应用举例利用循环队列求二项式系数（杨辉三角）杨辉三角形特点：1、头尾均为12、其他元素是上层相邻元素之和。问题描述：n为第n层，输出具有n层杨辉三角形。给第n-1层，如何产生第n层。假如知道第三层，1,3,3,1（已全部入队），如何产生第四层的数？1、每次出队一个元素x（三层的）2、读取一元素y=Gethead()3、x+y入队（第四层的元素），3、循环1-3。出队1；Gethead（）3；1+3=4，入队；出队3；Gethead（）3；1+3=6，入队；出队3；Gethead（）1；3+1=4，入队；在两行之间加上辅助变量0，作为行界值（为了便于编程）013310|0146410杨三角算法：1、根据杨三角第n-1层数产生编程，m=1（当前层数）2、每次从队列里面出队一个元素x，读取头元素y3、将x+y入队4、不断重复2,3，直到y=0；（小循环）5、不断重复1,2,3,直到m=n；（大循环）存在小问题：1、头尾问题；2、何时小循环结束106第1行11