數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列

棧和隊(duì)列1、棧和隊(duì)列的定義及特點(diǎn)；

2、棧的順序存儲(chǔ)表示；

3、隊(duì)列的順序存儲(chǔ)表示；隊(duì)列的鏈接存儲(chǔ)表示；

4、棧和隊(duì)列的應(yīng)用舉例。教學(xué)內(nèi)容限定僅在表尾進(jìn)行插入或刪除操作。3.1棧3.1.1抽象數(shù)據(jù)類型棧的定義棧的定義a1a2an-1an…棧頂(top)棧底(bottom)出棧進(jìn)棧棧底元素

棧頂元素

棧：線性表

后進(jìn)先出(LIFO結(jié)構(gòu))。棧的抽象數(shù)據(jù)類型的定義

ADTStack{數(shù)據(jù)對(duì)象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

約定an

端為棧頂，a1

端為棧底?；静僮鳎篒nitStack(&S)

操作結(jié)果：構(gòu)造一個(gè)空棧

S。DestroyStack(&S)

初始條件：棧S已存在。

操作結(jié)果：棧S被銷毀。

GetTop(S,&e)

初始條件：棧S已存在且非空。

操作結(jié)果：用e

返回S的棧頂元素。StackEmpty(S)

初始條件：棧S已存在。

操作結(jié)果：若棧S為空棧，則返回TRUE，否則FALSE。

StackLength(S)

初始條件：棧S已存在。

操作結(jié)果：返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度。

ClearStack(&S)

初始條件：棧S已存在。

操作結(jié)果：將S清為空棧。

Push(&S,e)

初始條件：棧S已存在。

操作結(jié)果：插入元素e

為新的棧頂元素。

Pop(&S,&e)

初始條件：棧S已存在且非空。操作結(jié)果：刪除S的棧頂元素，并用e

返回其值。

}ADTStack3.1.2棧的表示和實(shí)現(xiàn)

順序棧

順序棧：利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置。

topbaseAtopBtopCtopDtopEtop空棧

若再進(jìn)行元素“出?！辈僮鳎瑢a(chǎn)生“下溢”。

top棧滿

若再進(jìn)行元素“入?！辈僮鳎瑢a(chǎn)生“上溢”。

#defineLIST_INIT_SIZE100//線性表存儲(chǔ)空間的初始分配量

#defineLISTINCREMENT10//線性表存儲(chǔ)空間的分配增量

typedef

struct{

ElemType*elem;//數(shù)組指針，指示線性表的基地址

intlength;//當(dāng)前長(zhǎng)度

int

listsize;//當(dāng)前分配的存儲(chǔ)容量(以sizeof(ElemType)為單位)

}SqList;SelemType*base;//棧底指針，它始終指向棧底的位置。

SelemType*top;//棧頂指針。int

stacksize;//當(dāng)前分配的?？墒褂玫淖畲蟠鎯?chǔ)容量。

Sqstack;注：base的值為NULL，表明棧結(jié)構(gòu)不存在。

#defineSTACK_INIT_SIZE100//棧存儲(chǔ)空間的初始分配量

#defineSTACKINCREMENT10//棧存儲(chǔ)空間的分配增量

棧的基本操作在順序棧中的實(shí)現(xiàn)#definemaxs9;main(){int

stack[maxs];

inttop=0;

while(top<maxs){scanf(“%d”,&stack[top]);top++;}

inte;e=stack[top-1];

while(top>0)e=stack[top-1];top-=1;}InitStack

PushPoptop12toptoptop2topGetTop

21StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemtype));if(!S.base)exit(OVERFLOW);S.top=S.base;

S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStackStatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINcrement)*sizeof(SElemtype));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}//PushStatusGetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;e=*(S.top–1);returnOK;}//GetTop

