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

1、第3章棧和隊列棧和隊列是兩種應(yīng)用非常廣泛的數(shù)據(jù)結(jié)構(gòu)，它們都來自線性表數(shù)據(jù)結(jié)構(gòu)，都是“操作受限”的線性表。 棧在計算機(jī)的實現(xiàn)有多種方式：硬堆棧：利用CPU中的某些寄存器組或類似的硬件或使用內(nèi)存的特殊區(qū)域來實現(xiàn)。這類堆棧容量有限， 但速度很快；軟堆棧：這類堆棧主要在內(nèi)存中實現(xiàn)。堆棧容量可以達(dá)到很大。在實現(xiàn)方式上，又有動態(tài)方式和靜態(tài)方式兩種。本章將棧和隊列的基本概念、結(jié)構(gòu)、基本操作以及這些操作的具體實現(xiàn)。3.1棧3.1.1棧的基本概念1棧的概念棧(Stack)：是限制在表的一端進(jìn)行和刪除操作的線性表。又稱為后進(jìn)先出LIFO (Last InOut)或先進(jìn)后出FILO (棧頂(Top)：允許進(jìn)行In

2、Last Out)線性表。、刪除操作的一端，又稱為表尾。用棧頂指針(top)來指示棧頂元素。棧底(Bottom)：是固定端，又稱為表頭。 空棧：當(dāng)表中沒有元素時稱為空棧。出棧(pop)進(jìn)棧（push）設(shè)棧S=(a1，a2，an)，則a1 稱為棧底元素，an為棧頂元素，如圖 3-1所示。棧中元素按a1，a2，an的次序 進(jìn)棧，退棧的第一個元素應(yīng)為棧頂元素。即棧的修改是按后進(jìn)先出的原則進(jìn)行的。topanai a2 a1順序棧示意圖bottom圖3-12棧的抽象數(shù)據(jù)類型定義ADT Stack數(shù)據(jù)對象：D = ai|aiElemSet,i=1,2,n，n0 數(shù)據(jù)關(guān)系：R =|ai-1，aiD,i=2,

3、3,n 基本操作：初始化、進(jìn)棧、出棧、取棧頂元素等 ADT Stack3.1.2棧的順序 用一維數(shù)組來棧的順序表示結(jié)構(gòu)簡稱為順序棧，和線性表相類似，棧。根據(jù)數(shù)組是否可以根據(jù)需要增大，又可分為靜態(tài)順序棧和動態(tài)順序棧。靜態(tài)順序棧實現(xiàn)簡單，但不能根據(jù)需要增大棧的空間；動態(tài)順序棧可以根據(jù)需要增大棧的空間，但實現(xiàn)稍為復(fù)雜。3.1.2.1棧的動態(tài)順序表示采用動態(tài)一維數(shù)組來的大小可以根據(jù)需要增加。棧。所謂動態(tài)，指的是棧用bottom表示棧底指針，棧底固定不變的；棧頂 則隨著進(jìn)棧和退棧操作而變化。用top(稱為棧頂指針)指示當(dāng)前棧頂位置。用tottom作為?？盏臉?biāo)記，每次top指向棧頂數(shù)組中的下一個位置。結(jié)點

4、進(jìn)棧：首先將數(shù)據(jù)元素保存到棧頂(top所指的當(dāng)前位置)，然后執(zhí)行top加1，使top指向棧頂位置;的下一個結(jié)點出棧：首先執(zhí)行top減1，使top指向棧頂元素的位置，然后將棧頂元素取出。圖3-2是一個動態(tài)棧的變化示意圖。topc b atopbottomtopbottomabottom空棧元素a進(jìn)棧top元素b，c進(jìn)棧f e d b atopb abottombottom元素c退棧元素d，e，f進(jìn)棧圖3-2(動態(tài))堆棧變化示意圖基本操作的實現(xiàn)1棧的類型定義#defineSTACK_SIZE100/*棧初始向量大小 */#define STACKINCREMENT 10量 */*空間分配增#typ

