[编程语言] 堆和栈的全面总结

大家好，欢迎来到IT知识分享网。

操作系统中的栈：

        由编译器自动分配和自动释放，一个函数对应一个栈，用于存放函数的参数值、函数调用完成后的返回值和函数体内的局部变量等。栈占用连续的一段内存空间，其操作和组织方式与数据结构中的栈十分相似。栈是为了执行线程留出的内存空间。当调用函数时创建栈，当函数执行完毕，栈就被回收了。

操作系统中的堆：

         由程序员手动进行内存的申请与释放。由于程序员手动申请及释放的内存块存放在堆中，堆中有很多内存块，所以堆的组织方式类似于链表。操作系统中的堆与数据结构中的堆完全不同。我觉得通俗的理解可以是这样的：数据结构中的堆是”结构堆”，有严谨的逻辑和操作方式，而操作系统中的堆，更像是使用链表将”一堆杂乱的东西”联系起来。堆是为动态分配预留的内存空间，其生命周期为整个应用程序的生命周期。当应用程序结束以后，堆开始被回收。

        每个线程都有一个属于自己的栈，但每一个应用程序通常只有一个堆（一个应用程序使用了多个堆的情况也是有的）。当线程被创建的时候，设置了栈的大小。在应用程序启动的时候，设置了堆的大小。栈的大小通常是固定的，但是堆可以在需要的时候进行扩展，如程序员向操作系统申请更多内存的时候。

由于栈的工作方式类似于数据结构中的栈，堆的工作方式类似于链表，所以栈显然会比堆快得多。按照栈的存取方式，想要释放内存或是新增内存，只需要相应移动栈顶指针即可。堆则要首先在内存的空闲区域寻找合适的内存空间，然后占用，然后指向这块空间。显然堆比栈要复杂得多。

       接下来本来是想将栈和堆分开进行陈述，斟酌了一下还是决定从同一方面对栈和堆进行比较。有了比较才明显。

1. 在创建栈的时候栈的大小就固定了，因为栈要连续占用一段空间。根据上文所属的堆的特性，决定了堆的大小是动态的，其分配和释放也是动态的。

2. 栈中的数据过多会导致爆栈，比如dfs写搓了。而假如堆也爆了的话。。。那说明内存也爆了。

3. 每个函数的栈都是各自独立的，但是一个应用程序的堆是被所有的栈共享。既然提到共享，那么这里就有”并行存取”的问题了。实际上并行存取是由堆控制的，而不是被栈控制的。

4. 栈的作用域仅限于函数内部，栈在函数结束的时候会自行释放掉空间。但是创建于堆上的变量必须要手动释放，堆中的变量不存在作用域的问题，因为堆是全局的。

5. 栈中存放的是函数返回值地址、函数参数，函数内的局部变量等。堆中存放的是由程序员手动进行申请的内存块(malloc、new等)。

6. 堆和栈都按需进行分配。栈有严格的容量上限，而堆的容量上限则是”不严格”的。堆并没有固定的容量上限，它与当前的剩余内存量有关（其实还不准确，操作系统还有虚拟内存或其他概念，所以堆的工作方式较为抽象）。

7. 通过移动栈顶指针即可实现栈内存的分配。在堆上分配内存的做法则是从当前空闲的内存中找一块满足大小的区域，就像链表的工作方式一样。

8. 只要没有超出栈容量，栈可以进行任意的释放和申请内存，并不会造成内存出现问题，是安全的。而堆不同，大量申请和释放小内存块可能会造成内存问题，这些小的内存块零散的分布在内存中，导致后续大块的内存申请失败，因为虽然空闲的内存足够多，但是并不连续。这种情况下的小块内存叫做”堆碎片”。不过这并不是什么大问题，具体详见”操作系统”的有关知识。

9. 栈在确定了栈底地址后，其栈顶指针从栈底地址开始，逐渐向低地址走。也就是说栈的存储空间是从高地址走向低地址的。堆则相反，堆在申请空间的时候通常逐渐往高地址的方向来寻找可用内存。

纯粹的文字描述显得枯燥无味，我们来看一些代码：

#include <iostream>
using namespace std;

void func()
{
   int i = 5;
   int j = 3;
   int k = 7;
   int *p = &i;
   printf("%d\n", *p);
   printf("%d\n", *(p-1));
   printf("%d\n", *(p-2));

}

int main()
{
   func();

   getchar();
   return 0;
}

上述代码的结果是：5 3 7

从结果中我们可以看出两件事：

一是栈地址是连续的，我们可以通过一个指针和一个相对的大小，来”偏移”到别的变量上去。

二是从中可以看出栈地址是从高到低分布的，栈底在高地址，朝低地址的方向生长。所以程序中是p-1而不是p+1。

void func()
{
	int *p = NULL;
	// 上行代码是个重点。这个指针待会会用于申请新的内存。
	// 此时除了它自身作为一个变量需要占用4字节的空间(指针都占4字节)，没有任何其他空间被申请。
	// 这个指针变量是函数的局部变量，所以它被创建在栈上。
	int num = 100; 		// 这个变量同样创建于栈上。
	int buffer[100];	// 同样的，buffer占用了栈的400字节的空间
	p = new int[100];	// 注意，程序员手动申请了一块空间，这400字节的内存创建于堆上。
	// 所以此刻p的状态是：p为函数局部变量，它指向了一块全局范围的内存空间。
}
// 函数体结束。上述函数有个严重的问题，那就是指针p的内存泄露。
// 正确的做法是在函数最后delete掉这块内存，或是返回这块内存的地址以供继续使用。

