棧和隊列比較簡單，而且實用性非常廣泛，這里主要介紹一下他們的概念和實現，在很多算法中，棧和隊列的運用很重要，因此，雖然簡單確是最重要的數據結構之一，必須重視。

棧是保證元素后進先出(后存入者先使用，Last In First Out,LIFO)的關系結構。

隊列是保證元素先進先出(先存入者先使用，First In First Out,FIFO)的關系結構。

棧

棧的順序表實現

class

順序表操作的后端插入和刪除操作都是o(1)操作。

棧的鏈接表實現：

順序表的操作時間復雜度為o(1)，那么為什么還要考慮鏈接表？因為順序表擴大存儲區需要做一次高代價的操作，另外順序表需要完整的大塊存儲區。采用鏈接表實現可以緩解這兩個缺陷，但是鏈接表也有自身的缺點：更多依賴于解釋器的存儲管理，每個結點的鏈接開銷以及鏈接結點在實際計算機內存中的任意散布可能帶來操作開銷。

采用鏈接表技術，自然是表頭一端作為棧頂，表尾作為棧底。

class

棧和遞歸

這里要介紹一下棧和遞歸的關系，我們平時用的遞歸算法，其內部原理就是運用了棧。

遞歸：在一個函數定義中引用了被定義的對象(被定義的函數本身)。

在遞歸的結構中，遞歸的部分必須比原來的整體簡單，這樣才有可能達到某種終點(遞歸定義的出口)，顯然，終點不能是遞歸的。遞歸結構中必須包含非遞歸的基本結構構成的部分，否則就會出現無限遞歸。

例如階乘函數n!，其遞歸的代碼實現：

def

現在來解析這一遞歸結構，表述其于棧之間的關系：

• 為了得到factor(n)的結果，必須先計算出factor(n-1)。
• 遞歸調用計算出factor(n-1)時還需要乘n，以得到factor(n)的結果，說明在遞歸調用factor(n-1)時，參數n的值需要被記錄，同樣計算factor(n-1)調用factor(n-2)時，也需要記錄這個調用之前參數n-1的記錄，向下繼續...
• 顯然需要記錄的數據的量與遞歸的層數成正比，一般而言沒有數量上的上限，不能用幾個整形變量來保存。
• 在這一系列調用中保存的數據，如n,n-1..較后保存的將先被使用，因為函數返回的順序與調用順序相反，后進入的層次先返回。

這種后進先出的使用方式和數據項數的無明確限制，就說明需要用一個棧來支持遞歸函數的實際運行，這個棧稱為程序運行棧。

下圖表示的是階乘函數factor(3)的是如何遞歸計算的。

第一個圖表示函數調用factor(3)開始執行的狀態，參數3壓入棧。隨后執行調用factor(2)，參數2壓入棧，直到factor(0)壓入棧。然后開始逐一返回，其中factor(0)直接返回1(遞歸出口)，factor(1)同樣返回1*factor(0)，計算得到factor值為1，factor(2)返回2factor(1)=2，factor(3)返回3*factor(2)=6。

遞歸的實現依賴于運行棧，對遞歸函數的每次調用都在棧上開辟一塊區域，稱為函數幀，函數的執行總以棧頂的幀作為當前幀。所有局部變量都在這里體現。當函數從下一層遞歸調用中返回時，函數的上一層執行取得下層函數調用得到的結果，執行系統彈出已經結束的調用對應的幀，然后回到調用前的那一層執行時的狀態。

函數的嵌套調用秉持著“先調用后返回”的規則，函數調用時的內部動作分為兩個部分：在進入新的函數調用前需要保存一些信息，退出一次函數調用時需要恢復調用前的狀態。這被稱為函數調用的前序動作和后序動作。

函數調用的前序動作包括：

• 為被調用函數的局部變量和形式參數分配存儲區(稱為函數幀/活動記錄/數據區)
• 將所有實參和函數的返回地址存入函數幀(實參和形參的結合/傳值)
• 將控制轉到被調用函數入口

函數調用的后序動作包括：

• 將被調用函數的計算結果存入指定位置
• 釋放被調用函數的存儲區
• 按以前保存的返回地址將控制轉回調用函數

函數的調用是有代價的，在得到程序代碼的模塊化和語義清晰性等優勢的同時，可能會付出執行時間的代價。

遞歸與非遞歸：

將一個遞歸定義的函數變成非遞歸的形式，可以自己建立一個棧來模擬程序運行棧：

def

任何一個遞歸定義的函數都可以通過引入一個棧保存中間結果的方式，翻譯為一個非遞歸的過程。與此對應的是，任何一個包含循環的程序都可以翻譯為一個不包括循環的遞歸函數。

棧的應用：簡單背包問題(動態規劃思想)

其求解算法用遞歸的方式描述很簡單，但是通過自己管理一個棧來存儲中間信息定義非遞歸算法，則比較復雜。

問題描述：一個背包里可放入重量為weight的物品，現有n件物品的集合S，其中物品的重量分別為w0,w1...wn-1。問題是能否從中選出若干件物品，其重量之和正好等于weight。如果存在就說這一背包有解，否則無解。

問題的求解：假設weight>=0，n>=0。用記法knap(weight,n)表示n件物品相對于總重量weight的背包問題，在考慮它是否有解時，通過考慮一件物品的選或者不選，可以把問題分為兩種情況

• 如果不選最后一件物品(wn-1)，那么knap(weight,n-1)的解也就是knap(weight,n)的解，如果找到前者的解也就找到了后者的解。
• 如果選擇最后一件物品，那么knap(weight-wn-1,n-1)有解，其解加上最后一件物品就是knap(weight,n)的解，即前者有解后者也有解。

定義遞歸出口：