5、edefElemType ;typedef struct sqstack*/ElemType*bottom;/*棧不存在時值為NULLElemType*top;/*棧頂指針 */stacksize ;位 */SqStack ;/*當(dāng)前已分配空間，以元素為單2S棧的初始化us Init_Stack(void)SqStackS ;S.bottom=(ElemType *)malloc(STACK_SIZE*sizeof(ElemType);if (! S.bottom) return ERROR;S.top=S.bottom ;*/S. stacksize=STACK_SIZE; return O

6、K ;/*棧空時棧頂和棧底指針相同3S壓棧(元素進(jìn)棧)us push(SqStack S , ElemTypee)if(S.top-S.bottom=S. stacksize-1)S.bottom=(ElemType *)realloc(S.STACKINCREMENT+STACK_SIZE)*sizeof(ElemType);*/* 棧滿，追加空間if (! S.bottom)returnERROR;S.top=S.bottom+S. stacksize ;S. stacksize+=STACKINCREMENT ;*S.top=e;*/S.top+ ; /* 棧頂指針加1，e成為新的棧頂4

7、S彈棧(元素出棧)us pop( SqStack/*彈出棧頂元素*/S, ElemType*e )if ( S.top= S.bottom )return ERROR ;S.top- ; e=*S. top ;/*/?？?，返回失敗標(biāo)志returnOK ;3.1.2.2棧的靜態(tài)順序表示采用靜態(tài)一維數(shù)組來棧。棧底固定不變的，而棧頂則隨著進(jìn)棧和退棧操作變化的，棧底固定不變的；棧頂則隨著進(jìn)棧和退棧操作而變化，用一個整型變量top(稱為棧頂指針)來指示當(dāng) 前棧頂位置。用top=0表示?？盏某跏紶顟B(tài)，每次top指向棧頂在數(shù)組中的位置。結(jié)點進(jìn)棧：首先執(zhí)行top加1，使top指向新的棧頂位置，然后將數(shù)據(jù)元素保

8、存到棧頂(top所指的當(dāng)前位置)。結(jié)點出棧：首先把top指向的棧頂元素取出，然后執(zhí)行top減1，使top指向新的棧頂位置。若棧的數(shù)組有Maxsize個元素，則top=Maxsize- 1時棧滿。圖3-3是一個大小為5的棧的變化示意圖。tope d b ac b atoptopb atopbottomatopbottombottombottombottomTop=1Top=3Top=4棧滿空棧Top=2元素c進(jìn)棧1個元素進(jìn)棧3個元素進(jìn)棧圖3-3靜態(tài)堆棧變化示意圖基本操作的實現(xiàn)1棧的類型定義# define*/MAX_STACK_SIZE100/*棧向量大小# typedeftypedef str

9、uctElemType ;sqstackElemTypestack_arrayMAX_STACK_SIZE ; top;SqStack ;2 棧的初始化SqStack Init_Stack(void)SqStackS ;S.bottom=S.top=0 ;return(S) ;3S壓棧(元素進(jìn)棧)us push(SqStack S , ElemTypee)/* 使數(shù)據(jù)元素e進(jìn)棧成為新的棧頂*/if(S.top=MAX_STACK_SIZE-1)returnERROR;/*/棧滿，返回錯誤標(biāo)志S.top+ ;/* 棧頂指針加1*/* e成為新的棧頂S.stack_arrayS.top=e*/;r