StatusPop(SqStack&S,SElemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//Pop棧頂指針鏈棧an注意:鏈棧中指針的方向an-1a1…^▲3.2棧的應(yīng)用舉例

3.2.1數(shù)制轉(zhuǎn)換

十進(jìn)制數(shù)N

和其他d

進(jìn)制數(shù)M

的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問題，其解決方法很多，其中一個(gè)簡(jiǎn)單算法是逐次除以基數(shù)d

取余法，它基于下列原理：

N=(Ndivd)*d+Nmodd

具體作法為：首先用N

除以d，得到的余數(shù)是d

進(jìn)制數(shù)M的最低位M0，接著以前一步得到的商作為被除數(shù)，再除以d，得到的余數(shù)是d

進(jìn)制數(shù)M

的次最低位M1，依次類推，直到商為0時(shí)得到的余數(shù)是M

的最高位Ms（假定M

共有s+1位）。例：

(1348)10=(2504)8，其運(yùn)算過程如下：

N

Ndiv8Nmod8134816841682102125202計(jì)算順序輸出順序bottomtop

4052top1348168void

conversion

(){

intstack[4];

inttop=0;

intN;

scanf(“%d”,N);while(N){

stack[top]=N%8;top++;N=N/8;}for(top=top-1;top>=0;top--)

printf(“%d”,stack[top]);}21top2top0top2504InitStack(S)Push(S,N%S)While(!Stackempty(S)){

Pop(S,e);

printf(“%d”,e);}3.2.2括號(hào)匹配的檢驗(yàn)假設(shè)表達(dá)式中允許括號(hào)嵌套，則檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來描述。例：

[

(

[

]

[

]

)

]12345678bottomtop[([toptoptoptoptoptoptoptop[可能出現(xiàn)的不匹配的情況：盼來的右括號(hào)不是所“期待”的；到來的是“不速之客”（右括號(hào)多）；到結(jié)束也未盼來所“期待”的括號(hào)（左括號(hào)多）。算法的設(shè)計(jì)思想：1）凡出現(xiàn)左括號(hào)，則進(jìn)棧；

2）凡出現(xiàn)右括號(hào)，首先檢查棧是否空。

若棧空，則表明該“右括號(hào)”多余；

否則和棧頂元素比較，

若相匹配，則“左括號(hào)出?！保?/p>

否則表明不匹配。

3）表達(dá)式檢驗(yàn)結(jié)束時(shí)，

若?？?，則表明表達(dá)式中匹配正確，

否則表明“左括號(hào)”有多余的。

3.2.3行編輯程序功能：接受用戶從終端輸入的數(shù)據(jù)并存入用戶的數(shù)據(jù)區(qū)。

bottomtoptoptop接受一個(gè)字符即存入數(shù)據(jù)區(qū)。（差！難糾錯(cuò)。）設(shè)一個(gè)輸入緩沖區(qū)，接受完一行字符后再存入用戶的數(shù)據(jù)區(qū)。（好！可及時(shí)糾錯(cuò)。）做法

糾錯(cuò)辦法

#

退格符，表示前一個(gè)字符無(wú)效。

@

退行符，表示整行字符均無(wú)效。

例：接受的字符為：

whli##ile

outch@putch

實(shí)際有效的為：

while

putch

whltopitoptoptopitopletoptopvoidLineEdit(){

InitStack(S);

ch=getchar();while(ch!=EOF){//EOF為全文結(jié)束符

while(ch!=EOF&&ch!='\n'){switch(ch){case'#':Pop(S,c);break;case‘@’:ClearStack(S);break;//重置S為空棧

default:Push(S,ch);break;}

ch=getchar();//從終端接收下一個(gè)字符

}

將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)；

ClearStack(S);//重置S為空棧

if(ch!=EOF)ch=getchar();}

DestroyStack(S);}3.2.4迷宮求解

出口入口

0123456789012345678911122232333424252616151431415152536364657585868788

窮舉求解求迷宮路徑算法的基本思想：

若當(dāng)前位置“可通”，則納入路徑，繼續(xù)前進(jìn)；

若當(dāng)前位置“不可通”，則后退，換方向（按東南西北

的順序）繼續(xù)探索；

若四周“均無(wú)通路”，則將當(dāng)前位置從路徑中刪除出去。3.2.5表達(dá)式求值

運(yùn)算規(guī)則先乘除，后加減；從左算到右；先括號(hào)內(nèi)，后括號(hào)外；例：求表達(dá)式4+23-10/5

的值。計(jì)算順序?yàn)椋?+23-10/5=4+6-10/5=10-10/5=10-2=8

操作數(shù)或結(jié)果運(yùn)算符#4+2

3

610-10/582▲

“四染色”定理是計(jì)算機(jī)科學(xué)中著名定理之一，即可以用不多于四種顏色對(duì)地圖著色，使相鄰的行政區(qū)域不重色。補(bǔ)充：地圖四染色問題

算法思想：從第一號(hào)行政區(qū)開始逐一染色，每一個(gè)區(qū)域逐次用顏色1、2、3、4進(jìn)行試探。若當(dāng)前所取的色數(shù)與周圍已染色的行政區(qū)不重色，則用棧記下該行政區(qū)的色數(shù)，否則依次用下一色數(shù)進(jìn)行試探；若出現(xiàn)用1至4色均與相鄰區(qū)域發(fā)生重色，則需退?；厮?，修改當(dāng)前棧頂?shù)纳珨?shù)，再進(jìn)行試探。直至所有行政區(qū)域都已分配合適的顏色。例：已知7個(gè)行政區(qū)域地圖，對(duì)其進(jìn)行染色。12345671011111010000101001100101011010110101101100700000001234123456712234431(3)(1)(2)(4)(5)(6)(7)3243作業(yè)：3.1、3.2、3.3、3.4、3.18選擇題部分

1、若入棧序列是a,b,c,d,e，則不可能的出棧序列是（）。（A）

edcba（B）decba（C）dceab

（D）abcde

2、判定一個(gè)棧ST(最多元素為m0)為空的條件是（）。

（A）ST.top!=0（B）ST.top=0

（C）ST.top!=m0

（D）ST.top=m0

3、判定一個(gè)棧ST(最多元素為m0)為滿的條件是（）。

（A）ST.top!=0（B）ST.top=0

（C）ST.top!=m0

（D）ST.top=m0

3.3棧與遞歸的實(shí)現(xiàn)

遞歸：一個(gè)直接調(diào)用自己或通過一系列的調(diào)用語(yǔ)句間接地調(diào)用自己的函數(shù)，稱做遞歸函數(shù)。例：階乘函數(shù)相應(yīng)的C語(yǔ)言函數(shù)是：floatfact(int

n){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}若求5!，則有main(){printf(“5!=%f\n”,fact(5));}

當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行該被調(diào)用函數(shù)之前，需先完成三件事：將實(shí)參等傳遞給被調(diào)用函數(shù)，保存返回地址（入棧）；

為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū)；

