第4章棧和隊(duì)列

數(shù)據(jù)結(jié)構(gòu)與算法作者：胡明王紅梅出版社：電子工業(yè)出版社郵箱：wanghm@第4章棧和隊(duì)列本章的基本內(nèi)容是：兩種特殊的線性表——棧和隊(duì)列從數(shù)據(jù)結(jié)構(gòu)角度看，棧和隊(duì)列是操作受限的線性表，他們的邏輯結(jié)構(gòu)相同。從抽象數(shù)據(jù)類型角度看，棧和隊(duì)列是兩種重要的抽象數(shù)據(jù)類型。

4.1引言例4-1括號(hào)匹配問(wèn)題C語(yǔ)言對(duì)于算術(shù)表達(dá)式中括號(hào)的配對(duì)原則是：右括號(hào)“)”與其前面最近的尚未配對(duì)的左括號(hào)“(”相配對(duì)。例如，算術(shù)表達(dá)式((x+5)*6-38))%5中的括號(hào)沒(méi)有正確配對(duì)，多了一個(gè)“)”。如何判斷給定表達(dá)式中所含括號(hào)是否正確配對(duì)呢？如果順序掃描表達(dá)式，當(dāng)掃描到右括號(hào)“)”時(shí)，需要查找已經(jīng)掃描過(guò)的最后一個(gè)尚未配對(duì)的左括號(hào)“(”，對(duì)于“(”具有最后掃描到最先配對(duì)的特點(diǎn)。如何保存已經(jīng)掃描過(guò)的尚未配對(duì)的左括號(hào)“(”，并對(duì)其實(shí)施配對(duì)操作呢？

4.1引言例4-2函數(shù)的嵌套調(diào)用函數(shù)的嵌套調(diào)用是在函數(shù)的執(zhí)行過(guò)程中再調(diào)用其他函數(shù)。當(dāng)函數(shù)C執(zhí)行結(jié)束時(shí)，應(yīng)該返回到什么位置呢？工作棧是如何保證調(diào)用次序的正確性呢？

4.1引言例4-3銀行排隊(duì)問(wèn)題在需要順序操作但人群眾多的場(chǎng)合，排隊(duì)是現(xiàn)代文明的一種表現(xiàn)。例如，儲(chǔ)戶到銀行辦理個(gè)人儲(chǔ)蓄業(yè)務(wù)，需要領(lǐng)取一張排隊(duì)單，在排隊(duì)單上打印了儲(chǔ)戶的順序號(hào)以及前面的人數(shù)，儲(chǔ)戶只需坐在椅子上等待，儲(chǔ)蓄窗口會(huì)順次叫號(hào)。如何實(shí)現(xiàn)這種先來(lái)先服務(wù)的功能呢？

4.1引言例4-4打印緩沖區(qū)在計(jì)算機(jī)系統(tǒng)中，經(jīng)常會(huì)遇到兩個(gè)設(shè)備在處理數(shù)據(jù)時(shí)速度不匹配的問(wèn)題。例如，將計(jì)算機(jī)內(nèi)存中的數(shù)據(jù)傳送到打印機(jī)上打印輸出。如何實(shí)現(xiàn)這種先來(lái)先服務(wù)的功能呢？棧的邏輯結(jié)構(gòu)（a1,a2,……,an）棧：限定僅在表的一端進(jìn)行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。空棧：不含任何數(shù)據(jù)元素的棧。

棧頂棧底

4.2棧a1a2a3入棧出棧棧底棧頂插入：入棧、進(jìn)棧、壓棧刪除：出棧、彈棧棧頂棧頂棧的邏輯結(jié)構(gòu)

4.2棧棧的操作特性：后進(jìn)先出a1a2a3入棧出棧棧底棧頂插入：入棧、進(jìn)棧、壓棧刪除：出棧、彈棧棧頂棧的邏輯結(jié)構(gòu)

4.2棧例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂c棧頂情況1：棧的邏輯結(jié)構(gòu)

4.2棧棧底棧頂ab棧頂c棧頂出棧序列：c出棧序列：c、b出棧序列：c、b、a例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu)情況1：

4.2棧棧底棧頂ab棧頂出棧序列：b情況2：例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu)

4.2棧棧底a出棧序列：b出棧序列：b、c出棧序列：b、c、ac棧頂棧頂注意：棧只是對(duì)表插入和刪除操作的位置進(jìn)行了限制，并沒(méi)有限定插入和刪除操作進(jìn)行的時(shí)間。例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu)情況2：

