數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第3章

第三章棧和隊(duì)列【課前思考】1.什么是線性結(jié)構(gòu)？

簡單地說，線性結(jié)構(gòu)是一個數(shù)據(jù)元素的序列。2.你見過餐館中一疊一疊的盤子嗎？如果它們是按1,2,…,n的次序往上疊的，那么使用時候的次序應(yīng)是什么樣的？

必然是依從上往下的次序，即n,…,2,1。它們遵循的是"后進(jìn)先出"的規(guī)律，這正是本章要討論的"棧"的結(jié)構(gòu)特點(diǎn)。3.在日常生活中，為了維持正常的社會秩序而出現(xiàn)的常見現(xiàn)象是什么？

是"排隊(duì)"。在計(jì)算機(jī)程序中，模擬排隊(duì)的數(shù)據(jù)結(jié)構(gòu)是"隊(duì)列"?！緦W(xué)習(xí)目標(biāo)】1、掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們。2、熟練掌握棧類型的兩種實(shí)現(xiàn)方法。

3、熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法。

棧和隊(duì)列是在程序設(shè)計(jì)中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)，因此本章的學(xué)習(xí)重點(diǎn)在于掌握這兩種結(jié)構(gòu)的特點(diǎn)，以便能在應(yīng)用問題中正確使用?！局R點(diǎn)】順序棧、循環(huán)隊(duì)列、鏈隊(duì)列【重點(diǎn)和難點(diǎn)】通常稱，棧和隊(duì)列是限定插入和刪除只能在表的“端點(diǎn)”進(jìn)行的線性表。

線性表?xiàng)ｊ?duì)列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≤n3.1棧3.2棧的應(yīng)用舉例3.4隊(duì)列

目錄3.1棧一、棧的定義

棧(stack)作為一種限定性線性表，是將線性表的插入和刪除操作限制為僅在表的一端進(jìn)行。將表中允許進(jìn)行插入、刪除操作的一端稱為棧頂(Top)。棧頂?shù)漠?dāng)前位置是動態(tài)變化的，它由一個稱為棧頂指針的位置指示器指示。

表的另一端為固定的一端，被稱為棧底(Bottom)。當(dāng)棧中沒有元素時稱為空棧。棧的插入操作被形象地稱為進(jìn)棧或入棧，刪除操作稱為出?；蛲藯?。插入：最先放入棧中元素在棧底，最后放入的元素在棧頂；刪除：最后放入的元素最先刪除，最先放入的元素最后刪除。棧是一種后進(jìn)先出(LastInFirstOut)的線性表，簡稱為LIFO表。圖3.1棧例：設(shè)一個棧的輸入序列為A,B,C,D,則借助一個棧所得到的輸出序列不可能是

。

(A)A,B,C,D (B)D,C,B,A (C)A,C,D,B (D)D,A,B,C二、棧的主要操作

1.初始化棧：InitStack(&S)將棧S置為一個空棧(不含任何元素)。2.進(jìn)棧：Push(&S，e)將元素X插入到棧S中，也稱為“入?！薄ⅰ安迦搿?、“壓入”。3.出棧：Pop(&S，&e)

刪除棧S中的棧頂元素，也稱為”退?！薄ⅰ皠h除”、“彈出”。4.取棧頂元素：GetTop(S，&e)取棧S中棧頂元素。5.判?？眨篠tackEmpty(S)判斷棧S是否為空，若為空，返回值為1，否則返回值為0。三、棧的抽象數(shù)據(jù)類型描述

ADTStack{

數(shù)據(jù)對象：D={ai|ai

∈ElemSet，i=1,2,…,n,n≥0}

數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai

∈D,i=1,2,…,n}

基本操作：

InitStack(&S)

操作前提：S為未初始化的棧。

操作結(jié)果：將S初始化為空棧。

ClearStack(&S)

操作前提：棧S已經(jīng)存在。

操作結(jié)果：將棧S置成空棧。

StackEmpty(S)

操作前提：棧S已經(jīng)存在。

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

StackLength(S)

操作前提：棧S已經(jīng)存在。

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

StackTraverse(S,visit())

操作前提：棧S已經(jīng)存在且非空。

操作結(jié)果：從棧底到棧頂依次對S的每個元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失效。

Push(&S,e)

操作前提：棧S已經(jīng)存在。

