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

3.1棧

3.2隊列3.1棧3.1.1棧的定義及基本運算棧(Stack)是限定僅在表的一端進行插入或刪除操作的線性表。插入、刪除的一端稱為棧頂(Top)，另一端稱為棧底(Bottom)。不含任何元素的空表稱為空棧。對于非空棧S?=?(a1,a2,…,an)，a1是棧底元素，an是棧頂元素。如圖3.1所示，進棧的順序是a1,a2,…,an，出棧的順序正好相反。因此，棧是一種后進先出的(LastInFirstOut)的線性表。棧的常用基本運算有以下六種：(1)?InitStack(&S)棧初始化：操作結(jié)果是構(gòu)造一個空棧S。(2)?SetNull(S)置空棧：棧S已存在，將棧S清為空棧。(3)?Empty(S)判斷?？眨喝魲為空則返回“真”值；否則返回“假”值。(4)?Push(S,x)進棧：若棧S不滿，將數(shù)據(jù)元素x插入棧頂，并返回入棧是否成功的狀態(tài)信息。入棧操作會改變棧的內(nèi)容。(5)?Pop(S,&x)出棧：若棧S非空，刪除棧頂數(shù)據(jù)元素，通過參數(shù)x帶回棧頂元素，并返回出棧是否成功的狀態(tài)信息。出棧操作會使棧的內(nèi)容發(fā)生變化。(6)?GetTop(S,&x)取棧頂元素：若棧S非空，通過參數(shù)x帶回棧頂元素，并返回取棧頂元素是否成功的狀態(tài)信息。該操作完成后，棧的內(nèi)容不變。3.1.2棧的順序存儲結(jié)構(gòu)和基本運算的實現(xiàn)1．棧的順序存儲結(jié)構(gòu)——順序棧棧的順序存儲結(jié)構(gòu)簡稱順序棧(SequentialStack)。順序棧采用一維數(shù)組來存儲，并且用一個整型量Top指示當前棧頂?shù)奈恢茫覀儾环涟裈op稱為棧頂指針。順序棧的類型定義如下：其中，maxsize是數(shù)組空間的長度；datatype是棧中元素的類型。設S是指向SeqStack結(jié)構(gòu)體類型數(shù)據(jù)的指針。順序棧本質(zhì)上是順序表的簡化，我們需要確定用數(shù)組的哪一端作為棧底。通常把數(shù)組中下標為0的一端作為棧底，那么S->data[0]是棧底元素，S->data[S->Top]是棧頂元素。當S->Top?=?-1時為空棧，滿棧時S->Top=maxsize-1。對于順序棧，入棧時要先判斷棧是否已滿，棧滿簡稱為“上溢”；出棧時需判斷棧是否為空，?？蘸喎Q為“下溢”。入棧操作S->Top加1，出棧操作S->Top減1。圖3.2說明了棧中元素和棧頂指針之間的關系。2．順序棧基本運算的實現(xiàn)1)棧初始化算法3.1建立空順序棧。2)置空棧算法3.2順序棧置空。3)判斷棧空算法3.3判順序棧S是否為空棧。4)入棧算法3.4順序棧入棧。5)出棧算法3.5順序棧棧頂元素出棧。6)取棧頂元素算法3.6取順序棧的棧頂元素。3．多個順序棧共享連續(xù)空間在同時使用兩個或多個順序棧時，為了避免某個棧發(fā)生上溢，而其余棧還有很多未用空間的情況出現(xiàn)，可讓這些棧共享同一個一維數(shù)組空間，相互之間調(diào)劑余缺，既節(jié)約了存儲空間，又降低了發(fā)生上溢的概率。下面以兩個順序棧共享同一個數(shù)組空間的情況進行討論。兩個棧共享一個數(shù)組空間的結(jié)構(gòu)類型定義如下：將兩個棧的棧底分別固定在一維數(shù)組空間的兩端，棧頂向中間延伸，空閑區(qū)域在數(shù)組的中部，如圖3.3所示。只有當兩個棧占滿整個數(shù)組空間時(S->Top1+1等于S->Top2)，才會發(fā)生上溢。設i表示整型數(shù)值，它只取1或者2，分別表示對1號棧或者2號棧進行操作。這里我們只給出兩個棧共享空間的入棧和出棧操作。進棧操作的算法如下所示：當存儲棧的數(shù)組中沒有空閑單元時為棧滿。此時1號棧的棧頂與2號棧的棧頂處于相鄰的位置，即Top1+1?=?Top2(或Top1?=?Top2-1)。另外，對于2號棧的入棧，Top2應當是減1而不是加1。出棧操作的算法如下所示：當Top1=-1時，1號棧為空；當Top2=maxsize時，2號棧為空。另外，對于2號棧的出棧，Top2應當是加1而不是減1。3.1.3棧的鏈式存儲結(jié)構(gòu)和基本運算的實現(xiàn)1.棧的鏈接存儲結(jié)構(gòu)——鏈棧棧的鏈接存儲結(jié)構(gòu)簡稱鏈棧(LinkedStack)，通常用單鏈表表示。鏈棧的結(jié)點結(jié)構(gòu)類型定義如下：由于鏈棧是動態(tài)分配元素存儲空間的，因此在對棧進行操作時不存在上溢的問題。我們將單鏈表的表頭定義為棧頂。由于只能在棧頂進行入棧和出棧操作，因此只能在表頭插入和刪除，可以說鏈棧是操作受限的單鏈表。既然只能在表頭進行操作，所以也就沒有必要設置頭結(jié)點了。如圖3.5所示，S是LinkStack類型的指針，指向鏈棧，可以看作是棧的接口。Top是棧頂指針，指向棧頂結(jié)點。當Top等于NULL時為空棧。2．鏈棧基本運算的實現(xiàn)鏈?；具\算的實現(xiàn)實質(zhì)上是單鏈表基本運算的簡化。由于對棧的操作都是在棧頂(單鏈表的表頭)進行的，因此算法的時間復雜度均為O(1)。1)棧初始化算法3.7建立空鏈棧。2)置空棧算法3.8鏈棧置空。3)入棧算法3.9鏈棧入棧。4)出棧算法3.10鏈棧棧頂元素出棧。5)取棧頂元素算法3.11取鏈棧的棧頂元素。3.1.4順序棧和鏈棧的比較從時間特性方面來看，實現(xiàn)順序棧和鏈棧的所有基本運算的算法，其時間復雜度都是O(1)，因此唯一可以比較的是空間特性。棧初始化時，順序棧必須確定一個固定的長度作為棧的容量，所以有存儲元素個數(shù)的限制和空間浪費的問題。鏈棧沒有棧滿的問題，只有當內(nèi)存沒有可用空間時才會出現(xiàn)不能入棧的情況，但是每個元素都需要一個指針域，從而又產(chǎn)生了結(jié)構(gòu)性的開銷。所以當棧的使用過程中元素個數(shù)變化較大時，用鏈棧是適宜的；反之，應該采用順序棧。3.2隊列3.2.1隊列的定義及基本運算隊列(Queue)也是一種運算受限的線性表。它只允許在表的一端進行插入，該端稱為隊尾(Rear)；在表的另一端進行刪除，該端稱為隊頭(Front)。當隊列中沒有元素時稱為空隊列。隊列亦稱作先進先出(FirstInFirstOut)的線性表，簡稱為FIFO表。設隊列中的元素為a1,a2,…,an，a1是隊頭元素，an是隊尾元素。隊列中的元素都是按照a1,a2,…,an的順序依次入隊和出隊的。圖3.6是隊列的示意圖。隊列的主要基本運算如下：(1)?InitQueue(&Q)隊列初始化：構(gòu)造一個空隊列Q。(2)?SetNull(Q)置空隊：將隊列Q清空。(3)?Length(Q)求隊列長度：返回隊列中元素的個數(shù)。(4)?Empty(Q)判空隊：若隊列Q為空隊列，返回“真”值；否則返回“假”值。(5)?EnQueue(Q,x)入隊：若隊列Q非滿，將元素x插入Q的隊尾。(6)?DeQueue(Q)出隊：若隊列Q非空，刪除隊頭元素，返回Q的隊頭元素。(7)?GetFront(Q)取隊頭元素：若隊列Q非空，返回Q的隊頭元素；Q中元素保持不變。3.2.2隊列的順序存儲結(jié)構(gòu)和基本運算的實現(xiàn)1．隊列的順序存儲結(jié)構(gòu)——順序隊列隊列的順序存儲結(jié)構(gòu)稱為順序隊列，采用數(shù)組存儲隊列中的元素。本書約定，在非空隊列中隊頭指針front指向隊頭元素的前一個位置，隊尾指針rear指向隊尾元素的位置。如果是空隊，隊頭、隊尾指針相等。隊尾指針減去隊頭指針就是隊列的長度。當然也可以約定隊頭指針front指向隊頭元素的位置，隊尾指針rear指向隊尾元素的后一個位置。順序隊列的結(jié)構(gòu)類型定義如下：順序隊列中出隊、入隊操作的情況如圖3.7所示。順序隊列中可能出現(xiàn)“上溢”和“下溢”現(xiàn)象，并且還存在“假上溢”現(xiàn)象。也就是說，盡管隊列的數(shù)組空間雖然未被占滿，但尾指針已達到數(shù)組的上界而不能進行入隊操作。例如在圖3.7(c)或(d)的情況下，再進行入隊操作，則會出現(xiàn)“假上溢”。采用循環(huán)隊列(CircularQueue)的方法可以較好地解決“假上溢”問題，即將數(shù)組看作一個首尾相接的圓環(huán)，如圖3.8所示。在循環(huán)隊中通過取模運算修改隊尾指針和隊頭指針，具體描述為：在循環(huán)隊列中，入隊時尾指針向前追趕頭指針，出隊時頭指針向前追趕尾指針。由圖3.9可以看出，在隊空和隊滿時都有sq->front等于sq->rear，無法區(qū)分空隊和滿隊。通常采用少用一個元素空間的方法來解決這個問題，如圖3.10所示。判斷空隊和滿隊的條件分別是：2．循環(huán)隊列基本運算的實現(xiàn)我們用前面所述方法來實現(xiàn)循環(huán)隊列上的基本運算。1)隊列初始化算法3.12生成空循環(huán)隊列。對于循環(huán)隊列來說，只要隊頭和隊尾指針相等即為空隊，所以這里置為0～maxsize-1之間的任何一個值都可以，但一般置為0。2)置空隊算法3.13循環(huán)隊列置空。3)求隊列長度算法3.14求循環(huán)隊列長度。4)入隊算法3.15循環(huán)隊列入隊。5)出隊算法3.16循環(huán)隊列出隊。6)取隊頭元素算法3.17取循環(huán)隊列的隊頭元素。3.2.3隊列的鏈式存儲結(jié)構(gòu)和基本運算的實現(xiàn)1．隊列的鏈式存儲結(jié)構(gòu)——鏈隊列隊列的鏈式存儲結(jié)構(gòu)簡稱鏈隊列，它是僅限在表頭刪除和表尾插入的單鏈表。為了便于在表尾做插入操作，需要增加一個尾指針，指向單鏈表中的最后一個結(jié)點。我們將鏈隊列的頭指針和尾指針封裝在一起作為一個結(jié)構(gòu)體。下面是其類型定義：為了運算方便，鏈隊列中通常也帶有頭結(jié)點。圖3.11給出了鏈隊列的示意圖，圖中q為L