一、堆和栈，他们之间的区别和联系

堆

数据结构中堆是满足父子节点大小（比如大根堆中规定父节点的值要比子节点大）关系的一种完全二叉树。由于是完全二叉树，可以用数组来实现，用节点编号来访问和操作节点，简化程序，提升效率。而其大小关系则为我们查询堆中极值提供了常数级别的时间复杂度，又由二叉树的性质，插入和删除则为对数级别时间复杂度。这就好像地位不同的人在排队，排在最前面的一定是地位较高的人，所以堆是优先队列（Priority Queue）实现的基础。利用这一特性，可以加速某些需要频繁取队列中极值的算法比如 A* 算法等。

栈

数据结构中的栈则是一种相当简单的结构。就像是只有一个口的深深的文件桶，先进去的文件会被压在下面（push），而且我们每次只能取到最上面的文件（pop），体现了其先进后出（FILO）的特性。虽然栈操作简单，但也有如单调栈等在栈内保持一定数据特性的变种。

联系与区别

操作系统中的堆和栈都是指内存空间，不同的是堆为按需申请、动态分配，例如 C 中的 malloc 函数和 C++ 中的 new 操作（当然 C++ 的 new 不仅仅是申请内存这么简单）。内存中的空闲空间并不是连续的，而是不同程序占用了不同的一块一块的内存，即使是同一个程序也可能占用了不同地方的多块内存。操作系统中则会对这些空间进行统一的管理，在应用程序提出申请时，就会从堆中按照一定算法找出一块可用内存，标记占用空间等信息之后返回其起始地址给程序。在程序结束之前，操作系统不会删除已经申请的内存，而是要靠程序主动提出释放的请求（free、delete），如果使用后忘记释放，就会造成所谓的内存泄漏问题。因此堆基本上可以理解为当前可以使用的空闲内存，但是其申请和释放都要程序员自己写代码管理。

而操作系统的栈则是程序运行时自动拥有的一小块内存，大小在编译期时由编译器参数决定，用于局部变量的存放或者函数调用栈的保存。在 C 中如果声明一个局部变量（例如 int a），它存放的地方就在栈中，而当这个局部变量离开其作用域之后，所占用的内存则会被自动释放，因此在 C 中局部变量也叫自动变量。栈的另一个作用则是保存函数调用栈，这时和数据结构的栈就有关系了。在函数调用过程中，常常会多层甚至递归调用。每一个函数调用都有各自的局部变量值和返回值，每一次函数调用其实是先将当前函数的状态压栈，然后在栈顶开辟新空间用于保存新的函数状态，接下来才是函数执行。当函数执行完毕之后，栈先进后出的特性使得后调用的函数先返回，这样可以保证返回值的有序传递，也保证函数现场可以按顺序恢复。操作系统的栈在内存中高地址向低地址增长，也即低地址为栈顶，高地址为栈底。这就导致了栈的空间有限制，一旦局部变量申请过多（例如开个超大数组），或者函数调用太深（例如递归太多次），那么就会导致栈溢出（Stack Overflow），操作系统这时候就会直接把你的程序杀掉。

延伸阅读：

二、链表与数组的区别

数组：使用一块连续的内存空间地址去存放数据，例如：

int  a[5]={1,2,3,4,5}。突然我想继续加两个数据进去，但是已经定义好的数组不能往后加，只能通过定义新的数组

int b[7]={1,2,3,4,5,6,7}; 这样就相当不方便比较浪费内存资源,对数据的增删不好操作。

链表：使用多个不连续的内存空间去存储数据，可以节省内存资源（只有需要存储数据时，才去划分新的空间），对数据的增删比较方便。

上一篇

项目计划管理怎么考核?

下一篇

用链表的目的是什么?