操作結(jié)果：在S的頂部插入(亦稱壓入)元素e；若S棧未滿，將e插入棧頂位置，若棧已滿，則返回FALSE，表示操作失敗，否則返回TRUE。

Pop(&S,&e)

操作前提：棧S已經(jīng)存在。

操作結(jié)果：刪除(亦稱彈出)棧S的頂部元素，并用e帶回該值；若棧為空，返回值為FALSE，表示操作失敗，否則返回TRUE。

GetTop(S,&e)

操作前提：棧S已經(jīng)存在。

操作結(jié)果：取棧S的頂部元素。與Pop(&S,&e)不同之處在于GetTop(S,&e)不改變棧頂?shù)奈恢?。}ADTStack

1.順序棧

順序棧是用順序存儲結(jié)構(gòu)實(shí)現(xiàn)的棧，即利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時附設(shè)一個棧頂指針top和棧底指針base。base始終指向棧底的位置。top=base作為棧空的標(biāo)記。非空棧的棧頂指針top始終在棧頂元素的下一個位置上。四、棧的表示和實(shí)現(xiàn)

16top空棧toptoptoptoptopa進(jìn)棧b進(jìn)棧aababcdee進(jìn)棧abcdef進(jìn)棧溢出abde退棧cbasebasebasebasebasebase棧頂指針和棧中元素之間的關(guān)系#defineSTACK_INIT_SIZE100

//存儲空間初始分配量#defineSTACKINCREMENT10

//存儲空間分配增量typedef

struct{SElemType*base;

//在棧構(gòu)造前和銷毀后base值為NULL

SElemType*top;

//棧頂指針

int

stacksize;}SqStack;

//當(dāng)前已分配存儲空間棧的順序存儲結(jié)構(gòu)定義如下：（1）構(gòu)造空順序棧算法:初始化棧StatusInitStack(SqStack&S){//構(gòu)造一個空棧SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//為棧分配存儲空間失敗S.top=S.base;//令棧頂指針=棧底指針//設(shè)置棧的當(dāng)前可使用的最大容量S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStack2.順序棧基本操作的實(shí)現(xiàn)如下:程序描述：//Thisprogramistoinitializeastack.#include<malloc.h>#include<iostream.h>#include<conio.h>#defineSTACK_INIT_SIZE

100#defineSTACKINCREMENT

10#defineOK

1#defineERROR

0typedef

intSElemType;typedef

struct

//definestructureSqStack(){SElemType*base;SElemType*top;intstacksize;

}SqStack;

intInitStack(SqStack&S)

//InitStack()sub-function{S.base=(SElemType)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base){printf("Allocatespacefailure!\n");return(ERROR);}S.top=S.base;S.stacksize=STACK_INIT_SIZE;return(OK);}//InitStack()endvoidmain()//main()function{SqStackS;if(InitStack(S))printf("Success!Thestackhasbeencreated!\n");printf("...OK!…\n");getch();}（2）取順序棧的棧頂元素StatusGetTop(SqStackS,SElemType&e){//如果棧

S空，返回

ERROR；如果棧

S不空，用

e

返回棧

S

的棧頂元素，并返回

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

//如果棧

S

為空，則返回

ERRORe=*(S.top-1);//將棧頂指針減

1后所指向的單元內(nèi)的值賦給

ereturnOK;}//GetTop（3）將元素壓入順序棧算法（進(jìn)棧）StatusPush(SqStack&S,SElemTypee){//將元素e

插入到棧S

中，成為新的棧頂元素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;//修改當(dāng)前棧的存儲空間}//if結(jié)束*S.top++=e;//先將e

送入棧頂，然后將棧頂指針加1returnOK;}//Push（4）將元素彈出順序棧算法（退棧）StatusPop(SqStack&S,SElemType&e){//如果棧S空，返回ERROR；如果棧S不空，刪除S棧頂元素，用e返回其值，并返回OK。if(S.top==S.base)returnERROR;//如果棧S為空，則返回ERRORe=*--S.top;//先令top減1，再將top所指單元值賦給ereturnOK;}//Pop（5）判?？辗馡ntStackEmpty(SqStackS){//如果棧S空，返回1；如果棧S不空，返回0if(S.top==S.base)return1;//如果棧S為空，則返回1elsereturn0;//如果棧S為空，則返回0}//Empty3.鏈棧（1）鏈棧結(jié)構(gòu)及數(shù)據(jù)類型棧的鏈?zhǔn)酱尜A結(jié)構(gòu)，也稱為鏈棧，它是一種限制運(yùn)算的鏈表，即規(guī)定鏈表中的插入和刪除運(yùn)算只能在鏈表開頭進(jìn)行。typedef

