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

1、第第3 3章章 棧和隊列棧和隊列 棧和隊列是兩種特殊的線性表，是操作受限的線性表，稱為限定性數(shù)據(jù)結(jié)構(gòu)。3.1 棧（stack）3.1.13.1.1棧的定義和特點棧的定義和特點定義：棧(Stack)是限制在表的一端進(jìn)行插入和刪除運算的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom)。當(dāng)表中沒有元素時稱為空棧。假設(shè)棧S=(a1，a2，a3，,an)，則a1稱為棧底元素，an為棧頂元素。棧中元素按 a1，a2，a3，an的次序進(jìn)棧，退棧的第一個元素應(yīng)為棧頂元素。換句話說，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧稱為后進(jìn)先出表（LIFO）。特點：先進(jìn)后出（FILO）或后

2、進(jìn)先出（LIFO）。ana1a2.棧底棧頂.出棧進(jìn)棧棧s=(a1,a2,an)棧的示意圖3.1.2棧的運算（棧的基本運算）棧的運算（棧的基本運算）1.初始化棧：初始化棧：InitStack (&S)初始空棧S。將棧S置為一個空棧(不含任何元素)。2.銷毀：銷毀：destroyStack (&S)將棧S銷毀，釋放棧的存儲空間。3.判棧空：判棧空： StackIsEmpty(S) 判斷棧S是否為空，若為空則返回真（TRUE）否則返回假（FALSE）.4.清空：清空： clearStack(&S)將棧清空，變?yōu)榭諚！?.入棧：入棧： Push(&S,e)棧S已存在，e為給定數(shù)據(jù)元素值。將給定值為e的

3、元素入棧，即將e在棧S的棧頂端插入。6.出棧：出棧： Pop(&S,&e)將棧S的棧頂元素出棧，即將棧頂元素刪除，并通過參數(shù)e返回出棧的元素的值。7.取棧：取棧： getTop(S,&e)取棧S的棧頂元素的值，將棧頂?shù)脑氐闹低ㄟ^參數(shù)e返回。8.求棧長：求棧長： stackLength(S)求棧S的長度，即棧中的元素的個數(shù)。當(dāng)棧S非空時，函數(shù)返回該棧的長度；而當(dāng)棧S為空時則返回0。9.遍歷：遍歷： stackTraverse(S,visit()Visit()為元素的訪問函數(shù)。依照從棧底到棧頂?shù)捻樞蛞来卧L問棧S的元素，且每個元素只被訪問一次。3.1.3 3.1.3 順序棧順序棧實現(xiàn)：一維數(shù)組sM

4、top=-1123450?？諚ｍ斨羔榯op,指向?qū)嶋H棧頂后的空位置，初值為-1top123450進(jìn)棧Atop出棧棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=-1,棧空，此時出棧，則下溢（underflow)top=Maxsize-1,棧滿，此時入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？枕樞驐５拇鎯Y(jié)構(gòu)描述 #define StackSpaceIncer 20 /存儲空間的增量 typedef struct SElemType * base; / SElemType為棧元素類型,base為順序棧存儲空間的動態(tài) 數(shù)組 in

5、t top; /指示下一個入棧的下標(biāo)位置 int stackSize; /棧當(dāng)前的存儲空間大小 SqStack ; / SqStack為順序棧類型順序棧的基本操作（1）初始化 InitSqStack (&S,InitSize) 創(chuàng)建一個初始空間大小為InitSize的空順序棧S。（2）判空操作 stackIsEmpty(S) 清空操作 clearStack(&S) 求棧長 stackLength (S)（3）入棧 Push(&S,e) 在順序棧S的棧頂插入一個值為e的元素。（4）出棧 Pop(&S,&e) 若順序棧S為空，則出棧操作出錯。否則，將棧頂元素刪除只需將棧頂指針top向下移動一個位置

6、（top-1）即可，同時還需將出棧元素的值由參數(shù)e 返回。（5）取棧頂 getTop(S,&e) 若順序棧S為空，則出棧操作出錯。否則，下標(biāo)為top-1的元素即為棧頂元素，將其值由參數(shù)e返回。3.1.4 3.1.4 鏈?zhǔn)綏ｆ準(zhǔn)綏５逆準(zhǔn)酱鎯Y(jié)構(gòu)成為鏈?zhǔn)綏?。棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)成為鏈?zhǔn)綏?。鏈棧的存儲結(jié)構(gòu)描述 typedef struct stackNode SElemType data; struct stackNode *next; *LinkStack; /鏈?zhǔn)綏ｎ愋?，即鏈表的頭指針類型實現(xiàn)實現(xiàn) .topdatalink棧底 .棧底toptopxptop .棧底topp入棧過程：出棧過程：棧頂3

