对堆和栈的理解一直比较模糊，在看了网友的各种解释后，记录一下，以便日后查看。

数据结构中的栈和堆

  • 首先，我们要知道堆栈是两种数据结构：堆和栈。
  • 堆和栈都是一种数据项按序排列的数据结构。

栈 就像装数据的桶或箱子

栈是具有FILO(先进后出)性质的数据结构。

  • 就如同我们想要取出放在箱子里面底下的东西（放入比较早的物体），需要先移开压在它上面的物体（放入比较晚的物体）。

堆 就像一颗倒过来的树

  • 堆是一种经过排序的树形数据结构，每一个节点都有一个值。
  • 通常我们所说的堆的数据结构，是指二叉堆。
  • 堆的特点是根结点的值最小/最大，且根结点的两个子树也是一个堆。
    • 由于堆的这个特性，常用来实现优先队列，堆的存储是随意的，就如同在图书馆的书架上取书，虽然书的摆放是有顺序的，但是我们想取任意一本书时不必像栈一样，先要取出前面所有的书，书架的这种机制不同于箱子，我们可以直接取出我们想要的任意一本书。

内存分配中的栈和堆

内存分配中的堆和栈与数据结构中的堆和栈是有区别的。

下面说说C语言程序内存分配中的堆和栈，一般情况下，程序存放在 ROM（只读内存，比如硬盘）或 Flash 中，运行时需要拷贝到 RAM（随机存储器）中执行，RAM 会分别存储不同的信息，如下图所示：

内存分配

内存中的栈区处于相对较高的地址,以地址的增长方向为上的话:

  • 栈地址是向下增长的，栈中分配局部变量空间；
  • 堆区是向上增长的，用于分配程序员申请的内存空间；
  • 另外还有静态区，是分配静态变量，全局变量空间的；
  • 只读区是分配常量和程序代码空间的；以及其他一些分区。

看一个网上很流行的经典例子

  • main.cpp
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int a = 0;// 全局初始化区
char *p1;//全局未初始化区
main(){
 int b;//栈区
 char s[] = "abc";//栈区
 char *p2;//栈区
 char *p3 = "123456";//123456\0在常量区，p3在栈区
 static int c = 0;//全局（静态）初始化区
 p1 = (char*)malloc(10);//堆区
 p2 = (char*)malloc(20);//堆区
}

0.申请方式和回收方式不同

栈（stack）是系统自动分配空间，例如：我们定义一个 char a;系统会自动在栈上为其开辟空间。 堆（heap）则是程序员根据需要自己申请的空间，例如：malloc(10); 开辟十个字节的空间。 由于栈的空间是自动分配自动回收的，所以栈上的数据的生存周期只是在函数的运行过程中，运行结束就释放掉，不可以再访问。而堆上的数据只要程序员不释放空间，就一直可以访问到，不过缺点是一旦忘记释放会造成内存泄露。（MRC）（OC 的 ARC 下系统会自动释放）

1.申请后系统的响应

栈：只要栈的剩余空间大于所申请的空间，系统就会为程序提供内存，否则将报异常提示栈溢出。 堆：首先应该知道操作系统有一个记录时间内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个大于申请空间的的堆结点，然后将该结点从空闲链表中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内存空间中的首地址处记录本次分配的空间大小，这样，代码中的 delete 语句才能正确的释放内存空间。另外，由于找到的堆结点的大小不一定正好等于申请的大小，系统会自动的将多余的那部分重新放入空闲链表中。也就是说，堆会在申请后做一些后续工作，这就会引出申请效率的问题。

2.申请效率的比较

栈：系统分配，速度快。但程序员无法控制。 堆：程序员申请的，一般速度比较慢，而且容易产生内存碎片，不过用起来方便。

3.申请大小的限制

栈：在 windows 下，栈是向低地址扩展的数据结构，是一块连续的内存区域，这句话的意思是栈顶的地址和栈的空间最大容量是系统预先规定好的，在 Windows 下，栈的大小是2M（也有的说是1M，总之是一个在编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将提升 overflow。因此能从栈获得的空间比较小。 堆：堆是向高地址扩展的数据结构，是不连续的内存区域。因为系统是由链表来存储的空闲地址的，自然是不连续的。而链表的遍历方向是由低地址向高地址的。堆得大小受限于计算机系统中有效的虚拟内存。由此可见，堆可以获得的空间比较灵活，也比较大。

4.堆和栈中存储的内容

由于栈的大小有限，所以用子函数还是有物理意义的，而不仅仅是裸机意义。 栈：在函数调用时，第一个进栈的是主函数中函数调用后的下一条指令（函数调用语句的下一条可执行语句）的地址，然后是函数的各个参数，在大多数的C编译器中，参数是由右向左入栈的，然后是函数中的局部变量。 当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指向最开始存的地址，也就是主函数中的下一条指令，程序由该点继续运行。 堆：一般是在堆的头部用一个字节存放堆的大小信息。堆中的具体内容由程序员安排

5.存取效率的比较

1
2

char s1[] = "abc";
char *s2 = "ABC";

abc 是在运行时赋值的，放在栈中。 ABC 是在编译时就确定的，放在堆中。 但是，在以后的存取中，在栈上的数组比指针所指向的字符串的存取速度要快（例如堆）。 比如：

1
2
3
4
5
6
7
8
9

#include 
void main(){
 char a = 1;
 char c[] = "1234567890";
 char *p = "1234567890";
 a = c[1];
 a = p[1];
 return;
}

对应的汇编代码:

1
2
3
4
5
6
7

10: a = c[1]; 
00401067 8A 4D F1 mov cl,byte ptr [ebp-0Fh] 
0040106A 88 4D FC mov byte ptr [ebp-4],cl 
11: a = p[1]; 
0040106D 8B 55 EC mov edx,dword ptr [ebp-14h] 
00401070 8A 42 01 mov al,byte ptr [edx+1] 
00401073 88 45 FC mov byte ptr [ebp-4],al

关于堆和栈区别的比喻

堆和栈的区别可以引用一位前辈的比喻来看出：

使用栈就象我们去饭馆里吃饭，只管点菜（发出申请）、付钱、和吃（使用），吃饱了就走，不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作，他的好处是快捷，但是自由度小。

使用堆就象是自己动手做喜欢吃的菜肴，比较麻烦，但是比较符合自己的口味，而且自由度大。比喻很形象。