一、堆和栈的理论知识

堆和栈都是一种数据项按序排列的数据结构。

“栈”一般是由硬件（CPU）实现的一种数据结构，其特点是后进先出，也就是说后存放的先取，先存放的后取。CPU用栈来保存调用子程序（函数）时的返回地址，高级语言有时也用它作为局部变量的存储空间。

“堆”是个实实在在的软件概念，堆是一种经过排序的树形数据结构，每个结点都有一个值。常用来实现优先队列，堆的存取是随意。使用与否完全由编程者“显示地（explicitly）”决定，如malloc。

程序经过编译连接生成执行程序后，堆和栈的起始地址就已经确定了（具体说，是通过“连接程序”），在一个具有反向增长的栈的CPU上，数据空间可表示如下：

低　　　  ->｜－－－－－－－－－－－－－－－－－｜
　　　　　　｜　全局量（所有已初始化量 .data，　｜
　　　　　　｜　未初始化量 .bss ）　　　　　　　｜
　  堆起始->｜－－－－－－－－－－－－－－－－－｜
　　　　　　｜　　　　堆向高地址增长　　　　　　｜
　　　　　　｜　　　　　　　　　　　　　　　　　｜
　　　　　　｜　　　　　　　　　　　　　　　　　｜
　　　　　　｜　　　　　自由空间　　　　　　　　｜
　　　　　　｜　　　　　　　　　　　　　　　　　｜
　　　　　　｜　　　　　　　　　　　　　　　　　｜
　　　　　　｜　　　　栈向低地址增长　　　　　　｜
高  栈起始->｜－－－－－－－－－－－－－－－－－｜

在内存中，“堆”和“栈”共用全部的自由空间，只不过各自的起始地址和增长方向不同，它们之间并没有一个固定的界限，如果在运行时，“堆”和“栈”增长到发生了相互覆盖时，称为“栈堆冲突”，系统肯定垮台。由于开销方面的原因，各种编译在实现中都没有考虑解决这个问题，只有靠设计者自己解决，比如增加内存等。

1）申请方式 
栈（stack）: 由系统自动分配。 例如，声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间 
堆（heap）: 需要程序员自己申请，并指明大小，在c中malloc函数 
                 如p1 = (char *)malloc(10); 
                 在C++中用new运算符 
                 如p2 = (char *)malloc(10); 
                 但是注意p1、p2本身是在栈中的。

由于栈上的空间是自动分配自动回收的，所以栈上的数据的生存周期只是在函数的运行过程中，运行后就释放掉，不可以再访问。

而堆上的数据只要程序员不释放空间，就一直可以访问到，不过缺点是一旦忘记释放会造成内存泄露。

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

小结： 
堆和栈的区别可以用如下的比喻来看出： 
使用栈就象我们去饭馆里吃饭，只管点菜（发出申请）、付钱、和吃（使用），吃饱了就走，不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作，他的好处是快捷，但是自由度小。 
使用堆就象是自己动手做喜欢吃的菜肴，比较麻烦，但是比较符合自己的口味，而且自由度大。

堆和栈