• 重量weight已經等于0，說明問題有解
• 重量weight已經小于0，由于不斷歸結中所需的重量遞減，有可能出現這種情況，這說明按照已做的安排不能得到一個解。
• 重量大于0但已經沒有物品可用，說明按照這種安排無解。

def

函數三個參數分別是總重量weight，各物體重量表wlist和物品數量n，前兩個if處理三種簡單情況，返回True或False(遞歸出口)，后兩種情況通過遞歸調用得到結果。

隊列

隊列的鏈接表實現：

帶有首指針的單鏈表其插入操作enqueue()為o(1)操作，但是在另一端的去除操作dequeue()確實o(n)操作。那么為了實現首尾兩端的插入和刪除操作都為o(1)操作，則需要首尾指針都有的單鏈表。

class

隊列的list實現：

基于順序表實現隊列的困難：出隊操作如果在首端操作，取出當時的元素后，需要將后面的元素全部前移需要o(n)時間。如果是從尾端彈出元素，時間是o(1)操作，但是尾端插入時間為o(n)，因此無論何種方式進行插入和刪除，都避免不了o(n)的操作。另一種可能是隊首的元素彈出后，后面的元素不前移，但記住新表頭元素的位置，這樣做會帶來另一個問題，隊首的空位會越變越多，造成空間的浪費。

有一種想法：如果入隊時隊尾已經達到存儲區的末尾，應該考慮轉到存儲區開始的位置去入隊新元素。

循環順序表：

• 在隊列使用中，順序表的開始位置并不改變，上圖是一個包含8個位置的表，例如變量q.elems始終指向表元素區開始。
• 隊頭變量q.head記錄當前隊列里第一個元素的位置(圖中位置4)，隊尾變量q.rear記錄當前隊列里最后元素之后的第一個空位(圖中位置1)。
• 隊列元素保存在順序表的一段連續單元，用python的寫法是[q.head:q.rear]，左閉右開區間里。圖中有5個元素，從位置4到位置0的一段。兩個變量的值之差(取模存儲區長度)就是隊列里的元素個數。

初始時隊列為空，q.head和q.rear取相同值，表示順序表里的為空，出隊和入隊操作時需要更新q.head和q.rear

q

如下圖所示，如果隊列再存一個元素，q.rear和q.head就會相同，這與判斷隊列為空時一樣，產生沖突。事實上這種狀態就看成了隊列滿，即定義其條件為(q.rear+1)%q.len=q.head。當隊列滿時又需要繼續插入元素的話，就需要更換存儲區更大的空間。

循環隊列無法直接利用python的list里的自動存儲擴充機制：隊列元素的存儲方式與list元素的默認存儲方式不一致，list元素總是在存儲區的最前面一段，而隊列的元素可能是表里的任意一段，有時還分為頭尾兩段，如果list自動擴充，其中的隊列元素就有可能失控，另一方面list沒提供檢查存儲區容量的機制，隊列操作中無法判斷系統何時擴容。

考慮其基本設計：

• 定義隊列名SQueue對象里有一個list類型的成分_elems存放隊列元素。
• 分別考慮兩個屬性head和_num表示隊首元素所在位置以及表中元素的個數。
• 用python的list作為隊列存儲區。需要檢查當前的表是否已滿，必要時換一個存儲表，因此要記錄當前表的長度，下面用屬性_len。

數據不變式：實現一種數據結構時，最基本的問題是這些操作需要維護對象屬性之間的正確關系。

• 所有構造對象的操作，都必須把對象成分設置為滿足數據不變式的狀態，也就是說對象的初始狀態要滿足數據不變式。
• 每個對象操作都應該保證不破壞數據不變式，也就是說如果對一個狀態完好的對象應用一個操作，該操作完成時，還必須保證對象處于完好的狀態。

下面隊列實現中，考慮數據不變式：

• elems屬性引用著隊列的元素存儲區，它是一個list對象，_len屬性記錄存儲區的有效容量。
• _head是隊列的首元素的下標，_num始終記錄著隊列中元素的個數。
• 當時隊列里的元素總保存在elems里從head開始的連續位置中，新入隊的元素存入由_head+_num算出的位置，但如果需要把元素存入下標_len的位置時，改為在下標0位置存入該元素。
• 在_num==_len的情況下出現入隊操作，就擴大存儲區。

class

雙端隊列：

允許兩端插入和刪除元素，因此功能覆蓋以上所有結構，作為效率要求很高的結構，這里要求兩端插入和刪除操作時間復雜度均為o(1)。雙鏈表結構可以實現兩端的常量時間插入和刪除操作，可以實現雙端隊列。python中的collections庫中定義了一種deque類型雙端隊列，支持元素兩端的插入和刪除。deque采用一種雙鏈表技術實現，每個鏈接結點里順序存儲一組元素。

順序表與鏈表的計算機內存分配問題：

對于現在計算機內存機制，如果連續進行的一批內存訪問是局部的，操作速度就會塊得多。人們在考慮效率的同時，一個重要線索就是盡可能使計算機內存的使用局部化。python中順序表是局部化的代表，在可能的情況下應該盡量使用。鏈接結構的一個特點是，其中的結點可能在內存中任意分配。即使程序順著鏈接逐個訪問結點，在內存層面的表現通常也是在許多位置隨機的單元之間跳來跳去。因此鏈接表再帶來靈活性的同時，效率上可能有明顯的付出。這些情況就是需要考慮順序表實現的最重要原因。另外在其它的一些語言中，建立順序表結構還可以避免復雜的存儲管理。

---

參考書籍：《數據結構與算法—python語言描述》—裘宗燕

總結

以上是生活随笔為你收集整理的2.2基本算法之递归和自调用函数_数据结构与算法之5——队列和栈的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。