当函数执行完毕后，如何返回调用处？

周立功教授数年之心血之作《程序设计与数据结构》以及《面向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 函数的调用与返回

在讨论AD