堆与栈的区别 | TryCoding.Fun

堆与栈的区别

理解程序内存管理和数据结构中的堆与栈概念

问题

堆与栈有什么区别？

堆（Heap）与栈（Stack）在不同场景下有不同含义：程序内存布局中表示两种内存管理方式，数据结构中表示两种常用的数据结构。

栈（Stack）

栈由操作系统自动分配和释放，用于存放函数的参数值、局部变量等。栈的内存地址由高到低生长，后定义的变量地址低于先定义的变量。相邻变量的地址之间不会存在其它变量。栈中数据的生命周期随函数执行完成而结束。

堆（Heap）

堆由开发人员分配和释放，若不释放则程序结束时由操作系统回收。堆的内存地址由低到高生长，但后申请的内存不一定在先申请的内存后面，因为会复用已释放的内存空间。堆中数据若未释放，生命周期等同于程序生命周期。

堆的分配过程：操作系统维护一个记录空闲内存地址的链表，收到申请时遍历链表，找到第一个空间足够的节点分配给程序，并在内存首地址记录分配大小，多余部分放回空闲链表。

主要区别

（1）管理方式：栈由操作系统自动管理，堆需要程序员手动控制，容易产生内存泄漏

（2）空间大小：栈远小于堆。64位 Windows 默认栈大小 1MB，64位 Linux 默认 10MB；堆大小理论上等于虚拟内存大小

（3）生长方向：堆向上（地址由低到高），栈向下（地址由高到低）

（4）分配方式：堆都是动态分配；栈有静态分配（局部变量）和动态分配（alloca 函数），动态分配也由操作系统自动释放

（5）分配效率：栈有专门的寄存器和指令支持，效率高；堆通过库函数或运算符实现，机制复杂，效率低，频繁申请易产生内存碎片

（6）存放内容：栈存放函数返回地址、参数、局部变量、寄存器内容等（静态变量存放在数据段或 BSS 段）；堆的内容由程序员填充，堆顶用一个字节存放堆大小

栈（Stack）

栈是一种运算受限的线性表，只允许在表的一端（栈顶）进行插入和删除操作，具有”先进后出”（FILO）特性。

基本操作包括：

栈分为顺序栈（数组实现，元素地址连续）和链式栈（链表实现，元素地址不连续）。

堆（Heap）

堆是一种特殊的完全二叉树，满足堆序性：所有节点的值总是不大于或不小于其父节点的值。根节点是最大值的称为大顶堆（大根堆），根节点是最小值的称为小顶堆（小根堆）。

堆通常用数组存储，对于节点 i：