接下来我们来了解一下当调用一个函数的时候所发生的事情：

首先操作系统为这个函数分配了一个栈，因为在调用完这个函数以后需要能正确返回到下一条语句并继续执行，所以第一步是将调用完函数的下一条指令的地址压入栈。这样当函数调用完成，栈顶指针一点点释放内存以后，栈顶指针指向了这个地址，就能返回到正确的位置继续执行了。

int main()
{
	func();
	printf("%d\n", 100);
	return 0;
}

比如上述代码，在调用func之前，首先把func的下一条语句，也就是printf语句的地址，存在栈中。这样函数调用完成后就能正确返回到这个printf并继续往后执行了。注意这里的地址是指令地址，而不是变量地址什么的。它有那么点类似于操作系统中的程序计数器（PC，即Program Counter）。然后把实参从右到左的顺序依次入栈（大多数的C/C++编译器为从右到左）接着是函数中的各种局部变量。要注意的是函数中的static变量是不入栈的。全局变量和static变量在编译的时候就已经在静态存储区分配好内存了。

如果这个时候该函数又调用了其它函数，过程也是一样的，首先是返回地址，然后是参数和局部变量。这样在每层调用结束，栈顶指针不断下降（释放内存）的时候，就能正确返回到之前调用的位置并继续往下执行了。

出栈，或者说释放内存的过程，根据栈的特性，是相反的，所以就不赘述了。

一个 C或C++程序，它眼中的内存地址分分为这么五个区域：

栈区（stack）、堆区（heap）、全局静态区（static）、文字常量区和程序指令区。

栈区和堆区前面已经介绍过，全局静态区用于存放全局变量和静态static静态变量，全局静态区分为两块内容：一块用于初始化以后的全局变量和静态变量，一块用于未初始化的全局变量和静态变量。全局静态区和堆一样，程序结束后由操作系统进行释放。文字常量区用于存放常量字符串，程序结束后由操作系统进行释放。程序指令区最好理解，就是存放程序代码的二进制指令。

int cnt;		// 存放在全局静态区的未初始化区
int num = 0;	// 存放在全局静态区的已初始化区
int *p;			// 存放在全局静态区的未初始化区
int main()
{
	int i, j, k;			// 存放在栈区
	int *pBuffer = (int *)malloc(sizeof(int) * 10);	// 指针pBuffer在栈中，该内存在堆中
	char *s = "hactrox";	// 指针s存放在栈中，字符串存放在文字常量区中
	char str[] = "hactrox";	// str和字符串存放在栈中
	static int a = 0;		// a存放在全局静态区的已初始化区
}

char *s = “hactrox”;    // “hactrox”在文字常量区，s指向这个区域中的”hactrox”，所以这可以理解为，首先在文字常量区创建了这个字符串，然后s指向这个字符串这样两个步骤。s本身作为一个局部变量存储在栈中。

// 下面的代码是错误的，指针还没指向就直接赋值了？

int *p = 5;

// 下面的代码才是正确的，首先要创建这个int型变量，然后p指向这个变量。new来的int变量在堆中。

int *p = new int(5);

接下来我们看一看一个非常常见的问题：下述代码有没有什么问题？有问题的话问题在哪里？

#include <iostream>
using namespace std;

char* f1()
{
   char *s = "hactrox";
   return s;
}

char* f2()
{
   char s[] = "hactrox";
   return s;
}

int main()
{
   printf("%s\n", f1());
   printf("%s\n", f2());

   getchar();
   return 0;
}

问题在于第二个函数，f2并不能正确返回那个字符串。在函数f1中，”hactrox”字符串创建于文字常量区，然后返回该常量字符串的地址，因为文字常量区的字符串是全局的，虽然指针s是局部变量，但是s在消亡前已经把目标地址送出来了，所以s消亡与否不是重点，重点是返回的地址所指向的区域还在，所以能正确显示。在函数f2中，“hactrox”与s均为局部变量，它们保存在栈中。虽然s同样返回了一个地址，但这个地址所指向的内存已经被释放掉了。地址有效，但目标已无效。所以输出的只是乱码。

关于文字常量区还有一些东西要说（好像和本博客的主题扯远了？）

#include <iostream>
using namespace std;

void func()
{
	char *str1 = "123";
	printf("%x\n", str1);
	char *str2 = "123";
	// 同在文字常量区，编译器可能会将str2直接指向str1所指向的内存，
	// 而不是开辟新的空间来存放第二个相同字符串。
	// 通过打印str2的指针可验证
	printf("%x\n", str2);

	char *s1 = "hactrox";
	printf("%x\n", s1);
	char *s2 = "hactrox";
	printf("%x\n", s2);
}
int main()
{
	func();

	getchar();
	return 0;
}

char s[] = “hactrox”;

char *s = “hactrox again”;

第二段代码，即文字常量区变量在编译的时候就已经确定了，

而第一段代码，是在运行的时候进行赋值的。

这样看起来貌似第二段代码的效率要高，其实不然，

当在运行时刻用到这两个变量的时候，对于第一段代码，直接读取字符串，而对于第二段代码，首先读取该字符串指针，然后根据指针再读取字符串，显然效率就下降了。

其实我觉得关注栈和堆，其实主要是关注作用域、生命周期和有效性的问题。

指针被释放了，不代表指针指向的内存会被释放。同样的，指针指向的内存被释放了，不代表指针会被同步释放或自动指向NULL，指针依旧指向那块已经失效了的地址。这块地址不能用，谁都不能保证一块已经失效的地址接下来会发生什么。