棧：限定僅在表尾進行插入和刪除操作的線性表。
空棧：不含任何數(shù)據(jù)元素的棧。
允許插入和刪除的一端稱為棧頂，另一端稱為棧底。

棧的操作特性：后進先出(LIFO)
注意：棧只是對表插入和刪除操作的位置進行了限制，并沒有限定插入和刪除操作進行的時間。

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

兩棧共享空間
在一個程序中需要同時使用具有相同數(shù)據(jù)類型的兩個棧，如何順序存儲這兩個棧？
直接解決：為每個棧開辟一個數(shù)組空間。
順序棧單向延伸——使用一個數(shù)組來存儲兩個棧。
兩棧共享空間：使用一個數(shù)組來存儲兩個棧，讓一個棧的棧底為該數(shù)組的始端，另一個棧的棧底為該數(shù)組的末端，兩個棧從各自的端點向中間延伸。

順序棧和鏈棧的比較
時間性能：相同，都是常數(shù)時間O(1)。
空間性能：
順序棧：有元素個數(shù)的限制和空間浪費的問題。
鏈棧：沒有棧滿的問題，只有當(dāng)內(nèi)存沒有可用空間時才會出現(xiàn)棧滿，但是每個元素都需要一個指針域，從而產(chǎn)生了結(jié)構(gòu)性開銷。
總之，當(dāng)棧的使用過程中元素個數(shù)變化較大時，用鏈棧是適宜的，反之，應(yīng)該采用順序棧。

遞歸的定義
子程序（或函數(shù)）直接調(diào)用自己或通過一系列調(diào)用語句間接調(diào)用自己，是一種描述問題和解決問題的基本方法。
遞歸的基本思想
問題分解：把一個不能或不好解決的大問題轉(zhuǎn)化為一個或幾個小問題，再把這些小問題進一步分解成更小的小問題，直至每個小問題都可以直接解決。
遞歸的要素
遞歸邊界條件：確定遞歸到何時終止，也稱為遞歸出口；
遞歸模式：大問題是如何分解為小問題的，也稱為遞歸體。

遞歸過程與遞歸工作棧
遞歸過程在實現(xiàn)時，需要自己調(diào)用自己。
層層向下遞歸，返回次序正好相反。
遞歸函數(shù)的內(nèi)部執(zhí)行過程
⑴ 運行開始時，首先為遞歸調(diào)用建立一個工作棧，其結(jié)構(gòu)包括值參、局部變量和返回地址；
⑵ 每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址壓棧；
⑶ 每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。

隊列的邏輯結(jié)構(gòu)
隊列：只允許在一端進行插入操作，而另一端進行刪除操作的線性表。
空隊列：不含任何數(shù)據(jù)元素的隊列。
允許插入（也稱入隊、進隊）的一端稱為隊尾，允許刪除（也稱出隊）的一端稱為隊頭。
隊列中元素具有相同類型及先進先出特性，相鄰元素具有前驅(qū)和后繼關(guān)系！

放寬隊列的所有元素必須存儲在數(shù)組的前n個單元這一條件 ，只要求隊列的元素存儲在數(shù)組中連續(xù)的位置。
設(shè)置隊頭、隊尾兩個指針！

假溢出：當(dāng)元素被插入到數(shù)組中下標(biāo)最大的位置上之后，隊列的空間就用盡了，盡管此時數(shù)組的低端還有空閑空間，這種現(xiàn)象叫做假溢出。
循環(huán)隊列：將存儲隊列的數(shù)組頭尾相接。
隊列的順序存儲結(jié)構(gòu)及實現(xiàn)
1.附設(shè)一個存儲隊列中元素個數(shù)的變量num，當(dāng)num=0時隊空，當(dāng)num=QueueSize時為隊滿；
2.修改隊滿條件，浪費一個元素空間，隊滿時數(shù)組中只有一個空閑單元；
3.設(shè)置標(biāo)志flag，當(dāng)front=rear且flag=0時為隊空，當(dāng)front=rear且flag=1時為隊滿。

時間性能:循環(huán)隊列和鏈隊列的基本操作都需要常數(shù)時間O (1)。
空間性能:
循環(huán)隊列：必須預(yù)先確定一個固定的長度，所以有存儲元素個數(shù)的限制和空間浪費的問題。
鏈隊列：沒有隊列滿的問題，只有當(dāng)內(nèi)存沒有可用空間時才會出現(xiàn)隊列滿，但是每個元素都需要一個指針域，從而產(chǎn)生了結(jié)構(gòu)性開銷。

總結(jié)

以上是生活随笔為你收集整理的20176408李俊 栈和队列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。