4.2棧棧的抽象數(shù)據(jù)類型定義ADTStackData

棧中元素具有相同類型及后進(jìn)先出特性，相鄰元素具有前驅(qū)和后繼關(guān)系Operation

InitStack

前置條件：棧不存在輸入：無(wú)功能：棧的初始化輸出：無(wú)后置條件：構(gòu)造一個(gè)空棧

4.2棧DestroyStack

前置條件：棧已存在輸入：無(wú)功能：銷毀棧輸出：無(wú)后置條件：釋放棧所占用的存儲(chǔ)空間Push

前置條件：棧已存在輸入：元素值x

功能：在棧頂插入一個(gè)元素x

輸出：如果插入不成功，拋出異常后置條件：如果插入成功，棧頂增加了一個(gè)元素棧的抽象數(shù)據(jù)類型定義

4.2棧Pop

前置條件：棧已存在輸入：無(wú)功能：刪除棧頂元素輸出：如果刪除成功，返回被刪元素值，否則，拋出異常后置條件：如果刪除成功，棧減少了一個(gè)元素GetTop

前置條件：棧已存在輸入：無(wú)功能：讀取當(dāng)前的棧頂元素輸出：若棧不空，返回當(dāng)前的棧頂元素值后置條件：棧不變棧的抽象數(shù)據(jù)類型定義

4.2棧Empty

前置條件：棧已存在輸入：無(wú)功能：判斷棧是否為空輸出：如果棧為空，返回1，否則，返回0

后置條件：棧不變endADT棧的抽象數(shù)據(jù)類型定義

4.2棧棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序?！獥５捻樞虼鎯?chǔ)結(jié)構(gòu)如何改造數(shù)組實(shí)現(xiàn)棧的順序存儲(chǔ)？

012345678a1確定用數(shù)組的哪一端表示棧底。附設(shè)指針top指示棧頂元素在數(shù)組中的位置。

top

4.2棧出棧：top減1進(jìn)棧：top加1?？眨簍op=-1

012345678a1topa2topa3top棧滿：top=MAX_SIZE-1棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)

4.2棧順序棧的存儲(chǔ)結(jié)構(gòu)定義：constintStackSize=10;//假定棧元素最多10個(gè)typedefintDataType;//DataType為棧元素的數(shù)據(jù)類型typedefstruct{DataTypedata[StackSize];//存放棧元素的數(shù)組

inttop;//棧頂指針，為棧頂元素在數(shù)組中的下標(biāo)}SeqStack;

4.2棧順序棧的實(shí)現(xiàn)——入棧voidPush(SeqStack&S,DataTypex){if(S.top==StackSize-1){printf("上溢");exit(-1);}S.data[++S.top]=x;}操作接口：

voidPush(SeqStack&S,DataTypex);時(shí)間復(fù)雜度？data[++top]=x

4.2棧順序棧的實(shí)現(xiàn)——出棧DataTypePop(SeqStack&S){if(S.top==-1){printf("下溢");exit(-1);}x=S.data[S.top--];returnx;}操作接口：

DataTypePop(SeqStack&S);時(shí)間復(fù)雜度？

4.2棧兩棧共享空間解決方案1：直接解決：為每個(gè)棧開(kāi)辟一個(gè)數(shù)組空間。解決方案2：

順序棧單向延伸——使用一個(gè)數(shù)組來(lái)存儲(chǔ)兩個(gè)棧在一個(gè)程序中需要同時(shí)使用具有相同數(shù)據(jù)類型的兩個(gè)棧，如何順序存儲(chǔ)這兩個(gè)棧？會(huì)出現(xiàn)什么問(wèn)題？如何解決？