將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成：

保存被調(diào)函數(shù)的計(jì)算結(jié)果；

釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)；按被調(diào)函數(shù)保存的返回地址（出棧）將控制轉(zhuǎn)移到調(diào)用函數(shù)。多個(gè)函數(shù)嵌套調(diào)用的規(guī)則是：后調(diào)用先返回。此時(shí)的內(nèi)存管理實(shí)行“棧式管理”。floatfact(int

n){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}遞歸調(diào)用執(zhí)行過程：主函數(shù)main()Printf(fact(5))第一層調(diào)用n=5s=5*fact(4)第二層調(diào)用n=4s=4*fact(3)第三層調(diào)用n=3s=3*fact(2)第四層調(diào)用n=2s=2*fact(1)第五層調(diào)用n=1s=1*fact(0)fact(5)=120輸出s=120.00第六層調(diào)用n=0s=1fact(4)=24fact(3)=6fact(2)=2fact(1)=1fact(0)=1主a

5a4a3a2a1aprintf(“5!=%f\n”,fact(5));basefloatfact(int

n){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}floatfact(int

n){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}floatfact(int

n){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}floatfact(int

n){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}floatfact(int

n){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}n=5n=4n=3n=2n=1n=0限定在表的一端插入、另一端刪除。3.4隊(duì)列

3.4.1抽象數(shù)據(jù)類型隊(duì)列的定義隊(duì)列的定義隊(duì)列：線性表

(queue)先進(jìn)先出(FIFO結(jié)構(gòu))。隊(duì)尾隊(duì)頭下圖是隊(duì)列的示意圖：

a1

a2

…

an出隊(duì)入隊(duì)隊(duì)頭隊(duì)尾當(dāng)隊(duì)列中沒有元素時(shí)稱為空隊(duì)列。隊(duì)列的抽象數(shù)據(jù)類型的定義