struct

SNode{SElemTypedata;structSNode*next;}SNode,*LinkStack（2）鏈棧的五種棧運(yùn)算（a）棧初始化voidInitStack(LinkStacktop){top=(LinkStack*)malloc(sizeof(SNode));top->next=NULL;}

（b）進(jìn)棧運(yùn)算StatusPush(LinkStack&top,SElemTypee){//將元素

e

插入到棧

S

中，成為新的棧頂元素q=(LinkStack*)malloc(sizeof(SNode));if(!q)exit(OVERFLOW);//存儲分配失敗q->data=e;q->next=top->next;top->next=q;returnOK;}（c）退棧運(yùn)算StatusPop(LinkStack&top,SElemType&e){//如果棧S空，返回ERROR；如果棧S不空，刪除S

的棧頂元素，用e

返回其值，并返回OK。if(!top->next)returnERROR;//如果棧S

為空，則返回ERRORe=top->next->data;//取出棧頂元素的值q=top->next;//q

指向棧頂元素top->next=q->next;//刪除棧頂元素free(q);//釋放棧頂元素所占的空間returnOK;}（d）取棧頂元素StatusGetTop(LinkStacktop,SElemType&e){//如果棧S空，返回ERROR；如果棧S不空，用e

返回棧S

的棧頂元素，并返回OK。if(!top->next)returnERROR;//如果棧S

為空，則返回ERRORelse{//如果棧S

不空，則返回棧頂元素e=top->next->data;returnOK;}}（5）判?？読ntStackEmpty(LinkStacktop){if(top->next==NULL)return

1;elsereturn

0;}

一、數(shù)制轉(zhuǎn)換3.2棧的應(yīng)用舉例十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)N：十進(jìn)制數(shù)，div：整除運(yùn)算，mod：求余運(yùn)算

NNdiv8Nmod8134816841682102125202由低位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個數(shù)位，但按從高位到低位的順序輸出。voidConversion(intN){/*對于任意的一個非負(fù)十進(jìn)制整數(shù)N，打印出與其等值的8進(jìn)制數(shù)*/StackS;intx;inte;InitStack(S);while(N){x=N%8;Push(S,x);/*將轉(zhuǎn)換后的數(shù)字壓入棧S*/N=N/8;}while(！StackEmpty(S)){Pop(S,e);printf(″%d″,e);}}算法3.1二、行編輯程序功能：接收用戶從終端輸入的數(shù)據(jù)或程序，并存入用戶的數(shù)據(jù)區(qū)。算法思想：設(shè)輸入緩沖區(qū)為一個棧結(jié)構(gòu)，每當(dāng)從終端接收一個字符后先作如下判別：若它既不是退格符（#）也不是退行符（@）,則將該字符入棧；若是退格符（#），則從棧頂刪去一個字符；若是退行符（@），則將棧清空。voidLineEdit(){InitStack(S);ch=getchar();While(ch!=EOF)//EOF為全文結(jié)束符{while(ch!=EOF&&ch!=“\n”){switch(ch){case“#”:pop(S,c);break;//當(dāng)棧非空時退棧case“@”:clearstack(S);break;//重置S為空棧default:push(S,ch);break;}//有效字符進(jìn)棧，但未考慮棧滿ch=getchar();}clearstack(S);if(ch!=EOF)ch=getchar();}destroystack(S);}三、表達(dá)式求值

任何一個表達(dá)式都是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成的。

操作數(shù)既可以是常數(shù)，也可以是被說明為變量或常量的標(biāo)識符。

運(yùn)算符可以分為算術(shù)運(yùn)算符、關(guān)系運(yùn)算符和邏輯運(yùn)算符三類。

基本界限符有左右括號和表達(dá)式結(jié)束符等。

假設(shè)操作數(shù)是整型常數(shù)，運(yùn)算符只含加、減、乘、除等四種運(yùn)算符，界限符有左右括號和表達(dá)式起始、結(jié)束符“?！?，如：＃（7+15）*（23-28/4）＃。