4.2棧兩棧共享空間：使用一個(gè)數(shù)組來(lái)存儲(chǔ)兩個(gè)棧，讓一個(gè)棧的棧底為該數(shù)組的始端，另一個(gè)棧的棧底為該數(shù)組的末端，兩個(gè)棧從各自的端點(diǎn)向中間延伸。兩棧共享空間

4.2棧棧1的底固定在下標(biāo)為0的一端；棧2的底固定在下標(biāo)為StackSize-1的一端。

top1和top2分別為棧1和棧2的棧頂指針；Stack_Size為整個(gè)數(shù)組空間的大?。▓D中用S表示）；a1

a2…aitop1012…

…S-1兩棧共享空間top2bj

……b2

b1棧1底棧2底

4.2棧top1=-1什么時(shí)候棧1為空？a1

a2…aitop1012…

…S-1兩棧共享空間top2bj

……b2

b1top1

4.2棧top1=-1什么時(shí)候棧1為空？a1

a2…aitop1012…

…S-1兩棧共享空間top2bj

……b2

b1什么時(shí)候棧2為空？top2top2=Stack_Size

4.2棧top1=-1什么時(shí)候棧1為空？a1

a2……aitop1012…

…S-1兩棧共享空間top2bj

……b2

b1什么時(shí)候棧2為空？top2=Stack_Size什么時(shí)候棧滿？top2=top1+1

4.2棧兩棧共享空間的存儲(chǔ)結(jié)構(gòu)定義：constintStackSize=10;//假設(shè)兩個(gè)棧最多10個(gè)元素typedefintDataType;//DataType為兩個(gè)棧的數(shù)據(jù)類型typedefstruct{DataTypedata[StackSize];//存放兩個(gè)棧的數(shù)組

inttop1,top2;//各自棧頂元素在數(shù)組中的下標(biāo)}BothStack;

4.2棧1.如果棧滿，則拋出上溢異常；2.判斷是插在棧1還是棧2；2.1若在棧1插入，則2.1.1top1加1;

2.1.2在top1處填入x；2.2若在棧2插入，則2.2.1top2減1;

2.2.2在top2處填入x；兩棧共享空間的實(shí)現(xiàn)——插入操作接口：voidPush(inti,DataTypex);

4.2棧1.若是在棧1刪除，則

1.1若棧1為空棧，拋出下溢異常；

1.2刪除并返回棧1的棧頂元素；2.若是在棧2刪除，則

2.1若棧2為空棧，拋出下溢異常；

2.2刪除并返回棧2的棧頂元素；兩棧共享空間的實(shí)現(xiàn)——?jiǎng)h除操作接口：DataTypePop(inti);

4.2棧棧的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)鏈棧：棧的鏈接存儲(chǔ)結(jié)構(gòu)firsta1a2an∧ai鏈棧需要加頭結(jié)點(diǎn)嗎？如何改造鏈表實(shí)現(xiàn)棧的鏈接存儲(chǔ)？將哪一端作為棧頂？將鏈頭作為棧頂，方便操作。鏈棧不需要附設(shè)頭結(jié)點(diǎn)。

4.2棧棧的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)棧頂棧底鏈棧：棧的鏈接存儲(chǔ)結(jié)構(gòu)topanan-1a1∧firsta1a2an∧ai兩種示意圖在內(nèi)存中對(duì)應(yīng)同一種狀態(tài)，啟示？topa1an-1an∧棧頂棧底

4.2棧voidPush(Node*top,DataTypex){s=(Node*)malloc(sizeof(Node));s->data=x;s->next=top;top=s;}topanan-1a1∧鏈棧的實(shí)現(xiàn)——插入xstop操作接口：voidPush(DataTypex);

為什么沒(méi)有判斷棧滿？

4.2棧DataTypePop(Node*top){if(top==NULL){printf("下溢");exit(-1);}x=top->data;p=top;top=top->next;free(p);returnx;}鏈棧的實(shí)現(xiàn)——插入操作接口：DataTypePop();

topanan-1a1∧topp

top++可以嗎？