ADTQueue{

數(shù)據(jù)對(duì)象：D＝{ai

|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：R1＝{<ai

-1,ai

>|ai-1,ai∈D,i=2,...,n}

約定其中a1

端為隊(duì)列頭，an

端為隊(duì)列尾?；静僮鳎?/p>

InitQueue(&Q)

操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。

DestroyQueue(&Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：隊(duì)列Q被銷毀，不再存在。QueueEmpty(Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：若Q為空隊(duì)列，則返回TRUE，否則返回FALSE。QueueLength(Q)

初始條件：隊(duì)列Q已存在。操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度。GetHead(Q,&e)

初始條件：Q為非空隊(duì)列。操作結(jié)果：用e

返回Q的隊(duì)頭元素。

ClearQueue(&Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：將Q清為空隊(duì)列。

EnQueue(&Q,e)

初始條件：隊(duì)列Q已存在。操作結(jié)果：插入元素e

為Q的新的隊(duì)尾元素。

DeQueue(&Q,&e)

初始條件：Q為非空隊(duì)列。

操作結(jié)果：刪除Q的隊(duì)頭元素，并用e

返回其值。}ADTQueue雙端隊(duì)列限定插入和刪除在表的兩端進(jìn)行。雙端隊(duì)列：線性表

(double-endedqueue)先進(jìn)先出(FIFO結(jié)構(gòu))。端點(diǎn)1端點(diǎn)2下圖是雙端隊(duì)列的示意圖：

a1

a2

…

an出隊(duì)入隊(duì)端點(diǎn)1端點(diǎn)2出隊(duì)入隊(duì)輸出受限的雙端隊(duì)列：一個(gè)端點(diǎn)可插入和刪除，另一個(gè)端點(diǎn)僅可插入。

輸入受限的雙端隊(duì)列：一個(gè)端點(diǎn)可插入和刪除，另一個(gè)端點(diǎn)僅可刪除。

▲3.4.2鏈隊(duì)列——隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

鏈隊(duì)列：用鏈表表示的隊(duì)列。是限制僅在表頭刪除和表尾插入的單鏈表。一個(gè)鏈隊(duì)列由一個(gè)頭指針和一個(gè)尾指針唯一確定。

（因?yàn)閮H有頭指針不便于在表尾做插入操作）。為了操作的方便，也給鏈隊(duì)列添加一個(gè)頭結(jié)點(diǎn)，因此，空隊(duì)列的判定條件是：頭指針和尾指針都指向頭結(jié)點(diǎn)。∧frontrearrearfront∧…圖3-12鏈隊(duì)列示意圖隊(duì)頭隊(duì)尾用C語(yǔ)言定義鏈隊(duì)列結(jié)構(gòu)如下：typedef

struct

QNode

{QElemtypedata;

struct

QNode*next;}Qnode,*QueuePtr;//定義隊(duì)列的結(jié)點(diǎn)typedef

struct

{QueuePtr*front;//隊(duì)頭指針

QueuePtr*rear;//隊(duì)尾指針}LinkQueue;StatusInitQueue(LinkQueue&Q)

{//構(gòu)造一個(gè)空隊(duì)列Q

Q.front=Q.rear=(QueuPtr)malloc(sizeof(QNode));

if(!Q.front)exit(OVERFLOW);

//存儲(chǔ)分配失敗

Q.front->next=NULL;

returnOK;

}隊(duì)列的基本操作在鏈隊(duì)列中的實(shí)現(xiàn)：

隊(duì)列的初始化：

a1a2a3^Q.frontQ.rear銷毀隊(duì)列：

=null=nullStatusDestroQueue(LinkQueue&Q)

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

free(Q.front);

Q.front=Q.rear;}returnOK;

}∧rear…front∧x∧y插入操作在鏈隊(duì)列中的實(shí)現(xiàn)ppStatusEnQueue(LinkQueue&Q,QElemTypee)

{//插入元素e為Q的新的隊(duì)尾元素

p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data=e;p->next=NULL;

Q.rear->next=p;

Q.rear=p;returnOK;

}StatusDeQueue(LinkQueue&Q,QElemType&e)

{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;free(p);returnOK;

}∧frontrearyx刪除操作在鏈隊(duì)列中的實(shí)現(xiàn)p▲p∧填空題部分

1、棧的特點(diǎn)是（），隊(duì)列的特點(diǎn)是（）。

2、線性表、棧和隊(duì)列都是（）結(jié)構(gòu)，可以在線性表的（）位置插入和刪除元素，棧只能在（）插入和刪除元素，隊(duì)列只能在（）插入元素和（）刪除元素。

3、設(shè)棧S和隊(duì)列Q的初始狀態(tài)皆為空，元素a1,a2,a3,a4,a5

和a6依次通過一個(gè)棧，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若

6個(gè)元素出隊(duì)列的順序是a3,a5,a4,a6,a2,a1則棧S至少應(yīng)該容納(

)個(gè)元素。4、若隊(duì)列的入隊(duì)序列是1,2,3,4，則出隊(duì)序列是（）。（A）4,3,2,1（B）1,2,3,4（C）1,4,3,2（D）3,2,4,1作業(yè)3.11、3.123.4.3循環(huán)隊(duì)列－隊(duì)列的順序表示和實(shí)現(xiàn)是限制僅在表頭刪除和表尾插入的順序表。頭尾指針利用一組地址連續(xù)的存儲(chǔ)單元依次存放隊(duì)列中的數(shù)據(jù)元素。rearfrontrearfrontJ1

J2

J3

頭、尾指針和隊(duì)列元素之間的關(guān)系rearfrontJ3

rearfront在非空隊(duì)列里，頭指針始終指向隊(duì)頭元素尾指針始終指向隊(duì)尾元素的下一位置。因?yàn)椋宏?duì)頭和隊(duì)尾的位置是變化的，所以：設(shè)頭、尾指針。

