谈谈堆与栈：数据结构和内存角色

然而，除此之外，它们在计算机的内存中也扮演着不同的角色。

数据结构

堆

• 一种特殊的、基于树的数据结构
• 通常可以有两种类型：
  1. 最大堆：根结点的键值是所有堆结点键值中最大者的堆
  2. 最小堆：根结点的键值是所有堆结点键值中最小者的堆

堆（图片来自 GeeksforGeeks）

栈

• 一种线性的数据结构
• 遵循执行操作的特定顺序：后进先出（FIFO）

栈（图片来自 GeeksforGeeks）

内存的用途

在计算机中，内存的用途大致可以分为四个方面：

1. 代码区：放置二进制代码
2. 数据区：用于存储全局变量等
3. 堆区：为动态分配预留的内存空间
4. 栈区：为执行线程留出的内存空间

堆区

堆是为动态分配预留的内存空间。

和栈不一样，从堆上分配和重新分配块没有固定模式，你可以在任何时候分配和释放它。

堆包含一个链表来维护已用和空闲的内存块。在堆上新分配（用 new 或者 malloc）内存是从空闲的内存块中找到一些满足要求的合适块，这个操作会更新堆中的块链表。这些元信息也存储在堆上，经常在每个块的头部一个很小的区域。

栈区

栈是为执行线程留出的内存空间。

1. 当函数被调用的时：系统栈会为这个函数开辟一个新的栈帧（包含局部变量、函数参数、返回值等），并把它压入栈中。这个栈帧中的内存空间被它所属的函数独占，正常情况下是不会和别的函数共享。
2. 当函数执行完毕时：系统栈会弹出该函数所对应的栈帧。

栈帧：也叫过程活动记录，是编译器用来实现函数调用过程的一种数据结构。

举个例子：

package main

func A() {
    // ...
    B()
}

func B() {
    // ...
}

func main() {
    A()
}

在上述代码片段中，main() 函数调用了函数 A()，函数 A() 又调用了函数 B()。执行过程如下：

1. main() 函数开始执行：将自己的栈帧压入栈
2. main() 函数调用函数 A()：将函数 A() 的栈帧压入栈
3. A() 函数调用函数 B()：将函数 B() 的栈帧压入栈
4. B() 函数执行完毕，从栈顶弹出 B() 的栈帧，此时 A() 的栈帧被暴露在栈顶，处理器能根据其中的返回地址跳回 A() 的代码区继续执行代码
5. A() 函数执行完毕，从栈顶弹出 A() 的栈帧，此时 main() 函数的栈帧被暴露在栈顶，处理器根据其中的返回地址跳回 main() 的代码区继续指定代码

栈要受到内存块的限制，不断的函数嵌套或为局部变量分配太多的空间，可能会导致栈溢出。也就是我们常说「递归导致栈溢出」的原因了。

总结

堆

• 堆是一种特殊的、基于树的数据结构，通常有最大堆和最小堆两种类型
• 堆区是为动态分配预留的内存空间

栈

• 栈是一种线性的数据结构，遵循后进先出
• 栈区是为执行线程留出的内存空间

参考资料

[1]

堆: https://www.geeksforgeeks.org/heap-data-structure/

[2]

栈: https://www.geeksforgeeks.org/stack-data-structure/