4.2棧順序棧和鏈棧的比較時(shí)間性能：相同，都是常數(shù)時(shí)間O(1)?？臻g性能：順序棧：有元素個(gè)數(shù)的限制和空間浪費(fèi)的問(wèn)題。鏈棧：沒(méi)有棧滿的問(wèn)題，只有當(dāng)內(nèi)存沒(méi)有可用空間時(shí)才會(huì)出現(xiàn)棧滿，但是每個(gè)元素都需要一個(gè)指針域，從而產(chǎn)生了結(jié)構(gòu)性開(kāi)銷。

總之，當(dāng)棧的使用過(guò)程中元素個(gè)數(shù)變化較大時(shí)，用鏈棧是適宜的，反之，應(yīng)該采用順序棧。

4.2棧隊(duì)列的邏輯結(jié)構(gòu)隊(duì)列：只允許在一端進(jìn)行插入操作，而另一端進(jìn)行刪除操作的線性表。允許插入（也稱入隊(duì)、進(jìn)隊(duì)）的一端稱為隊(duì)尾，允許刪除（也稱出隊(duì)）的一端稱為隊(duì)頭?？贞?duì)列：不含任何數(shù)據(jù)元素的隊(duì)列。（a1,a2,……,an）隊(duì)尾隊(duì)頭

4.3隊(duì)列隊(duì)列的操作特性：先進(jìn)先出a1a2a3入隊(duì)隊(duì)尾隊(duì)頭出隊(duì)隊(duì)頭隊(duì)列的邏輯結(jié)構(gòu)

4.3隊(duì)列隊(duì)列的抽象數(shù)據(jù)類型定義ADTQueueData

隊(duì)列中元素具有相同類型及先進(jìn)先出特性，相鄰元素具有前驅(qū)和后繼關(guān)系Operation

InitQueue

前置條件：隊(duì)列不存在輸入：無(wú)功能：初始化隊(duì)列輸出：無(wú)后置條件：創(chuàng)建一個(gè)空隊(duì)列

4.3隊(duì)列

DestroyQueue

前置條件：隊(duì)列已存在輸入：無(wú)功能：銷毀隊(duì)列輸出：無(wú)后置條件：釋放隊(duì)列所占用的存儲(chǔ)空間

EnQueue

前置條件：隊(duì)列已存在輸入：元素值x

功能：在隊(duì)尾插入一個(gè)元素輸出：如果插入不成功，拋出異常后置條件：如果插入成功，隊(duì)尾增加了一個(gè)元素隊(duì)列的抽象數(shù)據(jù)類型定義

4.3隊(duì)列

DeQueue

前置條件：隊(duì)列已存在輸入：無(wú)功能：刪除隊(duì)頭元素輸出：如果刪除成功，返回被刪元素值后置條件：如果刪除成功，隊(duì)頭減少了一個(gè)元素

GetQueue

前置條件：隊(duì)列已存在輸入：無(wú)功能：讀取隊(duì)頭元素輸出：若隊(duì)列不空，返回隊(duì)頭元素后置條件：隊(duì)列不變隊(duì)列的抽象數(shù)據(jù)類型定義

4.3隊(duì)列Empty

前置條件：隊(duì)列已存在輸入：無(wú)功能：判斷隊(duì)列是否為空輸出：如果隊(duì)列為空，返回1，否則，返回0

后置條件：隊(duì)列不變endADT隊(duì)列的抽象數(shù)據(jù)類型定義

4.3隊(duì)列01234入隊(duì)出隊(duì)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)順序隊(duì)列——隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)？例：a1a2a3a4依次入隊(duì)a1a2a3a4rearrearrearrear入隊(duì)操作時(shí)間性能為O(1)

4.3隊(duì)列如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)？例：a1a2依次出隊(duì)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a1a2a3a4rear

4.3隊(duì)列如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)？例：a1a2依次出隊(duì)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a2a3a4rear

4.3隊(duì)列如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)？例：a1a2依次出隊(duì)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a3a4rear出隊(duì)操作時(shí)間性能為O(n)