初始化時(shí)的初始值均應(yīng)置為0。入隊(duì)，尾指針增1出隊(duì)，頭指針增1頭尾指針相等時(shí)隊(duì)列為空在順序隊(duì)列中，當(dāng)尾指針已經(jīng)指向了隊(duì)列的最后一個(gè)位置的下一位置時(shí)，若再有元素入隊(duì)，就會(huì)發(fā)生“溢出”。

“假溢出”——隊(duì)列的存儲(chǔ)空間未滿，卻發(fā)生了溢出。rearfrontJ1

J2

J3

J4

rearfrontJ3

J4

(1)、平移元素：把元素平移到隊(duì)列的首部。效率低。解決“假溢出”的問題有兩種可行的方法：

(2)、將新元素插入到第一個(gè)位置上，構(gòu)成循環(huán)隊(duì)列，入隊(duì)和出隊(duì)仍按“先進(jìn)先出”的原則進(jìn)行。

操作效率、空間利用率高。rearfrontJ3

J4

frontrearJ3

J4

循環(huán)隊(duì)列的三種狀態(tài)：012345frontrear012345J5

J4

J3

frontrear012345J5

J4

J3

J6

J7

J8

front

rear注：僅憑front=rear不能判定隊(duì)列是空還是滿。解決辦法：

(1)、另設(shè)一個(gè)布爾變量以區(qū)別隊(duì)列的空和滿；(2)、少用一個(gè)元素的空間，約定入隊(duì)前測(cè)試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認(rèn)為隊(duì)滿；

(3)、使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)。#defineMAXQSIZE100//最大隊(duì)列長(zhǎng)度

typedef

struct{

QElemType*base;//預(yù)分配存儲(chǔ)空間基址

intfront;//頭指針，若隊(duì)列不空，

//指向隊(duì)列頭元素

intrear;//尾指針，若隊(duì)列不空，

//指向隊(duì)列尾元素的下一個(gè)位置

}SqQueue;隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)：循環(huán)意義下的加1操作可以描述為：

if(rear+1>MAXQSIZE)rear=0;elserear++;012345J5

J4

J3

rearfront利用模運(yùn)算可簡(jiǎn)化為：rear=(rear+1)%MAXQSIZE

StatusInitQueue(SqQueue&Q){//構(gòu)造一個(gè)空隊(duì)列QQ.base=(QElemType*)malloc

(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);//存儲(chǔ)分配失敗

Q.front=Q.rear=0;returnOK;}隊(duì)列的基本操作在循環(huán)隊(duì)列中的實(shí)現(xiàn)：

隊(duì)列的初始化：

StatusQueueLength(SqQueueQ){//返回隊(duì)列Q的元素個(gè)數(shù)

return(Q.rear-Q.front);}

StatusQueueLength(SqQueueQ){//返回隊(duì)列Q的元素個(gè)數(shù)

return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}求循環(huán)隊(duì)列的長(zhǎng)度

考慮到循環(huán)隊(duì)列frontrearJ3

J4

frontrearJ3

J1

J2

StatusEnQueue(SqQueue&Q,QElemTypee){//插入元素e為Q的新的隊(duì)尾元素

Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}StatusEnQueue(SqQueue&Q,QElemTypee){//插入元素e為Q的新的隊(duì)尾元素

if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;//隊(duì)列滿

Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}插入操作在循環(huán)隊(duì)列中的實(shí)現(xiàn)frontrearJ3

J4

J5

rear

StatusDeQueue(SqQueue&Q,ElemType&e){