周立功教授數(shù)年之心血之作《程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)》以及《面向AMetal框架與接口的編程（上）》，書本內(nèi)容公開后，在電子行業(yè)掀起一片學習熱潮。經(jīng)周立功教授授權(quán)，本公眾號特對《程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)》一書內(nèi)容進行連載，愿共勉之。

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

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

>>> 2.3.1 堆棧

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

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

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

圖2.7 四種棧示意圖

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

>>> 2.3.2 入棧與出棧

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

1. 入棧（push）操作

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

圖2.8 入棧操作示意圖

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

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

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

2. 出棧（pop）操作

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

圖2.9 出棧操作示意圖

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

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

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

>>> 2.3.3 函數(shù)的調(diào)用與返回

在討論ADT棧之前，首先看一種用于處理程序運行時的函數(shù)調(diào)用的系統(tǒng)棧。每當函數(shù)被調(diào)用時，系統(tǒng)首先創(chuàng)建一個稱作活動記錄或棧幀的結(jié)構(gòu)，將其放在系統(tǒng)棧的棧頂。初始時，被調(diào)函數(shù)的活動記錄只包含一個指向前一個活動記錄的指針和一個返回地址。前一個活動記錄的指針指向調(diào)用函數(shù)的活動記錄，而返回地址包含的是函數(shù)調(diào)用結(jié)束后下一條執(zhí)行語句的地址。因為在任何時刻只有一個函數(shù)被執(zhí)行，所以被執(zhí)行的函數(shù)就是活動記錄位于系統(tǒng)棧棧頂?shù)暮瘮?shù)。

如果該函數(shù)又調(diào)用其它函數(shù)，那么函數(shù)中的局部變量（靜態(tài)局部變量除外）及其參數(shù)也將加到其活動記錄中，然后為被調(diào)函數(shù)創(chuàng)建一個新的活動記錄并存放在系統(tǒng)棧棧頂?shù)暮瘮?shù)。當被調(diào)函數(shù)結(jié)束時，刪除該活動記錄。此時調(diào)用函數(shù)的活動記錄又位于系統(tǒng)棧的棧頂，繼續(xù)運行該函數(shù)。

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

程序清單2.29 函數(shù)的調(diào)用與返回示例

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

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

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