堆、栈、栈区、堆区四者在数据结构和虚拟内存模型中的区别 【前言】四者在我看来可以分成两部分介绍。数据结构里面的堆、栈，内存模型里的堆区、栈区。 一、二者区别 1、首先，栈和堆是数据结构里面的叫法，栈：先进后出，堆：优先队列可采用二叉树实现； ps：什么是数据结构？数据结构没有统一的定义，维基百科：存储与组织数据的方式。我感觉更应强调数据的组织方式，比如好多数据结构的存储方式都是用的数组，他们自己封装了接口，例如栈只允许在数组的一端进行操作或者使用单链表。总结一句话存储方式只有顺序存储和链式存储，但是数据组织结构就能区分不同的数据结构了。 2、内存模型里面的栈区和堆区和数据结构没有关系，底层也不是讲用了数据结构里面的堆栈的存储方式。但是类似，栈区（stack） 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈，其可以由一个数组实现。堆区（heap）一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表，具体是怎么管理堆区分配的可以参考。 另一个角度，在堆区分配空间的malloc，可以参考malloc分配空间原理来看一下堆区的结构。 转发注明原网址：https://www.cnblogs.com/huangfuyuan/p/9150362.html 二、内存模型中的堆区和栈区 这是一个围绕：What and where are the stack and heap?的提问，网址：https://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap 我结合他的回答，总结补充一下。 1、栈区。 因为栈主要是为一个线程配备（栈是线程独享的）为这个线程的函数调用服务的。用于存放返回地址，参数，临时变量而用，记录多层调用，是一个有明确的“后入先出”规则的内存 buffer。而且是供程序员“隐式”的使用，分配和回收都是“自动”的，程序员对栈内存的使用缺少自由和可控性，栈这部分内存由专用的寄存器和指令来负责维护。其特点是栈的“复用率”很高，是连续的，且有 IN – OUT 次序的（对 ESP 的维护非常严格严谨，这个工作是编译器来负责，通常也不需要程序员去干预。计算机会在底层对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。 栈上对象的特点是尺寸小而且生命周期很短，潜规则是不要创建尺寸极大的临时对象，调用深度也不希望过深。所以如果栈太大，则对内存使用的性价比会降低（栈的顶部方向的那部分属于栈所有但位于栈外的那部分内存是几乎不会被使用到的，距离栈顶越远的栈外内存的被使用的概率越低，距离栈底越近的内存则使用率越高，热点集中在靠近栈底的部分，而远端方向则是空白的，就好像地铁车厢的高度，不会因为一个姚明这样的存在就把它设计的很高，那样就属于浪费），而且也会减少可以同时创建的进程的数量。 栈只能进行push和pop两种操作，无论是排序，寻址，还是修改，删除，插入都很难，时间代价太高了。所以其实不是不能将栈变得很大，而是因为一旦变得很大，它在这个场景下就不是一个合理的数据结构了，应该选择其他的数据结构来解决。 2、堆区。 而堆内存的使用特点是不连续和无序的，分配和释放成本较高堆则是C/C++函数库提供的，它的机制是很复杂的，例如为了分配一块内存，库函数会按照一定的算法（具体的算法可以参考数据结构/操作系统）在堆内存中搜索可用的足够大小的空间，如果没有足够大小的空间（可能是由于内存碎片太多），就有可能调用系统功能去增加程序数据段的内存空间，这样就有机会分到足够大小的内存，然后进行返回。显然，堆的效率比栈要低得多。 ， 3、因此，栈和堆的设计体现了“分工”原则。栈的主要作用的为函数调用服务，并承担了生命周期很短和（编译器）“自动”维护，尺寸很小的临时对象的存储责任。堆则负责存储生命周期由程序员自主维护，以及尺寸极大的（例如明显超过栈的尺寸）对象/数据。 4、栈区和堆区的大小 栈区的大小在进程分配时是确定的，具体大小看编译器，操作系统。所需大小一般小于10M！太大没有意义，不符合栈是用来快速存取的目标！ 堆区是动态分配的，堆的数据结构相对较慢！因为会手动进行分配，会大一些。是自底向上分配，从低地址往高地址分配，大小不固定。栈相反。 5、哪个快 ？ 至于堆区和栈区哪个更快，从两方面来考虑： （1）分配和释放，堆在分配和释放时都要调用函数（MALLOC,FREE)，比如分配时会到堆空间去寻找足够大小的空间（因为多次分配释放后会造成空洞），这些都会花费一定的时间，具体可以看看MALLOC和FREE的源代码，他们做了很多额外的工作，而栈却不需要这些，由于栈先进后出的特性存取非常快，实际上也不是什么分配,只是从栈顶向上用就行,就好像工厂中的传送带(conveyorbelt)一样,StackPointer会自动指引你到放东西的位置,你所要做的只是把东西放下来就行.退出函数的时候，修改栈指针就可以把栈中的内容销毁.这样的模式速度最快。 PS:我现在实习的一家量化交易公司，他们就绝不会允许使用malloc在堆区操作，因为堆的分配是离散的，对于他们高频连续的数据存取不是很方便。具体好像是内核旁路技术（搭配网卡）加上多线程（4线程）共享栈内存。什么同步不同步，有时间再继续填坑！ （2）访问时间，访问堆的一个具体单，需要两次访问内存，第一次得取得指针，第二次才是真正得数据，而栈只需访问一次。另外，堆的内容被操作系统交换到外存的概率比栈大，栈一般是不会被交换出去的。 三、数据结构里面的堆 1、感觉数据结构的堆还是一个挺神秘的数据结构。优先队列，体现在一般只有两个操作：insert(插入)和findmin(出队最小值)，也有最大堆。 2、实现这两种操作的方法有：链表：排序的链表和不排序每次遍历； 二叉树：最常用，堆基本上叫二叉堆了！！ 3、二叉堆的介绍： 二叉堆是一个完全二叉树：只有最下面一层不是满二叉树，且优先排在左侧。2^h到2^(h+1)-1个节点，时间复杂度log(n)。 性质1：我们想最快找到min，则最小值应该在根节点，任意子树也是堆，所以任意父节点小于其子节点； 性质2：insert插入时，第一步插在紧接着左侧的根节点，不满足性质1，则和父节点交换。直至满足。称为：上滤； 性质3：findmin,找到最小值简单，删除比较麻烦。首先根节点删除会后有一个空穴，我们定位到二叉树最后一个节点；在最后一个节点所在的分支里面，逐步“下滤”，最小值上移；最后将最后一个节点填入下滤后子节点留下的空穴；（数据结构与算法138页） 4、堆的应用 堆排序：对于数据，我们先建立一个最大（小）堆，时间为n（就是insert的平均时间，业内证明最坏是log(n),平均是1.607次即o(1)，进行n次即为o(n)），然后进行n次 的删除。不过在删除前，我们新建一个数组，将最大值依次插进去。最后返回次数组，就是最大顺序排好的序列。n个素总的删除时间为n*log(n)。则总的时间复杂度n+n*log（n），即nlog(n)。 堆排序需要附加数组，存储增加一倍！好的方法是将刚刚删除的最大值，放到最后一个素的位置上，最后会输出一个按最小值排序的数组，无需分配额外空间！ （二叉树可以顺序也可以链式，完全二叉树用顺序的数组存储是最好的，所以二叉堆是数组存储的：https://www.cnblogs.com/yw-ah/p/5872516.html）
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/61212.html