7、.1.4 鏈?zhǔn)綏Ｉ系幕静僮麈準(zhǔn)綏Ｉ系幕静僮?由棧的基本操作可見，棧的操作僅僅是線性表的相應(yīng)操作的特例。因此，當(dāng)利用單鏈表來表示鏈?zhǔn)綏r，鏈?zhǔn)綏；静僮鞯膶崿F(xiàn)算法就可以用單鏈表的相關(guān)基本操作算法來表示。（1）初始化 InitLinkStack(&S) 即創(chuàng)建一個空的不帶頭結(jié)點的單鏈表S，也就是將頭指針S賦值為空。算法見 3-8。（2）入棧操作 Push(&S,e) 將元素e入棧即在單鏈表S的首端插入值為e的結(jié)點。鏈?zhǔn)綏５娜霔２僮魉惴ㄒ?3-9.（3）出棧操作 Pop(&S,&e) 棧非空時，將單鏈表的表首結(jié)點刪除，算法見3-10（4）取棧頂操作 getTop(S,&e) 棧非空時，由參數(shù)e返

8、回棧頂指針S所指棧頂結(jié)點的值。算法見 3-113.1.5 棧的應(yīng)用1、簡單的行編輯程序 一個簡單的行編輯程序功能是：接受用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。由于用戶在終端上進(jìn)行輸入時，不能保證不出差錯 ,如原為輸入：while(*s)卻輸成：whliilre(s)。 在編輯程序中，設(shè)立一個輸入緩沖區(qū)，用于接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入錯誤，并在發(fā)現(xiàn)有誤時可以及時更正。比如：whli#ilr#e(s#*s) outchaputchar(*s=#+)實際上為： while(*s) putchar(*s+) 算法如下: void lineedit( ) /利

9、用字符棧S，從終端接收一行并傳送至調(diào)用過程的數(shù)據(jù)區(qū) initstack(s); /構(gòu)造空棧S ch=gether( ); /從終端接收一個字符 while(ch!=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( ); /從終端接收下一個字符 /將從棧底到棧頂?shù)臈?nèi)字符傳送至調(diào)用過程的數(shù)據(jù)區(qū) cl

10、earstack(s); /重置s為空棧 if(ch!=eof) ch=gethar( ); destroystack(s); /結(jié)束字符輸入后銷毀棧 3.2 棧與遞歸棧與遞歸 遞歸是在數(shù)學(xué)和計算機科學(xué)中處理問題的一種重要方法。在軟件設(shè)計中當(dāng)采用遞歸方法解決問題時，可以使問題的描述和編寫的程序變得簡潔和清晰。3.2.1 遞歸的概念和算法 遞歸：一個概念、函數(shù)等對象用自己來定義自己。遞歸：一個概念、函數(shù)等對象用自己來定義自己。 在程序設(shè)計語言中，一個算法直接或者間接調(diào)用了自己，在程序設(shè)計語言中，一個算法直接或者間接調(diào)用了自己，則稱該算法為遞歸算法。這過程稱為遞歸調(diào)用的過程。則稱該算法為遞歸算法。

11、這過程稱為遞歸調(diào)用的過程。例如，下列為某人祖先的遞歸定義：某人的雙親是他的祖先（基本情況）。某人祖先的雙親同樣是某人的祖先（遞歸步驟）。斐波納契數(shù)列（Fibonacci Sequence），又稱黃金分割數(shù)列，指的是這樣一個數(shù)列：1、1、2、3、5、8、13、21. 斐波納契數(shù)列是典型的遞歸案例：遞歸關(guān)系就是實體自己和自己建立關(guān)系。遞歸的算法遞歸的算法 了解了遞歸的定義，在程序語言中便可給出其遞歸的算法。例如，利用C語言定義階乘的遞歸函數(shù)：算法 3-16 long fac(int n) /求n的階乘；設(shè)n值大于等于0long f;If (n=0) f=1;Else f=n*fac(n-1) ;

