C++中栈和堆的区别
发布网友
发布时间：2022-04-22 08:10
共1个回答
热心网友
时间：2022-06-18 09:38
内存分配中的堆和栈
在 C 语言中，内存分配方式不外乎有如下三种形式：
从静态存储区域分配：它是由编译器自动分配和释放的，即内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在，直到整个程序运行结束时才被释放，如全局变量与 static 变量。
在栈上分配：它同样也是由编译器自动分配和释放的，即在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元将被自动释放。需要注意的是，栈内存分配运算内置于处理器的指令集中，它的运行效率一般很高，但是分配的内存容量有限。
从堆上分配：也被称为动态内存分配，它是由程序员手动完成申请和释放的。即程序在运行的时候由程序员使用内存分配函数（如 malloc 函数）来申请任意多少的内存，使用完之后再由程序员自己负责使用内存释放函数（如 free 函数）来释放内存。也就是说，动态内存的整个生存期是由程序员自己决定的，使用非常灵活。需要注意的是，如果在堆上分配了内存空间，就必须及时释放它，否则将会导致运行的程序出现内存泄漏等错误。
数据结构的堆和栈
在数据结构中，栈是一种可以实现“先进后出”（或者称为“后进先出”）的存储结构。假设给定栈 S=（a0，a1，…，an-1），则称 a0 为栈底，an-1 为栈顶。进栈则按照 a0，a1，…，an-1 的顺序进行进栈；而出栈的顺序则需要反过来，按照“后存放的先取，先存放的后取”的原则进行，则 an-1 先退出栈，然后 an-2 才能够退出，最后再退出 a0。
在实际编程中，可以通过两种方式来实现：使用数组的形式来实现栈，这种栈也称为静态栈；使用链表的形式来实现栈，这种栈也称为动态栈。
相对于栈的“先进后出”特性，堆则是一种经过排序的树形数据结构，常用来实现优先队列等。假设有一个集合 K={k0，k1，…，kn-1}，把它的所有元素按完全二叉树的顺序存放在一个数组中，并且满足：
则称这个集合 K 为最小堆（或者最大堆）。
由此可见，堆是一种特殊的完全二叉树。其中，节点是从左到右填满的，并且最后一层的树叶都在最左边（即如果一个节点没有左儿子，那么它一定没有右儿子）；每个节点的值都小于（或者都大于）其子节点的值。
