栈和堆以及栈区和堆区的区别

栈和堆以及栈区和堆区的区别

数据结构中的栈和堆

• 栈：具有先进后出性质的数据结构
• 堆：一种经过排序的树形数据结构，节点的值最大/小，且根节点的两个子树也是一个堆，一般指二叉堆，常用来实现优先队列

进程的内存模型中的栈区和堆区

空间分配机制：

• 栈区：由编译器自动分配释放，存放函数的参数值，局部变量值等，操作类似于数据结构中的栈。只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出，一般 Linux 为 8MB(ulimit -a 查看)
• 堆区：一般由程序员/用户程序通过 malloc 或 free 等分配释放，若程序员/用户程序不主动释放，程序结束时可能由操作系统回收，分配和维护方式类似于链表。
  操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时， 会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内存空间中的首地址处记录本次分配的大小，这样，代码中的delete语句才能正确的释放本内存空间。另外，由于找到的堆结点的大小不一定正好等于申请的大小，系统会自动的将多余的那部分重新放入空闲链表中。

申请和存取效率比较：

• 栈：栈由系统自动分配，速度较快。但程序员是无法控制的。访问时，由于直接将数据读取到寄存器，寻址速度较快
• 堆：由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便。访问时，需要先把指向堆上数据的指针读入寄存器，然后读取数据，较慢

Ref:

• 堆和栈的区别 之 数据结构和内存