4.3隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何改進(jìn)出隊(duì)的時(shí)間性能？放寬隊(duì)列的所有元素必須存儲(chǔ)在數(shù)組的前n個(gè)單元這一條件，只要求隊(duì)列的元素存儲(chǔ)在數(shù)組中連續(xù)的位置。設(shè)置隊(duì)頭、隊(duì)尾兩個(gè)指針

4.3隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)例：a1a2a3a4依次入隊(duì)a1a2a3a4rearrearrearrear入隊(duì)操作時(shí)間性能仍為O(1)frontrear約定：隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針rear指向隊(duì)尾元素。

4.3隊(duì)列例：a1a2依次出隊(duì)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a1a2a3a4rearfrontfrontfront出隊(duì)操作時(shí)間性能提高為O(1)

4.3隊(duì)列例：a1a2依次出隊(duì)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a3a4rearfront隊(duì)列的移動(dòng)有什么特點(diǎn)？

4.3隊(duì)列例：a1a2依次出隊(duì)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a3a4rearfront整個(gè)隊(duì)列向數(shù)組下標(biāo)較大方向移動(dòng)單向移動(dòng)性

4.3隊(duì)列假溢出：當(dāng)元素被插入到數(shù)組中下標(biāo)最大的位置上之后，隊(duì)列的空間就用盡了，盡管此時(shí)數(shù)組的低端還有空閑空間，這種現(xiàn)象叫做假溢出。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)繼續(xù)入隊(duì)會(huì)出現(xiàn)什么情況？01234入隊(duì)出隊(duì)a3a4rearfronta5rear

4.3隊(duì)列循環(huán)隊(duì)列：將存儲(chǔ)隊(duì)列的數(shù)組頭尾相接。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何解決假溢出？01234入隊(duì)出隊(duì)a3a4fronta5rearreara6

4.3隊(duì)列不存在物理的循環(huán)結(jié)構(gòu)，用軟件方法實(shí)現(xiàn)。求模：（4＋1）mod5＝0隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何實(shí)現(xiàn)循環(huán)隊(duì)列？01234入隊(duì)出隊(duì)a3a4frontreara6

4.3隊(duì)列如何判斷循環(huán)隊(duì)列隊(duì)空？隊(duì)空的臨界狀態(tài)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a3rearfront

4.3隊(duì)列如何判斷循環(huán)隊(duì)列隊(duì)空？執(zhí)行出隊(duì)操作隊(duì)空：front=rear隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a3frontrearfront

4.3隊(duì)列如何判斷循環(huán)隊(duì)列隊(duì)滿？隊(duì)滿的臨界狀態(tài)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a3a4fronta5reara6

4.3隊(duì)列如何判斷循環(huán)隊(duì)列隊(duì)滿？執(zhí)行入隊(duì)操作隊(duì)滿：front=rear隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a3a4fronta5reara6reara7

4.3隊(duì)列方法一：附設(shè)一個(gè)存儲(chǔ)隊(duì)列中元素個(gè)數(shù)的變量num，當(dāng)num=0時(shí)隊(duì)空，當(dāng)num=QueueSize時(shí)為隊(duì)滿；方法二：修改隊(duì)滿條件，浪費(fèi)一個(gè)元素空間，隊(duì)滿時(shí)數(shù)組中只有一個(gè)空閑單元；方法三：設(shè)置標(biāo)志flag，當(dāng)front=rear且flag=0時(shí)為隊(duì)空，當(dāng)front=rear且flag=1時(shí)為隊(duì)滿。如何確定不同的隊(duì)空、隊(duì)滿的判定條件？為什么要將隊(duì)空和隊(duì)滿的判定條件分開(kāi)？隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)

4.3隊(duì)列隊(duì)滿的條件：(rear+1)modQueueSize=front隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)rear<fronta3a4fronta5reara6出隊(duì)01234入隊(duì)rear>fronta3a4fronta5reara6出隊(duì)

4.3隊(duì)列循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)定義：constintQueueSize=10;//定義數(shù)組的最大長(zhǎng)度typedefintDataType;//DataType為隊(duì)列元素的數(shù)據(jù)類型typedefstruct{DataTypedata[QueueSize];//存放隊(duì)列元素的數(shù)組