要對一個簡單的算術(shù)表達(dá)式求值，首先要了解算術(shù)四則運(yùn)算的規(guī)則，即：從左算到右；(2)先乘除，后加減；(3)先括號內(nèi)，后括號外。

運(yùn)算符和界限符可統(tǒng)稱為算符，它們構(gòu)成的集合命名為OP。

根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算過程中，任意兩個前后相繼出現(xiàn)的算符θ1和θ2之間的優(yōu)先關(guān)系必為下面三種關(guān)系之一：θ1<θ2，θ1的優(yōu)先權(quán)低于θ2。θ1=θ2，θ1的優(yōu)先權(quán)等于θ2。θ1>θ2，θ1的優(yōu)先權(quán)高于θ2。表3-1算符之間的優(yōu)先關(guān)系

實(shí)現(xiàn)算符優(yōu)先算法時需要使用兩個工作棧：一個稱作optr，用以存放運(yùn)算符；另一個稱作opnd，用以存放操作數(shù)或運(yùn)算的中間結(jié)果。

算法的基本過程如下：

首先初始化操作數(shù)棧opnd和運(yùn)算符棧optr，并將表達(dá)式起始符“＃”壓入運(yùn)算符棧；

依次讀入表達(dá)式中的每個字符，若是操作數(shù)則直接進(jìn)入操作數(shù)棧opnd，若是運(yùn)算符，則與運(yùn)算符棧optr的棧頂運(yùn)算符進(jìn)行優(yōu)先權(quán)比較，并做如下處理：(1)若棧頂運(yùn)算符的優(yōu)先級低于剛讀入的運(yùn)算符，則讓剛讀入的運(yùn)算符進(jìn)optr棧；(2)若棧頂運(yùn)算符的優(yōu)先級高于剛讀入的運(yùn)算符，則將棧頂運(yùn)算符退棧，送入θ，同時將操作數(shù)棧opnd退棧兩次，得到兩個操作數(shù)a、b，對a、b進(jìn)行θ運(yùn)算后，將運(yùn)算結(jié)果作為中間結(jié)果壓入opnd棧；(3)若棧頂運(yùn)算符的優(yōu)先級與剛讀入的運(yùn)算符的優(yōu)先級相同，說明左右括號相遇，只需將棧頂運(yùn)算符（左括號）退棧即可。算法具體描述如下：

