第3章 栈和队列-1

DATA1065865ABCDEFG数据结构第3章栈和队列主讲：李泽平第3章栈和队列学习提要

掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。

2.熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法。

3.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。第3章栈和队列栈和队列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限定性的数据结构。3.1栈3.1.1栈的定义栈：限定只能在表的一端进行插入和删除的特殊的线性表设栈s=（a1，a2，...,ai，...，an），其中a1是栈底元素，an是栈顶元素。a1a2….an进栈出栈栈顶top栈底bottom3.1栈3.1.1栈的定义栈：限定只能在表的一端进行插入和删除的特殊的线性表

设栈s=（a1，a2，...,ai，...，an），其中a1是栈底元素，an是栈顶元素。栈顶（top)：允许插入和删除的一端；

约定top始终指向新数据元素将存放的位置。栈底（bottom):不允许插入和删除的一端。a1a2….an进栈出栈栈顶栈底

结论：后进先出（LastInFirstOut），简称为LIFO线性表。

举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。

下面我们先给出栈结构的基本操作：（1）初始化栈InitStack(S)

（2）入栈Push(S,item)

（3）出栈Pop(S,item)

（4）获取栈顶元素内容GetTop(S,item)

（5）判断栈是否为空StackEmpty(S)

栈中的运算：1.设置空栈；2.插入一个新的栈顶元素

3.删除栈顶元素；4.读取栈顶元素。设数组S是一个顺序栈，栈的最大容量stacksize=4，初始状态top=0

10S[4]2310bases[top]=xtop=top+1top

10

25

30S[4]2310topbasetop=top-1x=s[top]栈空10进栈30出栈S[4]2310Top=0top栈满

top=stacksize

10

25

30

40S[4]2310top=4basebase3.1.2栈的存储结构

顺序栈、链栈a2a1

a1a2top顺序栈：用顺序存储结构表示的栈。

顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量top指示栈顶位置，称为栈顶指针，它始终指向待插入元素的位置。设置一个简单变量base指示栈底位置，称为栈底指针，它始终指向栈底。·进栈算法#definestatcksize100int

push(ints[],intx,int*ptop){

inttop;top=*ptop;if(top==stacksize){printf(“overflow”);return(0);}else{s[top]=x;*ptop=++top;/*实际栈顶指针加1*/return(1);}}通过地址传递，用ptop带回实际栈顶指针a2a3a4987654321a10top·进栈算法#definestatcksize100int

push(ints[],intx,int*ptop){

inttop;top=*ptop;if(top==stacksize){printf(“overflow”);return(0);}else{s[top]=x;*ptop=++top;/*实际栈顶指针加1*/return(1);}}通过地址传递，用ptop带回实际栈顶指针a2a3a4

a5987654321a10top·进栈算法#definestatcksize100int

push(ints[],intx,int*ptop){

inttop;top=*ptop;if(top==stacksize){printf(“overflow”);return(0);}else{s[top]=x;

*ptop=++top;/*实际栈顶指针加1*/return(1);}}通过地址传递，用ptop带回实际栈顶指针a2a3a4

a5987654321a10top栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。类型定义如下所示：

#defineMAX_STACK10//栈的最大数据元素数目

typedef

