堆与栈的区别
理解程序内存管理和数据结构中的堆与栈概念
问题
堆与栈有什么区别？
解答
堆（Heap）与栈（Stack）在不同场景下有不同含义：程序内存布局中表示两种内存管理方式，数据结构中表示两种常用的数据结构。
程序内存中的堆与栈
栈（Stack）
栈由操作系统自动分配和释放，用于存放函数的参数值、局部变量等。栈的内存地址由高到低生长，后定义的变量地址低于先定义的变量。相邻变量的地址之间不会存在其它变量。栈中数据的生命周期随函数执行完成而结束。
堆（Heap）
堆由开发人员分配和释放，若不释放则程序结束时由操作系统回收。堆的内存地址由低到高生长，但后申请的内存不一定在先申请的内存后面，因为会复用已释放的内存空间。堆中数据若未释放，生命周期等同于程序生命周期。
堆的分配过程：操作系统维护一个记录空闲内存地址的链表，收到申请时遍历链表，找到第一个空间足够的节点分配给程序，并在内存首地址记录分配大小，多余部分放回空闲链表。
主要区别
（1）管理方式：栈由操作系统自动管理，堆需要程序员手动控制，容易产生内存泄漏
（2）空间大小：栈远小于堆。64位 Windows 默认栈大小 1MB，64位 Linux 默认 10MB；堆大小理论上等于虚拟内存大小
（3）生长方向：堆向上（地址由低到高），栈向下（地址由高到低）
（4）分配方式：堆都是动态分配；栈有静态分配（局部变量）和动态分配（alloca 函数），动态分配也由操作系统自动释放
（5）分配效率：栈有专门的寄存器和指令支持，效率高；堆通过库函数或运算符实现，机制复杂，效率低，频繁申请易产生内存碎片
（6）存放内容：栈存放函数返回地址、参数、局部变量、寄存器内容等（静态变量存放在数据段或 BSS 段）；堆的内容由程序员填充，堆顶用一个字节存放堆大小
数据结构中的堆与栈
栈（Stack）
栈是一种运算受限的线性表，只允许在表的一端（栈顶）进行插入和删除操作，具有”先进后出”（FILO）特性。
基本操作包括：
- Push（入栈/压栈）：在栈顶添加新元素
- Pop（出栈/退栈）：删除栈顶元素
栈分为顺序栈（数组实现，元素地址连续）和链式栈（链表实现，元素地址不连续）。
堆（Heap）
堆是一种特殊的完全二叉树，满足堆序性：所有节点的值总是不大于或不小于其父节点的值。根节点是最大值的称为大顶堆（大根堆），根节点是最小值的称为小顶堆（小根堆）。
堆通常用数组存储，对于节点 i：
- 父节点下标：
(i - 1) / 2 - 左子节点下标：
2 * i + 1 - 右子节点下标：
2 * i + 2
关键点
- 内存管理中，栈由操作系统自动管理效率高，堆需手动管理灵活但易出错
- 栈空间小且地址向下生长，堆空间大且地址向上生长
- 数据结构中，栈是先进后出的线性表，堆是满足堆序性的完全二叉树
- 栈适合函数调用和临时变量，堆适合动态分配大内存
- 使用时都要防止越界访问，避免程序崩溃或产生不确定行为
目录