intExpEvaluation()/*讀入一個簡單算術(shù)表達(dá)式并計(jì)算其值。optr和opnd分別為運(yùn)算符棧和運(yùn)算數(shù)棧，OP為運(yùn)算符集合*/{InitStack(opnd);InitStack(optr);Push(optr,′?！?;printf(″Pleaseinputanexpression(Endingwith＃):″);c=getchar();while(c!=′?！鋦|GetTop(optr)!=′＃′)/*GetTop()通過函數(shù)值返回棧頂元素*/

{if(!In(c,OP)){Push(opnd,c);c=getchar();}elseswitch(Precede(GetTop(optr),c)){case′<′:Push(optr,c);c=getchar();break;case′=′:Pop(optr,x); c=getchar();break;case′>′:Pop(optr,theta);

Pop(opnd,b);Pop(opnd,a);v=Execute(a,theta,b);/*對a和b進(jìn)行op運(yùn)算*/Push(opnd,v);break;}}return

GetTop(opnd);}例求表達(dá)式1+2*3-4/2的值，棧的變化如下。

步驟操作數(shù)棧運(yùn)算符棧說明開始兩棧均為空111進(jìn)入操作數(shù)棧+進(jìn)入運(yùn)算符棧2進(jìn)入操作數(shù)棧*進(jìn)入運(yùn)算符棧3進(jìn)入操作數(shù)棧退棧2*3進(jìn)入操作數(shù)棧退棧1+6進(jìn)入操作數(shù)棧234567891+12+12+1117+*236+*+步驟操作數(shù)棧運(yùn)算符棧說明107-進(jìn)入運(yùn)算符棧4進(jìn)入操作數(shù)棧/進(jìn)入運(yùn)算符棧2進(jìn)入操作數(shù)棧退棧4/2進(jìn)入操作數(shù)棧退棧7-2進(jìn)入操作數(shù)棧1112131415161774-74-/742-/772---53.4隊(duì)列

隊(duì)列也是一種操作受限的線性表，限制僅在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除。

把允許進(jìn)行插入的一端稱做隊(duì)尾(rear)，允許進(jìn)行刪除的一端稱做隊(duì)頭(front)。

向隊(duì)列中插入新元素稱為進(jìn)隊(duì)或入隊(duì)，新元素進(jìn)隊(duì)后就成為新的隊(duì)尾元素；從隊(duì)列中刪除元素稱為出隊(duì)或離隊(duì)，元素出隊(duì)后，其后繼元素就成為隊(duì)首元素。

隊(duì)列是一種先進(jìn)先出（firstinfirstout，F(xiàn)IFO）的線性表。

二、隊(duì)列的基本運(yùn)算1.初始化操作：InitQueue(&Q)：構(gòu)造一個空隊(duì)列。2.判空操作：QueueEmpty(Q)：若隊(duì)列為空，則返回TRUE，否則返回FALSE。3.進(jìn)隊(duì)操作：EnQueue(&Q，x)：在隊(duì)列Q的隊(duì)尾插入x。操作成功，返回值為TRUE，否則返回值為FALSE。4.出隊(duì)操作：DeQueue(&Q，&x)：使隊(duì)列Q的隊(duì)頭元素出隊(duì)，并用x帶回其值。操作成功，返回值為TRUE，否則返回值為FALSE。5.取隊(duì)頭元素操作：GetHead（Q，&x）：用x取得隊(duì)頭元素的值。操作成功，返回值為TRUE，否則返回值為FALSE。6.隊(duì)列置空操作：ClearQueue(&Q)：將隊(duì)列Q置為空隊(duì)列。7.隊(duì)列銷毀操作DestroyQueue(&Q)：釋放隊(duì)列的空間。8.求隊(duì)列長度操作：QueueLength(Q)：返回隊(duì)列Q的元素個數(shù)，即隊(duì)列Q的長度。三、

隊(duì)列的抽象數(shù)據(jù)類型描述ADTQueue{

數(shù)據(jù)元素：D={ai|ai

∈ElemSet，i=1,2,…,n,n≥0}

數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai

∈D,i=1,2,…,n}

基本操作：InitQueue(&Q)：初始化操作。設(shè)置一個空隊(duì)列。QueueEmpty(Q)：判空操作。若隊(duì)列為空，則返回TRUE，否則返回FALSE。EnQueue(&Q，x)：進(jìn)隊(duì)操作。在隊(duì)列Q的隊(duì)尾插入x，操作成功，返回值為TRUE，否則返回值為FALSE。DeQueue(&Q，&x)：出隊(duì)操作。使隊(duì)列Q的隊(duì)頭元素出隊(duì)，并用x帶回其值。操作成功，返回值為RUE，否則返回值為FALSE。GetHead（Q，&x）：取隊(duì)頭元素操作。用x取得隊(duì)元素的值，操作成功，返回值為TRUE，否則返回值為FALSE。ClearQueue(&Q)：隊(duì)列置空操作。將隊(duì)列Q置為空隊(duì)列。DestroyQueue(&Q)：隊(duì)列銷毀操作。釋放隊(duì)列的空間。QueueLength(Q)：返回隊(duì)列Q的元素個數(shù)，即隊(duì)列Q的長度。}ADTQueue四、隊(duì)列的表示和實(shí)現(xiàn)1.鏈隊(duì)列圖

鏈隊(duì)列隊(duì)列的鏈?zhǔn)酱鎯ΓQ為鏈隊(duì)列。一個鏈隊(duì)列顯然需要兩個分別指示隊(duì)頭（頭指針）和隊(duì)尾（尾指針）的指針才能唯一確定。鏈隊(duì)列可以定義如下：typedefstructQNode{QElemTypedata;/*數(shù)據(jù)域*/structQNode*next;/*指針域*/}Qnode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;yxQ.frontQ.rearQ.frontQ.rearyxQ.frontQ.rearxQ.frontQ.rear