structstack{

StackEntryitem[MAX_STACK];//存放栈中数据元素的存储单元

inttop;//栈顶指针

}STACK;基本操作算法：1.初始化栈SvoidInItStack(Sqstack&S){ S.base=(SElemType*)malloc(Stack_ININ_SIZE*sezeof(Elemtype)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; returnOK;}

通常的习惯做法是以Top=0表示空栈，鉴于C语言中数组的下标从0开始，则当以C语言来描述时，如此设定会带来很大的不方便，因此可以设Top=-1来表示空栈。2.入栈boolPush(Stack&S,ElemTypee){

//若栈的存储空间不满，则插入元素e为新的栈顶元素，

//并返回TRUE；否则返回FALSE

if(S.top==S.stacksize)

//栈已满，无法进行插入

returnFALSE;

*S.top=e;

//插入新的元素

S.top++;

//*S.top++=e

//栈顶指针后移

returnTRUE;}

3.出栈boolPop(Stack&S,ElemType

&e){

//

若栈不空，则删除S的栈顶元素，用e返回其值，

//

并返回TRUE；否则返回FALSE

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

--S.top;

//栈顶指针前移

e=*S.top;//返回非空栈中栈顶元素

returnTRUE;

}

4.获取栈顶元素内容bool

GetTop(StackS,ElemType

&e){

//

若栈不空，则用e返回S的栈顶元素，并返回TRUE；否则返回FALSE

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

e=*(S.top-1);

//返回非空栈中栈顶元素

returnTRUE;}

5.判断栈S是否为空

int

StackEmpty(STACKS){if(S.top==S.base)returnTRUE;elseFALSE;}

结论：由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。

x

∧top栈底（2）链栈

用指针来实现的栈叫链栈。栈的容量事先不能估计时采用这种存储结构。链栈的类型说明如下：Typedef

struct

lnode{

intdata；

struct

lnode

next；

}lnode，Lstack；进栈算法int

lpush(Lstacks,inte){p=(Lstack)malloc(sizeof(lnode));p->data=e;p->next=s;s=p;return(1);}∧baseS栈s进栈元素e进栈算法int

lpush(Lstacks,inte){

p=(Lstack)malloc(sizeof(lnode));p->data=e;p->next=s;s=p;return(1);}

∧PbaseS进栈算法int

lpush(Lstacks,inte){p=(Lstack)malloc(sizeof(lnode));

p->data=e;

p->next=s;s=p;return(1);}

∧PbaseSe进栈算法int

lpush(Lstacks,inte){p=(Lstack)malloc(sizeof(lnode));p->data=e;p->next=s;s=p;return(1);}

∧PbaseSe进栈算法int

lpush(Lstacks,inte){p=(Lstack)malloc(sizeof(lnode));p->data=e;p->next=s;

s=p;return(1);}

∧PbaseSSe若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。链栈通常用一个无头结点的单链表表示。由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。^

top栈的链式存储结构在C语言中可用下列类型定义实现：typestructnode{//链栈的结点结构

StackEntryitem;//栈的数据元素类型

structnode*next;//指向后继结点的指针}NODE;typedef

structstack{NODE*top;}STACK;下面我们将给出链栈各项基本操作的算法。1.初始化栈SvoidInitStack(STACK*S){S->top=NULL;}2.入栈voidPush(STACK*S,StackEntryitem){p=(NODE*)malloc(sizeof(NODE));if(!p)exit(OVERFLOW);else{p->item=item;p->next=S->top;S->top=p;}}3.出栈voidPop(STACK*S,StackEntry*item){if(StackEmpty(*S))exit(“Stackisempty”);else{*item=S->top->item;p=S->top;S->top=p->next;free(p);}}4.获取栈顶元素内容

voidGetTop(STACK

S,StackEntry*item){if(StackEmpty(S))exit(“Stackisempty”);else*item=S.top->item;}5.判断栈S是否空int

StackEmpty(STACKS){if(S.top==NULL)returnTRUE;elseFALSE;}

3.2栈的应用举例

【举例1】将从键盘输入的字符序列逆置输出比如，从键盘上输入：tsetasi

sihT；算法将输出：Thisisatest

下面我们给出解决这个问题的完整算法。

typedefcharStackEntry;voidReverseRead(){ STACKS;//定义一个栈结构S charch;

InitStack(&S);//初始化栈 while((ch=getchar())!=’\n’)

//从键盘输入字符，直到输入换行符为止

Push(&S,ch);//将输入的每个字符入栈 while(!StackEmpty(S)) { //依次出栈并输出出栈的字符

Pop(&S,&ch);

putchar(ch); }

putchar(‘\n’);}【举例2】十进制数值转换成二进制使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以2，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。比如：(692)10=(1010110100)2，其展转相除的过程如下图所示：下面给出解决这个问题的完整算法。voidDecimal_Binary(){ STACKS;//定义栈结构SInitStack(&S);//初始化栈Sscanf(“%d”,data);//输入十进制正整数while(data){ Push(&S,data%2);//余数入栈

data/=2;//被除数data整除以2，得到新的被除数}while(!StackEmpty(S)){ //依次从栈中弹出每一个余数，并输出之

Pop(&S,&data);

printf(“%d”,data);}}【举例3】检验表达式中的括号匹配情况假设在一个算术表达式中，可以包含三种括号：圆括号“（”和“）”，方括号“[”和“]”和花括号“{”和“}”，并且这三种括号可以按任意的次序嵌套使用。比如，...[...{...}...[...]...]...[...]...(...)..。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。

算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。

（1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；（2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；（3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。

下面是解决这个问题的完整算法。

typedefcharStackEntry;

