周立功教授數年之心血之作《程序設計與數據結構》以及《面向AMetal框架與接口的編程（上）》，書本內容公開后，在電子行業掀起一片學習熱潮。經周立功教授授權，本公眾號特對《程序設計與數據結構》一書內容進行連載，愿共勉之。

第二章為程序設計技術，本文為2.3 棧與函數返回。

當函數執行完畢后，如何返回調用處呢？由于該函數可能會被多次調用，且每次調用的地方很可能不一樣，這樣被調用函數也就不可能知道自己該返回到哪里，因此在調用函數時必須告訴被調用函數應返回到哪里？

>>> 2.3.1 堆棧

為了保存變量（數據），通常計算機會提供非常多的內存。為了便于管理內存，將所有變量使用的內存稱為棧，而將未分配的內存區域稱為堆。這些未分配的內存區域，程序員可以塊為單位請求它。這部分內存是由操作系統管理的，一旦一塊內存被分配出去，它只能由分配了這塊內存的原始代碼使用，并使用指針訪問這塊內存。由于內存是稀缺資源，當程序不再需要該內存時，都應該釋放回去。如果不這樣做，程序將會耗光內存，導致運行速度下降甚至崩潰。這就是因為程序員沒有釋放本應釋放的內存，造成了所謂的內存泄漏。

堆和棧是兩種常用的數據結構，主要用于數據的動態存儲。當程序執行時，棧中存儲的是程序的執行過程，比如，main()函數的局部變量argc和argv都在棧中，而使用malloc()函數動態分配的內存是存儲在堆中的，堆棧共享同一塊內存區域。通常程序棧占據這塊區域的下部，而堆用的是上部。當調用函數時，函數的棧幀被推到棧上，棧向上“長出”一個棧幀。當函數終止時，其棧幀從程序棧彈出。雖然棧所使用的內存不會被清理，但最終可能會被推到程序棧上的另一個棧幀覆蓋。動態分配的內存來自堆，堆向下生長。隨著內存的分配和釋放，堆中會布滿碎片。盡管堆是向下生長的，但這只是大體方向，實際上內存可能在堆上的任意位置分配。

平常大家所說的“堆棧”主要是指棧，計算機在硬件上直接支持棧。在計算機科學中，棧是一個抽象的概念。它的抽象行為特征是棧可以存儲相同類型的數據，通常又將棧中的數據稱為元素。只允許向棧中壓入一個元素（即入棧push），或從棧中刪除一個元素（即出棧pop），且元素按照“后進先出”原則處理（last in，first out，LIFO），禁止測試或修改不在棧頂的元素。

圖2.7 四種棧示意圖

如圖2.7所示為通用計算機4種形式的棧，分別稱之為滿遞減堆棧、空遞減堆棧、滿遞增堆棧和空遞增堆棧，這些都是棧的物理結構。其中的“遞減”是指數據入棧時堆棧指針的值減少，即堆棧從高地址向下增長，就像鐘乳石一樣。“遞增”是指數據入棧時堆棧指針的值增加，即堆棧從低地址向上增長，就像石筍一樣。而“滿”是指SP指向的存儲單元保存最后入棧的數據；“空”是指SP指向的存儲單元將保存下一個入棧的數據。4種形式的棧都對應相同的邏輯數據結構，本書后續章節除非特殊說明，否則均以“滿遞增堆棧”為例。

>>> 2.3.2 入棧與出棧

假設允許入棧和出棧數據為int，即sp為(int *)類型變量。如果入棧的數據小于sizeof(int)個字節，則需要將其轉換成int類型數據才能入棧，且出棧后也要進行相應的類型轉換。對于入棧的數據大于sizeof(int)個字節，則只能拆分數據，一次入棧數據的一部分，通過多次入棧完成整個數據的入棧；而出棧這個數據也要多次，全部出棧后再組合成原始數據。

1. 入棧（push）操作

如果將sp當作(int *)類型的變量，則對于滿遞增堆棧來說，將數據data入棧用C語言描述如下（詳見圖2.8）：

圖2.8 入棧操作示意圖

如果data的長度大于sizeof(int)，則需要將數據拆分后多次入棧，入棧的順序可以先低位后高位，也可以反過來。如果入棧的順序為先低位后高位，其示例詳見程序清單 2.27。

程序清單 2.27 先低位后高位順序入棧示例

這里假設data可以象整數一樣移位，且sizeof(data)是sizeof(int)的4倍。

2. 出棧（pop）操作

如果將sp當作(int *)類型的變量，則對于滿遞增堆棧來說，將數據出棧用C語言描述如下（假設出棧的數據保存到變量data中，詳見圖2.9）：

圖2.9 出棧操作示意圖

如果出棧數據data的長度大于sizeof(int)，則需要多次出棧后拼接數據，其拼接的順序為入棧的反序。如果入棧的順序為先低位后高位，詳見程序清單 2.28。

程序清單 2.28 先高位后低位順序出棧示例

這里假設data可以象整數一樣進行位操作，且sizeof(data)是sizeof(int)的4倍。

>>> 2.3.3 函數的調用與返回

在討論ADT棧之前，首先看一種用于處理程序運行時的函數調用的系統棧。每當函數被調用時，系統首先創建一個稱作活動記錄或棧幀的結構，將其放在系統棧的棧頂。初始時，被調函數的活動記錄只包含一個指向前一個活動記錄的指針和一個返回地址。前一個活動記錄的指針指向調用函數的活動記錄，而返回地址包含的是函數調用結束后下一條執行語句的地址。因為在任何時刻只有一個函數被執行，所以被執行的函數就是活動記錄位于系統棧棧頂的函數。

如果該函數又調用其它函數，那么函數中的局部變量（靜態局部變量除外）及其參數也將加到其活動記錄中，然后為被調函數創建一個新的活動記錄并存放在系統棧棧頂的函數。當被調函數結束時，刪除該活動記錄。此時調用函數的活動記錄又位于系統棧的棧頂，繼續運行該函數。

C語言通過硬件棧保存函數的返回地址，被調用函數將返回地址出棧到程序計數器PC中，以返回到調用點，其示例代碼詳見程序清單2.29。

程序清單2.29 函數的調用與返回示例

對于程序清單2.29（10）來說，用C語言描述如下：

對于程序清單2.29（5）來說，用C語言描述如下：

由此可見，當調用函數時，將主程序代碼行的下一條指令的地址保存到棧中；當函數返回時，程序就會從棧中獲取該地址，并從那一點繼續向下執行。在函數調用了其它函數的情況下，將每一個返回地址都放到棧中；當函數結束時，就可以找到它們在棧中的地址。