10、eturn OK;/*/壓棧成功4S彈棧(元素出棧)uspop( SqStackS, ElemType*e )/*彈出棧頂元素*/if ( S.top=0 )return ERROR ;/*/?？?，返回錯誤標(biāo)志*e=S.stack_arrayS.top ; S.top- ;return OK ;當(dāng)棧滿時做進(jìn)棧運算必定產(chǎn)生空間溢出，簡稱“上溢”。上溢是一種出錯狀態(tài)，應(yīng)設(shè)法避免。當(dāng)?？諘r做退棧運算也將產(chǎn)生溢出，簡稱“下溢”。下溢則可能是正?，F(xiàn)象，因為棧在使用時，其初態(tài)或終 態(tài)都是空棧，所以下溢常用來作為控制轉(zhuǎn)移的條件。3.1.3棧的鏈?zhǔn)奖硎?棧的鏈?zhǔn)奖硎緱５逆準(zhǔn)浇Y(jié)構(gòu)稱為鏈棧，是運算受限的單鏈表。其

11、和刪除操作只能在表頭位置上進(jìn)行。因此，鏈棧沒有必要像單鏈表那樣附加頭結(jié)點，棧頂指針top就是鏈表的頭指針。圖3-4是棧的鏈?zhǔn)奖硎拘问?。toptopa4 a3 a2a1鏈棧的結(jié)點類型說明如下：空棧typedefstruct Stack_NodeElemTypedata ;struct Stack_Node Stack_Node ;*next ;非空棧圖3-4 鏈棧形式2(1)鏈?；静僮鞯膶崿F(xiàn)棧的初始化Stack_Node*Init_Link_Stack(void)Stack_Node*top ;top=(Stack_Node*)malloc(sizeof(Stack_Node ) ; top-

12、next=NULL ;return(top) ;(2)S壓棧(元素進(jìn)棧)us push(Stack_Node *top , ElemTypee)Stack_Node*p ;p=(Stack_Node*)malloc(sizeof(Stack_Node) ;if (!p)returnERROR;/*申請新結(jié)點失敗，返回錯誤標(biāo)志 */p-data=e ;p-next=top-next;top-next=p ;return OK;/*/鉤鏈(3)S/*彈棧(元素出棧)us pop(Stack_Node將棧頂元素出棧 */Stack_Node *p ;*top , ElemType *e)ElemTy

13、pee ;if (top-next=NULL )return ERROR ;/*/棧空，返回錯誤標(biāo)志p=top-next ; e=p-data ;*/*取棧頂元素top-next=p-next ; free(p) ;return OK ;/*修改棧頂指針*/3.2棧的應(yīng)用由于棧具有的“后進(jìn)先出”的固有特性，因此，棧成為程序設(shè)計中常用的工具和數(shù)據(jù)結(jié)構(gòu)。以下是幾個棧應(yīng) 用的例子。3.2.1數(shù)制轉(zhuǎn)換十進(jìn)制整數(shù)N向其它進(jìn)制數(shù)d(二、八、十六)的轉(zhuǎn) 換是計算機(jī)實現(xiàn)計算的基本問題。轉(zhuǎn)換法則：該轉(zhuǎn)換法則對應(yīng)于一個簡單算法原理:n=(n div d)*d+n mod d其中：div為整除運算,mod為求余運算

14、例如 (1348)10= (2504)8，其運算過程如下：nn div 8n mod 82120052212采用靜態(tài)順序棧方式實現(xiàn)void conver(n ,d)/*將十進(jìn)制整數(shù)N轉(zhuǎn)換為d(2或8)進(jìn)制數(shù)*/SqStackS ;k, *e ;S=Init_Stack();while(n0)k=n%d ; push(S , k) ; n=n/d ;/*求出所有的余數(shù)，進(jìn)棧 */while(S.top!=0)/*棧不空時出棧，輸出 */pop(S, e) ;prf(“%1d” , *e) ;3.2.2在文字處理括號匹配問題或編譯程序設(shè)計時，常常需要檢查一個字符串或一個表達(dá)式中的括號是否相匹配?匹