鏈隊(duì)列的基本操作（1）初始化操作intInitQueue(LinkQueue&Q){/*將Q初始化為一個空的鏈隊(duì)列*/Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;returnOK;}（2）入隊(duì)操作StatusEnQueue(LinkQueue&Q,QElemTypee){/*將數(shù)據(jù)元素x插入到隊(duì)列Q中*/QueuePtr

p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data=e;p->next=NULL;Q->rear->next=p;Q->rear=p;returnOK;}（3）出隊(duì)操作intDeQueue(LinkQueue&Q,QElemType&e){/*將隊(duì)列Q的隊(duì)頭元素出隊(duì)，并用e返回其值*/QueuePtrp;if(Q->front==Q->rear)returnERROR;p=Q->front->next;e=p->data;Q->front->next=p->next;/*隊(duì)頭元素p出隊(duì)*/if(Q->rear==p)/*如隊(duì)中只有一個元素p，則p出隊(duì)后成為空隊(duì)*/Q->rear=Q->front;free(p);/*釋放存儲空間*/returnOK;}yxQ.frontQ.rearxQ.frontQ.rear2.循環(huán)隊(duì)列:隊(duì)列的順序表示和實(shí)現(xiàn)用一組連續(xù)的存儲單元依次存放隊(duì)列的元素，并設(shè)兩個指針front、rear分別指示隊(duì)頭和隊(duì)尾元素的位置。front：指向?qū)嶋H的隊(duì)頭；rear：指向?qū)嶋H隊(duì)尾的下一位置。初態(tài)：front＝rear＝0；

入隊(duì)：q[rear]=x;rear＝rear+1;出隊(duì)：x=q[front];front=front+1;56“假溢出”現(xiàn)象將隊(duì)列元素存放數(shù)組首尾相接，形成循環(huán)隊(duì)列隊(duì)頭、隊(duì)尾指針加1時從MAXSIZE-1直接進(jìn)到0，可用語言的取模(余數(shù))運(yùn)算實(shí)現(xiàn)隊(duì)頭指針進(jìn)1:front=(front+1)%MAXSIZE;隊(duì)尾指針進(jìn)1:rear=(rear+1)%MAXSIZE;隊(duì)列初始化：front=rear=0;5701234567front01234567front01234567frontrearAABCrearrear空隊(duì)列A進(jìn)隊(duì)B,C進(jìn)隊(duì)0123456701234567A退隊(duì)B退隊(duì)01234567D,E,F,G,H,I進(jìn)隊(duì)frontBCrearAfrontBCrearCrearDEFGHfrontI假溢出的解決方法：初態(tài)：front＝rear＝0；入隊(duì)：q[rear]=x；rear＝(rear+1)%MAXSIZE;出隊(duì)：x=q[front];front=(front+1)%MAXSIZE;隊(duì)空條件：front==rear;隊(duì)滿條件：(rear+1)%MAXSIZE==front循環(huán)隊(duì)列的類型定義：＃defineMAXSIZE100/*隊(duì)列的最大長度*/typedefstruct{

QElemType*base;/*初始化的動態(tài)分配存儲空間*/intfront;/*頭指針*/intrear;/*尾指針*/}SeqQueue;循環(huán)隊(duì)列的基本操作：（1）初始化操作voidInitQueue（SeqQueue&Q）{/*將Q初始化為一個空的循環(huán)隊(duì)列*/

Q.base=(QElemType*)malloc(MAXSIZE*sizeof(QElemType));

if(!

Q.base)exit(OVERFLOW);

Q.front=Q.rear=0;}（2）入隊(duì)操作intEnQueue(SeqQueue&Q,QElemTypex){/*將元素x入隊(duì)*/if((Q.rear+1)%MAXSIZE==Q.front)/*隊(duì)列已經(jīng)滿了*/returnERROR;Q.base［Q.rear］=x;Q.rear=(Q.rear+1)%MAXSIZE;/*重新設(shè)置隊(duì)尾指針*/returnOK;/*操作成功*/}（3）出隊(duì)操作

intDeQueue(SeqQueue&Q,QElemType&e){/*刪除隊(duì)列的隊(duì)頭元素，用e返回其值*/if（Q.front==Q.rear）returnERROR;

/*隊(duì)列為空*/e=Q.base［Q.front］;Q.front=(Q.front+1)%MAXSIZE;/*重新設(shè)置隊(duì)頭指針*/returnOK;/*操作成功*/}有兩個進(jìn)程同時存在于一個程序中。其中第一個進(jìn)程在屏幕上連續(xù)顯示字符“A”，與此同時，程序不斷檢測鍵盤是否有輸入，如果有輸入就讀入