堆与栈的区别

应该算是比较经常会问到的面试题，我们需要从数据结构中的栈、数据结构中的堆、内存栈和内存堆四个方面来回答。

数据结构中的栈

数据结构中的栈是一种先进后出（First in,Last out）的线性数据结构，主要有push（O(1)）、peek（O(1)）和pop（O(1)）三种方法，对应JDK中的Stack（顺序栈）一级LinkedList（链式栈）。

数据结构中的堆

数据结构中的堆是一种用数组存储完全二叉树的非线性数据结构，又被称为优先队列，分为最小堆和最大堆，对应JDK中Priorigy Queue，能在logN时间内完成插入（offer）及（poll）操作。

内存栈

内存栈，又称栈内存，一般由编译器自动分配和释放，主要有三个特点：

1. 函数的压栈、弹出过程符合先进后出的原则；
2. 无论是函数还是变量，都是从高地址向低地址分配；
3. 函数、变量的分配在运行前就已经完成了，运行时的回收是及时的，且速度快，时间复杂度O(1)。

内存堆

内存堆，又称堆内存，在Java中堆内存用来存放由new创建的对象和数组，主要有以下特点：

1. 堆内存，是一个静态链表；
2. 在运行期间进行分配，分配方式是从低地址向高地址进行扩展；
3. 内存块有已使用和闲置量中状态；
4. 内存分配过程就是将闲置的内存块标记为已使用状态，回收过程则相反；
5. 因为总是从头往后（低地址向高地址）寻找闲置内存块，所以分配过程时间复杂度为O(N);
6. 对于C/C++等语言来说，分配的堆内存需要程序员手动回收，对于Java语言来说，GC线程可自动回收。