15、配：從左至右掃描一個字符串(或表達(dá)式)，則每個右括號將與最近遇到的那個左括號相匹配。則可以在從左至右掃描過程中把所遇到的左括號存放到堆棧中。 每當(dāng)遇到一個右括號時，就將它與棧頂?shù)淖罄ㄌ?如果存在)相匹配，同時從棧頂刪除該左括號。算法：設(shè)置一個棧，當(dāng)讀到左括號時，左括號進(jìn)棧。當(dāng)讀到右括號時，則從棧出一個元素，與讀到的左括號進(jìn)行匹配，若匹配成功，繼續(xù)讀入；否則匹配失敗，返回FLASE。算法描述#define TRUE0#defineSqStackFLASES ;-1S=Init_Stack() ;/*堆棧初始化*/Match_Brackets( )char ch , x ; scanf(“%c”

16、, &ch) ;while (asc(ch)!=13)if(ch=()|(ch=)push(S ,ch) ;else if(ch=)x=pop(S) ;if (x!=)prf(“括號不匹配”) ;return FLASE (ch=)x=pop(S) ;else ifif (x!=() prf(“(括號不匹配”) ;return FLASE;if (S.top!=0)prf(“括號數(shù)量不匹配！”) ;return FLASE;elsereturn TRUE;3.2.2棧與遞歸調(diào)用的實現(xiàn)棧的另一個重要應(yīng)用是在程序設(shè)計語言中實現(xiàn)遞歸調(diào)用。遞歸調(diào)用：一個函數(shù)(或過程)直接或間接地調(diào)用 自己本身，簡稱遞

17、歸(Recursive)。遞歸是程序設(shè)計中的一個強(qiáng)有力的工具。因為遞歸 函數(shù)結(jié)構(gòu)清晰，程序易讀，正確性很容易得到證明。為了使遞歸調(diào)用不至于無終止地進(jìn)行下去，實際上 有效的遞歸調(diào)用函數(shù)(或過程)應(yīng)包括兩部分：遞推規(guī)則 (方法)，終止條件。例如：求n!1當(dāng)n=0時終止條件Fact(n)=n*fact(n-1)當(dāng)n0時遞推規(guī)則為保證遞歸調(diào)用正確執(zhí)行，系統(tǒng)設(shè)立一個“遞歸工作棧”，作為整個遞歸調(diào)用過程期間使用的數(shù)據(jù)區(qū)。每一層遞歸包含的信息如：參數(shù)、局部變量、上一一個“工作” 。每進(jìn)入一層遞歸，層的返回地址就產(chǎn)生一個新的工作就從棧頂彈出一個工作壓入棧頂；每退出一層遞歸，。從被調(diào)函數(shù)返回調(diào)用函數(shù)的一般步驟：

18、(1) 若棧為空，則執(zhí)行正常返回。從棧頂彈出一個工作。將“工作”中的參數(shù)值、局部變量值賦給相應(yīng)返回地址。的變量； 將函數(shù)值賦給相應(yīng)的變量。(5)轉(zhuǎn)移到返回地址。3.3隊列3.3.1隊列及其基本概念1隊列的基本概念隊列(Queue)：也是運算受限的線性表。是一種先進(jìn)先出(InOut ，簡稱FIFO)的線性表。，而在另一端進(jìn)行刪除。只允許在表的一端進(jìn)行隊首(front) ：允許進(jìn)行刪除的一端稱為隊首。隊尾(rear) ：允許進(jìn)行的一端稱為隊尾。例如：排隊購物。操作系統(tǒng)中的作業(yè)排隊。先進(jìn)入隊列的成員總是先離開隊列。隊列中沒有元素時稱為空隊列。在空隊列中依次加入元素a1, a2, , an之后，a1是

19、隊首元素，an是隊尾元素。顯然退出隊列的次序也只能是a1, a2, , an，即隊列的修改是依先進(jìn)先出的原則進(jìn)行的，如圖3-5所示。a1 , a2 , ,an出隊入隊隊首圖3-5隊尾隊列示意圖2隊列的抽象數(shù)據(jù)類型定義ADT Queue數(shù)據(jù)對象：D = ai|aiElemSet,i=1, 2, , n, n = 0 數(shù)據(jù)關(guān)系：R = | ai-1, aiD,約定a1端為隊首，an端為隊尾?；静僮鳎篊reate()：創(chuàng)建一個空隊列；i=2,3,n EmptyQue()：若隊列為空，則返回true ，否則返回flase ；InsertQue(x) ：向隊尾元素x；DeleteQue(x) ：刪除隊

20、首元素x； ADT Queue3.3.2隊列的順序表示單元(一維數(shù)組) 依次存放從隊利用一組連續(xù)的首到隊尾的各個元素，稱為順序隊列。對于隊列，和順序棧相類似，也有動態(tài)和靜態(tài)之分。本部分介紹的是靜態(tài)順序隊列，其類型定義如下：#definetypedefMAX_QUEUE_SIZEstruct queue100ElemTypeQueue_arrayMAX_QUEUE_SIZE ; front ;rear ;Sueue;3.3.2.1隊列的順序結(jié)構(gòu)設(shè)立一個隊首指針front ，一個隊尾指針rear ，分別指向隊首和隊尾元素。初始化：front=rear=0。入隊：將新元素1。rear所指的位置，然后

21、rear加出隊：刪去front所指的元素，然后加1并返回被刪元素。隊列為空：front=rear。隊滿：rear=MAX_QUEUE_SIZE-1或front=rear。在非空隊列里，隊首指針始終指向隊頭元素，而隊尾指針始終指向隊尾元素的下一位置。順序隊列中存在“假溢出”現(xiàn)象。因為在入隊和出 隊操作中，頭、尾指針只增加不減小，致使被刪除元素的空間無法重新利用。因此，盡管隊列中實際元素個數(shù)可能遠(yuǎn)遠(yuǎn)小于數(shù)組大小，但可能由于尾指針?biāo)瘸鱿蛄靠臻g的上界而不能做入隊操作。該現(xiàn)象稱為假溢出。 如圖3-6所示是數(shù)組大小為5的順序隊列中隊首、隊尾指針和隊列中元素的變化情況。Q.reara5 a4Q.rearQ

22、.rearQ.frontQ.fronta3 a2 a1Q.rearQ.front(a) 空隊列Q.front(d)入隊2個元素(b) 入隊3個元素(c)出隊3個元素圖3-6隊列示意圖3.3.2.2循環(huán)隊列為充分利用向量空間，克服上述“假溢出”現(xiàn)象的方法是：將為隊列分配的向量空間看成為一個首尾相接的圓環(huán)，并稱這種隊列為循環(huán)隊列(Circular Queue)。在循環(huán)隊列中進(jìn)行出隊、入隊操作時，隊首、隊尾指針仍要加1，朝前移動。只不過當(dāng)隊首、隊尾指針指向向量上界(MAX_QUEUE_SIZE-1)時，其加1操作的結(jié)果是指向向量的下界0。這種循環(huán)意義下的加1操作可以描述為：if(i+1=MAX_QU

23、EUE_SIZE)i=0;elsei+ ;其中： i代表隊首指針(front)或隊尾指針(rear)用模運算可簡化為：i=(i+1)%MAX_QUEUE_SIZE ;顯然，為循環(huán)隊列所分配的空間可以被充分利用，除非向量空間真的被隊列元素全部占用，否則不會上 溢。因此，真正實用的順序隊列是循環(huán)隊列。例：設(shè)有循環(huán)隊列QU0，5，其初始狀態(tài)是front=rear=0，變化情r況ear如下圖3-7所示。后隊列的頭、尾指針的狀態(tài)frontfrontdefront01010123g23gd, e出隊25b5b54344rearrear(b) d, e, b, g入隊(c)(a) 空隊列rearfrontr

24、eark054ik054ik054i(e)r11123g22jbjpj33rearfrontfront(d)i, j, k入隊(f)r, p, s, t入隊b, g出隊圖3-7 循環(huán)隊列操作及指針變化情況入隊時尾指針向前追趕頭指針，出隊時頭指針向前追趕尾指針，故隊空和隊滿時頭尾指針均相等。因此， 無法通過front=rear來判斷隊列“空”還是“滿”。解決此問題的方法是：約定入隊前，測試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認(rèn)為隊滿。即：rear所指的單元始終為空。循環(huán)隊列為空：front=rear 。循環(huán)隊列滿：(rear+1)%MAX_QUEUE_SIZE=front。循環(huán)隊列的

25、基本操作1 循環(huán)隊列的初始化Sueue Init_CirQueue(void) SueueQ ;Q.front=Q.rear=0;return(Q) ;2S入隊操作us Insert_CirQueue(SueueQ , ElemTypee)/* 將數(shù)據(jù)元素e到循環(huán)隊列Q的隊尾*/if(Q.rear+1)%MAX_QUEUE_SIZE= Q.front)returnERROR;/*隊滿，返回錯誤標(biāo)志 */ueue_arrayQ.rear=e ;/* 元素e入隊*/Q.rear=(Q.rear+1)% MAX_QUEUE_SIZE ;/*隊尾指針向前移動 */return OK;/*入隊成功*/3

26、S出隊操作us Delete_CirQueue(SueueQ, ElemType*/*x )/* 將循環(huán)隊列Q的隊首元素出隊if (Q.front+1= Q.rear)return ERROR ;/*隊空，返回錯誤標(biāo)志*/*/*x=ueue_arrayQ.front ;/* 取隊首元素Q.front=(Q.front+1)% MAX_QUEUE_SIZE ;/*隊首指針向前移動 */return OK ;3.3.3隊列的鏈?zhǔn)奖硎?隊列的鏈?zhǔn)疥犃械逆準(zhǔn)奖硎窘Y(jié)構(gòu)簡稱為鏈隊列，它是限制僅在表頭進(jìn)行刪除操作和表尾進(jìn)行操作的單鏈表。需要兩類不同的結(jié)點：數(shù)據(jù)元素結(jié)點，隊列的隊首指針和隊尾指針的結(jié)點，如圖數(shù)