intfront,rear;//隊(duì)頭和隊(duì)尾指針}CirQueue;

4.3隊(duì)列voidEnQueue(CirQueue&Q,DataTypex){if((Q.rear+1)%QueueSize==Q.front){printf("上溢");exit(-1);}Q.rear=(Q.rear+1)%QueueSize;Q.data[Q.rear]=x;}循環(huán)隊(duì)列的實(shí)現(xiàn)——入隊(duì)01234入隊(duì)出隊(duì)a3a4rearfronta5rear

4.3隊(duì)列01234入隊(duì)a4a5a6出隊(duì)DataTypeDeQueue(CirQueue&Q){if(Q.rear==Q.front){printf("下溢");exit(-1);}Q.front=(Q.front+1)%QueueSize;returnQ.data[Q.front];}

循環(huán)隊(duì)列的實(shí)現(xiàn)——出隊(duì)frontrearfronta3

4.3隊(duì)列DataTypeGetFront(CirQueue&Q){if(Q.rear==Q.front){printf("下溢");exit(-1);}i=(Q.front+1)%QueueSize;

returnQ.data[i];}循環(huán)隊(duì)列的實(shí)現(xiàn)——讀隊(duì)頭元素01234入隊(duì)a4a5a6出隊(duì)frontreara3i

4.3隊(duì)列隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)鏈隊(duì)列：隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)隊(duì)頭指針即為鏈表的頭指針firsta1a2an∧如何改造單鏈表實(shí)現(xiàn)隊(duì)列的鏈接存儲(chǔ)？rearfront

4.3隊(duì)列隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)非空鏈隊(duì)列fronta1a2an∧rear空鏈隊(duì)列front∧rear

4.3隊(duì)列鏈隊(duì)列的存儲(chǔ)結(jié)構(gòu)定義：typedefintDataType;//DataType為隊(duì)列元素的數(shù)據(jù)類型typedefstructNode//定義鏈隊(duì)列的結(jié)點(diǎn)結(jié)構(gòu){DataTypedata;Node*next;}Node;typedefstruct//定義鏈隊(duì)列{Node*front,*rear;}LinkQueue;

4.3隊(duì)列操作接口：

LinkQueue();

算法描述：voidInitQueue(LinkQueue&Q){s=(Node*)malloc(sizeof(Node));s->next=NULL;Q.front=Q.rear=s;}鏈隊(duì)列的實(shí)現(xiàn)——隊(duì)列的初始化front∧rear

4.3隊(duì)列xs鏈隊(duì)列的實(shí)現(xiàn)——入隊(duì)操作接口：

voidEnQueue(DataTypex);fronta1an∧rear∧rearfrontxs∧∧rearrear算法描述：s->next=NULL;rear->next=s;rear=s;如何沒(méi)有頭結(jié)點(diǎn)會(huì)怎樣？

4.3隊(duì)列xs鏈隊(duì)列的實(shí)現(xiàn)——入隊(duì)操作接口：

voidEnQueue(DataTypex);fronta2an∧rear∧rear算法描述：s->next=NULL;rear->next=s;rear=s;如何沒(méi)有頭結(jié)點(diǎn)會(huì)怎樣？a1

4.3隊(duì)列鏈隊(duì)列的實(shí)現(xiàn)——入隊(duì)操作接口：

voidEnQueue(DataTypex);front=rear=NULLxs∧rear算法描述：s->next=NULL;rear=s;front=s;如何沒(méi)有頭結(jié)點(diǎn)會(huì)怎樣？front算法描述：s->next=NULL;rear->next=s;rear=s;

4.3隊(duì)列鏈隊(duì)列的實(shí)現(xiàn)——入隊(duì)voidEnQueue(LinkQueue&Q,DataTypex){s=(Node*)malloc(sizeof(Node));s->data=x;s->next=NULL;Q.rear->next=s;

Q.rear=s;}

4.3隊(duì)列鏈隊(duì)列的實(shí)現(xiàn)——出隊(duì)fronta1a2an∧rearp算法描述：