第4章棧和隊列

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

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

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

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

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

棧頂棧底

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

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

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

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

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

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

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

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

InitStack

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

4.2棧DestroyStack

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

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

功能：在棧頂插入一個元素x

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

4.2棧Pop

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

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

4.2棧Empty

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

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

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

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

top

4.2棧出棧：top減1進棧：top加1?？眨簍op=-1

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

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

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

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

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

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

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

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

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

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

4.2棧棧1的底固定在下標為0的一端；棧2的底固定在下標為StackSize-1的一端。

top1和top2分別為棧1和棧2的棧頂指針；Stack_Size為整個數(shù)組空間的大小（圖中用S表示）；a1

a2…aitop1012…

…S-1兩棧共享空間top2bj

……b2

b1棧1底棧2底

4.2棧top1=-1什么時候棧1為空？a1

a2…aitop1012…

…S-1兩棧共享空間top2bj

……b2

b1top1

4.2棧top1=-1什么時候棧1為空？a1

a2…aitop1012…

…S-1兩棧共享空間top2bj

……b2

b1什么時候棧2為空？top2top2=Stack_Size

4.2棧top1=-1什么時候棧1為空？a1

a2……aitop1012…

…S-1兩棧共享空間top2bj

……b2

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

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

inttop1,top2;//各自棧頂元素在數(shù)組中的下標}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；兩棧共享空間的實現(xiàn)——插入操作接口：voidPush(inti,DataTypex);

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

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

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

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

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

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

4.2棧棧的鏈接存儲結(jié)構(gòu)及實現(xiàn)棧頂棧底鏈棧：棧的鏈接存儲結(jié)構(gòu)topanan-1a1∧firsta1a2an∧ai兩種示意圖在內(nèi)存中對應(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∧鏈棧的實現(xiàn)——插入xstop操作接口：voidPush(DataTypex);

為什么沒有判斷棧滿？

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

topanan-1a1∧topp

top++可以嗎？

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

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

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

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

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

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

InitQueue

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

4.3隊列

DestroyQueue

前置條件：隊列已存在輸入：無功能：銷毀隊列輸出：無后置條件：釋放隊列所占用的存儲空間

EnQueue

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

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

4.3隊列

DeQueue

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

GetQueue

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

4.3隊列Empty

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

intfront,rear;//隊頭和隊尾指針}CirQueue;

4.3隊列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)隊列的實現(xiàn)——入隊01234入隊出隊a3a4rearfronta5rear

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

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

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

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

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

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

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

4.3隊列操作接口：

LinkQueue();

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

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

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

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

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

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

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

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

Q.rear=s;}

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