27、據(jù)元素結(jié)點類型定義：typedef struct Qnode示。datafront rear指針結(jié)點ElemTypedata ;數(shù)據(jù)元素結(jié)點struct QnodeQNode ;*next ;圖3-8鏈隊列結(jié)點示意圖指針結(jié)點類型定義：typedef struct link_queueQNode*front ,*rear ;Link_Queue ;鏈隊運算及指針變化鏈隊的操作實際上是單鏈表的操作，只不過是刪2除在表頭進(jìn)行，在表尾進(jìn)行。、刪除時分別修改不同的指針。鏈隊運算及指針變化如圖3-9所示。front rear(a) 空隊列front rearx(b)x入隊front rearyx(c)y再

28、入隊front rearyx(d)x出隊圖3-9隊列操作及指針變化3鏈隊列的基本操作鏈隊列的初始化LinkQueue *Init_LinkQueue(void)LinkQueue*Q ;QNode*p ;p=(QNode *)malloc(sizeof(QNode) ; /* 開辟頭結(jié)點 */p-next=NULL ;Q=(LinkQueue*)malloc(sizeof(LinkQueue) ;/*開辟鏈隊的指針結(jié)點 */Q.front=Q.rear=p ; return(Q) ; 鏈隊列的入隊操作在已知隊列的隊尾(Q.rear)。一個元素e ，即修改隊尾指針SusInsert_CirQueue(LinkQueue*Q , ElemTypee)/* 將數(shù)據(jù)元素e到鏈隊列Q的隊尾 */p=(QNode *)malloc(sizeof(QNode) ;if (!p)returnERROR;/*申請新結(jié)點失敗，返回錯誤標(biāo)志 */p-data=e ; p-next=NULL ;/*形成新結(jié)點 */Q.rear-next=p ;return OK;Q.rear=p ;/*新結(jié)點*/到隊尾S鏈隊列的出隊操作usDelete_LinkQueue(LinkQueue*Q, ElemType *x