12、/遞歸調(diào)用自身return f;一個遞歸定義必須滿足兩個最基本的遞歸法則：（1）基準(zhǔn)情形法則：遞歸定義中的基準(zhǔn)情形即遞歸出口，它本身不再使用遞歸定義，是遞歸的結(jié)束條件。（2）不斷推進(jìn)法則：是指在遞歸求解過程中，每一次遞歸調(diào)用都必須使求解狀況朝接近基準(zhǔn)情形的方向推進(jìn)。算法舉例算法舉例在數(shù)學(xué)中對于階乘的遞歸定義：n!，是階乘符號在此定義中，當(dāng)n0時就說利用n-1的階乘來定義n的階乘，所以此定義為遞歸定義。3.2.2 3.2.2 遞歸算法的運行機制遞歸算法的運行機制 在高級程序設(shè)計語言中，函數(shù)的執(zhí)行所遵循的原則為：當(dāng)函數(shù)調(diào)用時，則將實參傳遞給函數(shù)的形參，然后轉(zhuǎn)到函數(shù)的入口執(zhí)行函數(shù)體。而當(dāng)被調(diào)用函數(shù)執(zhí)

13、行結(jié)束時，則返回到改函數(shù)的被調(diào)用位置繼續(xù)執(zhí)行下一程序指令，當(dāng)有函數(shù)的多層嵌套調(diào)用時，在返回時也將逐層返回，其特點為“最后調(diào)用的，最先執(zhí)行完，最先往回返”。每次調(diào)用函數(shù)時所需保存的一個相關(guān)信息稱為一個“工作記錄”，其主要包括：1、返回地址：即函數(shù)運行結(jié)束后需轉(zhuǎn)去執(zhí)行的程序指令（是上一層中“函數(shù)被調(diào)用位置”的下一條程序指令）的地址2、函數(shù)的形參，函數(shù)局部變量：即在調(diào)用時為函數(shù)形參與局部變量分配的動態(tài)存儲空間。在程序執(zhí)行時，每當(dāng)發(fā)生一次函數(shù)調(diào)用，就向工作棧中壓入一個新的工作記錄；每當(dāng)有一次函數(shù)結(jié)束發(fā)生時，就從工作棧中彈出一個工作記錄。所以當(dāng)前正在執(zhí)行的函數(shù)的工作記錄一定在工作棧的棧頂，稱此工作記錄為

14、“活動記錄”3.3 3.3 隊列隊列(Queue)(Queue)3.3.1 3.3.1 隊列的定義及特性隊列的定義及特性定義：隊列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表隊尾(rear)允許插入的一端隊頭(front)允許刪除的一端a1 a2 a3.an 入隊出隊frontrear隊列Q=(a1,a2,an)v特性：隊列是一種運算受限制的線性表，元素的添加在表的一端進(jìn)行，而元素的刪除在表的另一端進(jìn)行。允許添加元素的一端稱為隊尾（Rear）；允許刪除元素的一端稱為隊頭（Front）。向隊列添加元素稱為入隊，從隊列中刪除元素稱為出隊。 新入隊的元素只能添加在隊尾，出隊的元素只能是

15、刪除隊頭的元素，隊列的特點是先進(jìn)入隊列的元素先出隊，所以隊列也稱作先進(jìn)先出表或FIFO（First-In-First-Out）表。 3.3.2 3.3.2 隊列的基本運算隊列的基本運算 隊列可定義如下五種基本運算：1初始化隊列初始化隊列 InitQueue(&Q) 構(gòu)造一個隊列，并將隊列Q設(shè)置成一個空隊列。2銷毀隊列銷毀隊列 destroyQueue (&Q) 將隊列Q銷毀，釋放其存儲空間。3. 判隊空判隊空 queueIsEmpty(Q) 判斷隊列Q是否為空，若為空返回真，否則返回假。4. 清空操作清空操作 clearQueue (&Q) 將隊列將隊列Q清空，變?yōu)榭贞犃星蹇眨優(yōu)榭贞犃?.

