堆与栈
堆，栈，堆栈，队列
堆
堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
将根节点最大的堆叫做
最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。堆是在程序运行时，而不是在程序编译时，申请某个大小的内存空间。即动态分配内存，对其访问和对一般内存的访问没有区别。
堆是应用程序在运行的时候开发者请求操作系统分配给自己内存，一般是申请 / 给予的过程。
堆是指程序运行时申请的动态内存，而栈只是指一种使用堆的方法 (即先进后出)。
栈
栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。
栈就是一个桶，后放进去的先拿出来，它下面本来有的东西要等它出来之后才能出来（先进后出）
栈 (Stack) 是操作系统在建立某个进程时或者线程（在支持多线程的操作系统中是线程）为这个线程建立的存储区域，该区域具有 FIFO 的特性，在编译的时候可以指定需要的 Stack 的大小。
堆栈
注意：其实堆栈本身就是栈，只是换了个抽象的名字。
堆栈的特性： 最后一个放入堆栈中的物体总是被最先拿出来， 这个特性通常称为后进先出 (LIFO) 队列。 堆栈中定义了一些操作。 两个最重要的是 PUSH 和 POP。 PUSH 操作在堆栈的顶部加入一 个元素。POP 操作相反， 在堆栈顶部移去一个元素， 并将堆栈的大小减一。
堆、栈区别
- 申请方式
堆是由程序员自己申请并指明大小，在 c 中 malloc 函数 如 p1 = (char *)malloc(10);
栈由系统自动分配，如声明在函数中一个局部变量 int b; 系统自动在栈中为 b 开辟空间
- 申请后系统的响应
栈：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。
堆：首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会 遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内 存空间中的首地址处记录本次分配的大小，这样，代码中的 delete 语句才能正确的释放本内存空间。另外，由于找到的堆结点的大小不一定正好等于申请的大 小，系统会自动的将多余的那部分重新放入空闲链表中。
- 申请大小的限制
栈：在 Windows 下, 栈是向低地址扩展的数据结 构，是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的，在 WINDOWS 下，栈的大小是 2M（也有的说是 1M，总之是 一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将提示 overflow。因此，能从栈获得的空间较小。
堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。
- 申请效率的比较：
栈由系统自动分配，速度较快。但程序员是无法控制的。
堆是由 new 分配的内存，一般速度比较慢，而且容易产生内存碎片, 不过用起来最方便.
- 释放方式比较： 栈使用的是一级缓存， 他们通常都是被调用时处于存储空间中，调用完毕立即释放。
堆则是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定（并不是一旦成为孤儿对象就能被回收）。所以调用这些对象的速度要相对来得低一些。
队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列中没有元素时，称为空队列。
建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针 front，它指向队头元素；另一个是队尾指针 rear，它指向下一个入队元素的存储位置。
队列采用的 FIFO(first in first out)，新元素（等待进入队列的元素）总是被插入到链表的尾部，而读取的时候总是从链表的头部开始读取。每次读取一个元素，释放一个元素。所谓的动态创建，动态释放。因而也不存在溢出等问题。由于链表由结构体间接而成，遍历也方便。（先进先出）
堆、栈、队列之间的区别
堆是在程序运行时，而不是在程序编译时，申请某个大小的内存空间。即动态分配内存，对其访问和对一般内存的访问没有区别。
栈就是一个桶，后放进去的先拿出来，它下面本来有的东西要等它出来之后才能出来。（后进先出）
队列只能在队头做删除操作, 在队尾做插入操作. 而栈只能在栈顶做插入和删除操作。（先进先出）
参考：