intCheck(){STACKS;//定义栈结构Scharch;

InitStack(&S);//初始化栈Swhile((ch=getchar())!=’\n’){//以字符序列的形式输入表达式

switch(ch){case(ch==‘(’||ch==‘[’||ch==‘{’):

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

//在遇到右括号时，分别检测匹配情况

case(ch==‘)’):if(StackEmpty(S))retrunFALSE;else{Pop(&S,&ch);if(ch!=‘(’)returnFALSE;}break;case(ch==‘]’):if(StackEmpty(S))retrunFALSE;

else{Pop(&S,&ch);if(ch!=‘[’)returnFALSE;break;case(ch==‘}’):if(StackEmpty(S))retrunFALSE;else{Pop(&S,&ch);if(ch!=‘{’)returnFALSE;}break;default:break;}}if(StackEmpty(S))returnTRUE;elsereturnFALSE;}运算符：**/*+-（）界限符：；以表达式A*B+C\D为例说明利用栈的求值过程。

优先级：43322110【举例4】表达式的计算操作数变量：ABCDA*B+C/D#思想：从左到右扫描表达式，若当前读入的是操作数，则进操作数（OPD）栈，若读入的符号是运算符(OPR)

，应进行判断：

1.若是“（”，进运算符栈。若是“）”，当运算符栈顶是“（”，则弹出栈顶元素，继续扫描下一符号；否则当前读入符号暂不处理，从操作数栈弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，结果送入操作数栈，继续处理当前读入符号。

2.若读入的运算符的优先级大于运算符栈顶的优先级，则进运算符栈，继续扫描下一符号；否则从操作数栈顶弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，把结果送入操作数栈。继续处理刚才读入的符号。

3.若读入的是“#”，且运算符栈顶的符号也是“#”时，则表达式处理结束。从操作数栈弹出表达式结果。A*B+C/D#top2top1初态#(a)OPROPDBA*#(b)OPDOPRT1#(c)T1=A*BOPDOPRDCT1/+#(d)OPDOPR(g)OPDOPRT2=C/DT2T1+#(e)OPDOPRT3#(f)T3=T2+T1OPDOPRA*B+C/D#输入：表达式符号序列表达式求值算法：输出：表达式值y初始化栈OPD、OPRPush(OPR,“#”,top2)；t=0;//表示扫描下一个符号while(t<>2){IFt==0THENreadW;

IFW为操作数THENPush(OPD,W,top1)ELSE{p=OPR[top2];//读运算符栈栈顶元素，存入p.IF((W>p)or(W=“(“))THEN{Push(OPR,W,top2);t=0;}ELSEIF((p=“#”）and(W=“#”))THEN{Pop(OPD,y,top1);t=2;//处理过程结束}ELSEIF((p=“(“)and(w=“）”））THENELSE{Pop(OPD,x,top1);Pop(OPD,z,top1);Pop(OPR,p,top2）；x=zx;Push(OPD,x,top1);t=1;}}}//t=1,当前的符号下次重新考虑输出y;return;{Pop(OPR,p,top2);t=0;}θP115r主程序srrrs子程序1rst子程序2rst子程序3

3.3栈与递归

(1)

过程的嵌套

(2)

递归算法：

1(n=0,1)n!=n(n-1)！(n>1)函数的递归调用1.定义：

在调用一个函数的过程中直接或间接地调用该函数本身。直接调用intf(x)intx;{inty,z;…..z=f(x);……return(2*z);}

f函数调用f函数intf1(x)intx;{inty,z;…..z=f2(y);……return(2*z);}intf2(t)intt;{inta,c;…..c=f1(a);……return(3+c);}间接调用特点是无终止的递归调用，因此，应该给定一个限制递归次数的条件。f1函数调用f2函数f2函数调用f1函数

floatfac(intn){floatf;if(n<0)printf(“n<0,dataerror!\n”);elseif(n==0||n==1)f=1;elsef=fac(n-1)*n;returnf;}例如：写一函数求n!以求4的阶乘为例：fac(4)=4*fac(3)fac(3)=3*fac(2)fac(2)=2*fac(1)fac(1)=1fac(4)=4*3*2*1fac(2)=2*1fac(3)=3*2*1下推回代利用栈实现递归调用主程序(1)输出f(4);

……4f(4);（1）n=4top(2)s=4*f(3)n3f(3);（2）n=3（1）n=4top(3)s=3*f(2)n2f(2);（3）n=2（2）n=3（1）n=4top(4)s=2*f(1)n1（4）n=1（3）n=2（2）n=3（1）n=4topss=3*2*1;(2)3(1)4tops=2*1(3)2(2)3(1)4top

s=4*3*2*1(1)4top返回(3)2(2)3(1)4top(4)1结束输出24递归的执行情况分析

longFact(intn){longs;if(n==1)s=1;elses=n*Fact(n-1);return(s);}作业

#11A+B*C-D/E#top1初态#(a)top2OPROPDBA+#(b)OPR*C

OPDT1=B*CA+#(c)OPDOPRT1T2#(d)OPDOPRT2=A+T1EDT2/-#(e)OPDOPRT3T2-#(f)T3=D/EOPDOPR(g)OPDOPRT4#T4=T2-T3(h)下一题A-B/C+D*E#top2初态#(a)OPROPDBA#(b)OPR/C

OPDA#(c)OPDOPRT1T1=B/CA#(d)OPDOPRT1DE+*T2T1A+#(e)OPDOPRT2=D*ET2T3+#(f)T3=A-T1OPDOPRT4=T2+T3(g)OPDOPRT4#(h)优先级相同时，应先处理栈中数据错在哪？#2

若进栈序列为3，5，7，9，进栈过程中可以出栈，则不可能的一个出栈次序是（）。

(a)7,5,3,9(b)9,7,5,3(c)7,5,9,3(d)9,5,7,3d#3

用一维数组设计栈，初态是栈空，top=0。现有输入序列是a、b、c、d，经过

push、push、pop、push、pop、push操作后，输出序列是（），栈顶指针是（）b、c2#4

对于下面的程序调用过程，请问出栈次序是（）。2、1、3上机作业：作业2：用C语言编写递归和非递归计算n!程序。递归算法：int

F(intn){intm;if(n==0)m=1;elsem=n*F(n-1);return(m);}非递归算法：int

F(intn){intf1=1,s=1;if(n==0)return1;while(s<=n){f1=f1*s;s=s+1;}return(f1);}

3.4队列

3.4.1队列的定义与运算定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表。此种结构称为先进先出（FIFO）表。

a1,

a2,

a3,

a4,…………

an-1,

an队列示意图队头队尾

插入端和删除端都是浮动的。通常我们将插入端称为队尾，用一个“队尾指针”指示；而删除端被称为队头，用一个“队头指针”指示。结论：先进先出（FirstInFirstOut），简称为FIFO线性表。举例1：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。举例2：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。（不一定）

举例3：在Windows这类多任务的操作系统环境中，每个应用程序响应一系列的“消息”，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。下面我们给出队列结构的基本操作：（1）初始化队列InitQueue(Q)（2）入队EnQueue(Q,item)（3）出队DeQueue(Q,item)（4）获取队头元素内容GetFront(Q,item)（5）判断队列是否为空QueueEmpty(Q)2.队列的存储结构（一）顺序存储结构(a)线性队列

(b)循环队列队列的顺序存储结构如下图所示：(a)线性队列问题1：当队空时，队头和队尾指针都为-1，队列将处于下图所示的状态：

此时若进行入队操作，就需要让队头和队尾指针都增1，再将新数据元素放入该位置。也就是说，这样设置队头、队尾指针位置，在进行入队操作时，空队与非空队状态所需要执行的操作不完全一样。解决方法：在算法中，需要对这两种情况加以区分，这势必增加了算法的复杂性。因此，人们设想了一种解决方法，即让队头指针指向队列真正队头元素的前一个位置，如下图所示。

3210

(a)rear=front=-1(队满）e3e4

(c)e1,e2出队，e4入队

队满rear=4fronte1e2e3

(b)rearfront(b)e1,e2,e3入队队空时，令rear=front=-1，当有新元素入队时，尾指针加1，当有元素出队时，头指针加1。故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置

问题2：由于顺序存储结构的存储空间属于静态分配，所以，在添加数据元素时，可能会出现没有剩余单元的情况。对于队列来说，这一点又有它的特殊性。下面我们讨论一下下图所示的队列。

“假溢出”现象。解决方法：将存储队列元素的一维数组首尾相接，形成一个环状。如下图所示。我们将这种形式表示的队列称之为循环队列。(b)循环队列a8a7a6a576543210rearfront问题：与教材P63上有何不同？实质是不是一样？假设为队列开辟的数组单元数目为MAX_QUEUE，在C语言中，它的下标在0~MAX_QUEUE-1之间，若增加队头或队尾指针，可以利用取模运算（一个整数数值整除以另一个整数数值的余数）实现。如下所示：

front=(front+1)%MAX_QUEUE；

rear=(rear+1)%MAX_QUEUE；

当front或rear为MAXQUEUE-1时，上述两个公式计算的结果就为0。这样，就使得指针自动由后面转到前面，形成循环的效果。

队空和队满的标志问题：

a7a876543210rearfront76543210rearfront(a)(b)队列变为空，队头和队尾指针相等。如下图所示rearfronta6a5a4a3a1a276543210a6a5a4a3a1a2a8a776543210rearfront(a)(b)队列变为满，队头和队尾指针也相等。如下图所示解决方法：一是为队列另设一个标志，用来区分队列是“空”还是“满”；二是当数组只剩下一个单元时就认为队满，此时，队尾指针只差一步追上队头指针，即：(rear+1)%MAX_QUEUE==front。类型定义：

#defineMAX_QUEUE10//队列的最大数据元素数目

typedef

structqueue{//假设当数组只剩下一个单元时认为队满

QueueEntryitem[MAX_QUEUE];//存放队列中数据元素的存储单元

intfront,rear;//队头指针、队尾指针

}QUEUE;

rearfront

0

1

2

3(3)队空队满条件：(Q.rear+1)%MAX==Q.front注：实际上为了避免与队空标志冲突，还留有一个空间。将头尾连接成一个环，形成循环队列。

rear(1)一般情况front

0

1

2

3e4e3

(2)队满fronte3

e4

0

1

2

3reare5队空条件：Q.rear==Q.front循环队列中加入一个元素的算法：

int

EnQueue(intQ[],intx,int*pf,int*pr)Q[max]已有的循环队列将插入的值已有队列的头指针已有队列的尾指针循环队列中加入一个元素的算法：

int

EnQueue(intQ[],intx,int*pf,int*pr){intfront,rear;front=*pf;rear=*pr;if((rear+1)%MAX==front)return(0);else{rear=(rear+1)%MAX;Q[rear]=x;*pr=rear;return(1);}}

rearMax=4,Rear+1=4front

0

1

2

3e4e3

rear(Rear+1)%4=0front

0

1

2

3e4e3rear

rearfront

0

1

2

3e4e3x循环队列中删除一个元素的算法：int

DeQueue(intQ[]，int*py，int*pf，int*pr)已有的循环队列返回删除的值的地址已有队列的头指针已有队列的尾指针循环队列中删除一个元素的算法：int

DeQueue(intQ[]，int*py，int*pf，int*pr){intfront,rear;front=*pf;rear=*pr;if(rear==front)return(0);else{front=(front+1)%MAX;*py=Q[front];*pf=front;return(1);}}各项基本操作算法。（1）初始化队列QvoidInitQueue(QUEUE*Q){Q->front=-1;Q->rear=-1;}（2）入队voidEnQueue(QUEUE*Q,QueueEntryitem){if((Q->rear+1)%MAX_QUEUE==Q->front)exit(OVERFLOW);else{Q->rear=(Q->rear+1)%MAX_QUEUE;Q->item[Q->rear]=item;}}（3）出队voidDeQueue(QUEUE*Q,QueueEntry*item){if(QueueEmpty(*Q))exit(“Queueisempty.”);else{Q->front=(Q->front+1)%MAX_QUEUE;*item=Q->item[Q->front];}}（4）获取队头元素内容voidGetFront(QUEUE

Q,QueueEntry*item){if(QueueEmpty(Q))exit(“Queueisempty.”);else*item=Q.item[(Q.front+1)%MAX_QUEUE];}（5）判断队列Q是否为空int

QueueEmpty(QueueQ){if(Q.front==Q.rear)returnTRUE;elsereturnFALSE;}^frontrear（二）链式存储结构在用链式存储结构表示队列时，需要设置队头指针和队尾指针，以便指示队头结点和队尾结点。ana2a1

ana3a2

Q.frontQ.rear删除一个元素添加一个元素e^a1a2anQ.frontQ.rear

Q.frontQ.rear队头队尾Q.rearQ.front入队需要执行下面三条语句：s->next=NULL;rear->next=s;rear=s;下面是在C语言中，实现队列链式存储结构的类型定义：typestructnode{//链式队列的结点结构

QueueEntryEntry;//队列的数据元素类型

structnode*next;//指向后继结点的指针}NODE;typedef

structqueue{//链式队列

NODE*front;//队头指针

NODE*rear;//队尾指针}QUEUE;下面我们给出链式队列的基本操作算法。（1）初始化队列QvoidInitQueue(QUEUE*Q){Q->front=(NODE*)malloc(sizeof(NODE))