16、入隊列入隊列 insertQueue(&Q,e) 將元素e插入到隊尾中，也稱“進(jìn)隊” ，“插入”。 6出隊列出隊列 deleteQueue(&Q,&e) 將隊列Q的隊頭元素刪除，也稱“退隊”、“刪除”。并通過e返回其值。7取隊頭元素取隊頭元素 GetFront(Q,&e) 得到隊列Q的隊頭元素的值，并將該值由參數(shù)e返回。8求隊長操作求隊長操作 queueLength(Q) 求隊列Q的長度，即隊列中元素的個數(shù)。隊列為空時返回0。9遍歷操作遍歷操作 queueTraverse(Q,visit() 依照從隊頭到隊尾的順序依次訪問隊列依照從隊頭到隊尾的順序依次訪問隊列Q中的所有元素，且中的所有元素，且

17、每個元素只被訪問一次。每個元素只被訪問一次。3.3.3 3.3.3 循環(huán)隊列循環(huán)隊列 循環(huán)隊列是隊列的順序存儲結(jié)構(gòu)中最常用的一種形式。1、循環(huán)隊列的存儲結(jié)構(gòu)與類型定義為充分利用向量空間，克服假溢出現(xiàn)象的方法是：將向量空間想象為一個首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量。存儲在其中的隊列稱為循環(huán)隊列（Circular Queue）。這種循環(huán)隊列可以以單鏈表的方式來在實際編程應(yīng)用中來實現(xiàn)。循環(huán)隊列類型循環(huán)隊列類型CirQueuev循環(huán)隊列v基本思想：基本思想：把隊列設(shè)想成環(huán)形，讓sq0接在sqM-1之后，若rear+1=M,則令rear=0.實現(xiàn)：利用“?！边\算;入隊： sqrear=x ;rea

18、r=(rear+1) %M;v 出隊：x=sqfront;front=(front+1)%M; 012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始狀態(tài)J4,J5,J6出隊J7,J8,J9入隊隊空：front=rear隊滿：front=rear3.3.3 3.3.3 循環(huán)隊列循環(huán)隊列 2、循環(huán)隊列上基本操作的實現(xiàn)（1）初始化操作）初始化操作 InitCirQueue(&Q,QSize)創(chuàng)建一個空間大小為Qsize的空隊列Q（2）判空操作判空操作 queueIsEmpty(Q)判斷隊列是否為空，只需判斷其隊頭指針Q .

19、front與隊尾指針Q.rear是否相等清空操作清空操作 clearQueue(&Q)（3）入隊操作）入隊操作 insertQueue(&Q,e)入隊操作時，若隊列Q已滿，就不再進(jìn)行插入，操作失敗。（4）出隊）出隊 操作操作 deleteQueue(&Q,&e)（5）取隊頭操作）取隊頭操作 getFront(Q,&e)當(dāng)隊列Q非空時，front指針?biāo)赶虻募礊殛狀^元素。（6）求隊長操作）求隊長操作 queueLength(Q)隊列的長度即為隊列中元素的個數(shù)。 3.3.4 3.3.4 鏈?zhǔn)疥犃墟準(zhǔn)疥犃?、鏈?zhǔn)疥犃械拇鎯Y(jié)構(gòu)與類型定義與線性表類似，隊列也有兩種存儲表示；隊列的鏈?zhǔn)酱鎯?鏈隊列鏈隊列

20、需要隊頭和隊尾兩個指針來確定；給鏈隊列添加個頭結(jié)點，并令頭指針指向頭結(jié)點。頭結(jié)點 .front隊頭隊尾rear設(shè)隊首、隊尾指針front和rear,front指向頭結(jié)點，rear指向隊尾2、 鏈?zhǔn)疥犃猩匣静僮鲗崿F(xiàn)：（1 1）初始化操作）初始化操作 InitLinkQueue(&Q)InitLinkQueue(&Q)對鏈?zhǔn)疥犃蠶進(jìn)行初始化，即創(chuàng)建只含有一個頭結(jié)點的空隊列。（2 2）隊列的判空操作）隊列的判空操作 queueIsEmpty(Q)queueIsEmpty(Q)判斷鏈?zhǔn)疥犃蠶是否為空，可以有兩種方法：一是盤對隊頭指針front與隊尾指針rear是否相等；二是盤對隊列鏈表中是否只有一個頭結(jié)點，即Q.front-是否為空，一般采用方法一，即空隊列的判斷條件為：Q.front=Q.raer（3 3）入隊操作）入隊操作 insertQueue(&Q,e)insertQueue(&Q,e)對于鏈?zhǔn)疥犃蠶，入隊時只需在rear所指向的隊尾結(jié)點后面插入新結(jié)點，同時rear再指向新的隊尾結(jié)