欢迎各位兄弟 发布技术文章

这里的技术是共享的

You are here

堆和栈的区别有哪些? 有大用

堆与栈的区别有:

1、栈由系统自动分配,而堆是人为申请开辟;

2、栈获得的空间较小,而堆获得的空间较大;

3、栈由系统自动分配,速度较快,而堆一般速度比较慢;

4、栈是连续的空间,而堆是不连续的空间。


堆和栈的区别

堆和栈的区别主要有五大点,分别是:

1、申请方式的不同。栈由系统自动分配,而堆是人为申请开辟;

2、申请大小的不同。栈获得的空间较小,而堆获得的空间较大;

3、申请效率的不同。栈由系统自动分配,速度较快,而堆一般速度比较慢;

4、存储内容的不同。栈在函数调用时,函数调用语句的下一条可执行语句的地址第一个进栈,然后函数的各个参数进栈,其中静态变量是不入栈的。而堆一般是在头部用一个字节存放堆的大小,堆中的具体内容是人为安排;

5、底层不同。栈是连续的空间,而堆是不连续的空间。

以上就是堆和栈的区别有哪些?的详细内容,更多请关注php中文网其它相关文章!


来自 https://www.php.cn/faq/416802.html


堆和栈的区别是啥?

 我来答  举报
像它 
高粉答主

2019-04-09 · 说的都是干货,快来关注

1、堆栈空间分配

栈(操作系统):由操作系统自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。

堆(操作系统): 一般由程序员分配释放, 若程序员不释放,程序结束时可能由OS回收,分配方式倒是类似于链表。

2、堆栈缓存方式

栈使用的是一级缓存, 他们通常都是被调用时处于存储空间中,调用完毕立即释放。

堆则是存放在二级缓存中,生命周期由虚拟机的垃圾回收算法来决定(并不是一旦成为孤儿对象就能被回收)。所以调用这些对象的速度要相对来得低一些。

3、效率比较

栈由系统自动分配,速度较快。但程序员是无法控制的。

堆是由new分配的内存,一般速度比较慢,而且容易产生内存碎片,不过用起来最方便。

4、存储内容

栈: 在函数调用时,在大多数的C编译器中,参数是由右往左入栈的,然后是函数中的局部变量。注意静态变量是不入栈的。

当本次函数调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向函数的返回地址,也就是主函数中的下一条指令的地址,程序由该点继续运行。

堆:一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容由程序员安排。


image.png



简介

单片机应用中,堆栈是个特殊存储区,堆栈属于RAM空间的一部分,堆栈用于函数调用、中断切换时保存和恢复现场数据。

堆栈中的物体具有一个特性:第一个放入堆栈中的物体总是被最后拿出来, 这个特性通常称为先进后出 (FILO—First-In/Last-Out)。 堆栈中定义了一些操作, 两个最重要的是PUSH和POP。 PUSH(入栈)操作:堆栈指针(SP)加1,然后在堆栈的顶部加入一 个元素。

POP(出栈)操作相反,出栈则先将SP所指示的内部ram单元中内容送入直接地址寻址的单元中(目的位置),然后再将堆栈指针(SP)减1.。这两种操作实现了数据项的插入和删除


来自 https://zhidao.baidu.com/question/36918441.html



什么是堆?什么是栈?他们之间有什么区别和联系?

请大家分别解释下操作系统和数据结构中的“堆”和“栈”概念。为什么操作系统和数据结构中会出现译名相同的概念,他们之间有什么联系吗?不会是因为最初翻译的时候不小心重复了吧?

关注者
375
被浏览
146,240

25 个回答

分享牛客大佬许嵩不爱吃土豆鸭的一篇【面试八股文】常见问题之 堆栈区别

回答这个问题前得考虑下面试官为什么会问这种基本问题?

在我看来其实涉及的内容知识点蛮多的,比如C/C++的内存分配,数据结构中的堆、栈,回答问题前,考虑下从哪个角度具体说,从而引导面试官向自己熟悉的内容提问 ,表现自己。

1.从C/C++的内存分配(与操作系统相关)上来说,堆(heap),栈(stack)属于内存空间的一段区域。

如图:

下面这幅图倒过来看,,,,栈放在最下面 ,可能理解更容易点 



一个程序在内存上由BSS段、data段、text段三个组成的。在没有调入内存前,可执行程序分为代码段、数据区和未初始化数据区三部分。

BSS段:(Block Started by Symbol)通常是指用来存放程序中未初始化的全局变量的一块内存区域,属于静态内存分配。BSS段的内容并不存放在磁盘上的程序文件中。原因是内核在程序开始运行前将它们设置为0,需要存放在程序文件中的只有正文段和初始化数据段。text段和data段在编译时已经分配了空间,而BSS段并不占用可执行文件的大小,它是由链接器来获取内存的。

数据段:(data segment)通常是指用来存放程序中已初始化的全局变量的一块内存区域,属于静态内存分配。总结为:初始化的全局变量和静态变量在已初始化区域,未初始化的全局变量和静态变量在BSS区。

代码段:(code segment/text segment)通常是指用来存放程序执行代码的一块内存区域。该区域的大小在程序运行前就已经确定,并且内存区域通常属于只读, 某些架构也允许代码段为可写,即允许修改程序。在代码段中,也有可能包含一些只读的常数变量,例如字符串常量等。

堆(heap):用于动态分配内存,位于BSS和栈中间的地址区域,由程序员申请分配和释放。堆是从低地址位向高地址位增长,采用链式存储结构。频繁的malloc/free造成内存空间的不连续,会产生碎片。(经常问如何解决内存碎片?)当申请堆空间时库函数是按照一定的算法搜索可用的足够大的空间,因此堆的效率比栈要低的多。注:与数据结构中的堆不是一个概念,但堆的分配方式类似于链表。

栈(stack): 由编译器自动释放,存放函数的参数值、局部变量等。每当一个函数被调用时,该函数的返回类型和一些调用的信息被存放到栈中,这个被调用的函数再为它的自动变量和临时变量在栈上分配空间。每调用一个函数一个新的栈就会被使用。栈区是从高地址位向低地址位增长的,是一块连续的内存区域,最大容量是由系统预先定义好的,申请的栈空间超过这个界限时会提示溢出。

实例程序:

2.区别:

1)管理方式栈由编译器自动管理,无需人为控制。而堆释放工作由程序员控制,容易产生内存泄漏(memory leak)。

2)空间大小在32位系统下,堆内存可以达到4G的空间(虚拟内存的大小,有面试官问过),从这个角度来看堆内存大小可以很大。但对于栈来说,一般都是有一定的空间大小的(在VC6默认的栈空间大小是1M,也有默认2M的)。可以重新设置,如图:

3)碎片问题堆频繁new/delete会造成内存空间的不连续,造成大量的碎片,使程序效率降低(重点是如何解决?如内存池、伙伴系统等)。对栈来说不会存在这个问题,因为栈是先进后出,不可能有一个内存块从栈中间弹出。在该块弹出之前,在它上面的(后进的栈内容)已经被弹出。

4)生长方向堆生长(扩展)方向是向上的,也就是向着内存地址增加的方向;栈生长(扩展)方向是向下的,是向着内存地址减小的方向增长, 可以看第一张图。

5)分配方式堆都是动态分配的,没有静态分配的堆。而栈有2种分配方式:静态分配和动态分配。静态分配是编译器完成的,如局部变量分配。动态分配由alloca函数进行分配,但是栈的动态分配和堆是不同的,它的动态分配是由编译器进行释放,无需我们手工实现。

6)效率栈是机器系统提供的数据结构,计算机会在底层对栈提供支持(有专门的寄存器存放栈的地址,压栈出栈都有专门的机器指令执行),这就决定了栈的效率比较高。堆则是C/C++函数库提供的,它的机制是很复杂的(可以了解侯捷老师的内存管理的视频,关于malloc/realloc/free函数等)。例如分配一块内存,堆会按照一定的算法,在堆内存中搜索可用的足够大小的空间,如果没有(可能是由于内存碎片太多),就有可能调用系统功能去增加程序数据段的内存空间,这样就有机会分到足够大小的内存,然后进行返回。总之,堆的效率比栈要低得多。

以上,希望对面试有些帮助,菜鸡 写的难免有些不足,望大佬多多包涵~


【面试八股文】常见问题之 堆栈区别www.nowcoder.com图标

如果觉得有用,就给牛妹点个赞吧~ღ( ´・ᴗ・` )比心

继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续

个人感觉这里的堆 应该指的是heap而非数据结构中的堆。
栈区(stack)— 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。
堆区(heap) — 一般由程序员分配释放, 若程序员不释放,程序结束时可能由OS回收 。

区别和联系:
1.申请方式
堆是由程序员自己申请并指明大小,在c中malloc函数 如p1 = (char *)malloc(10);
栈由系统自动分配,如声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间
2.申请后系统的响应
栈:只要栈的剩余空间大于所申请空间,系统将为程序提供内存,否则将报异常提示栈溢出。
堆:首先应该知道操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时,会 遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序,另外,对于大多数系统,会在这块内 存空间中的首地址处记录本次分配的大小,这样,代码中的delete语句才能正确的释放本内存空间。另外,由于找到的堆结点的大小不一定正好等于申请的大 小,系统会自动的将多余的那部分重新放入空闲链表中。
3.申请大小的限制
栈:在Windows下,栈是向低地址扩展的数据结 构,是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的,在WINDOWS下,栈的大小是2M(也有的说是1M,总之是 一个编译时就确定的常数),如果申请的空间超过栈的剩余空间时,将提示overflow。因此,能从栈获得的空间较小。
堆:堆是向高地址扩展的数据结构,是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的,自然是不连续的,而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见,堆获得的空间比较灵活,也比较大。
4.申请效率的比较:
栈由系统自动分配,速度较快。但程序员是无法控制的。
堆是由new分配的内存,一般速度比较慢,而且容易产生内存碎片,不过用起来最方便.

体会:
使用栈就象我们去饭馆里吃饭,只管点菜(发出申请)、付钱、和吃(使用),吃饱了就走,不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作,他的好处是快捷,但是自由度小。
使用堆就象是自己动手做喜欢吃的菜肴,比较麻烦,但是比较符合自己的口味,而且自由度大。
继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续

首先堆(heap)和栈(stack)两个重名不是翻译问题,而是英文原文就是一样的。


数据结构中堆是满足父子节点大小(比如大根堆中规定父节点的值要比子节点大)关系的一种完全二叉树。由于是完全二叉树,可以用数组来实现,用节点编号来访问和操作节点,简化程序,提升效率。而其大小关系则为我们查询堆中极值提供了常数级别的时间复杂度,又由二叉树的性质,插入和删除则为对数级别时间复杂度。这就好像地位不同的人在排队,排在最前面的一定是地位最高的人,所以堆是优先队列(Priority Queue)实现的基础。利用这一特性,可以加速某些需要频繁取队列中极值的算法比如 A* 算法等。


数据结构中的栈则是一种相当简单的结构。就像是只有一个口的深深的文件桶,先进去的文件会被压在下面(push),而且我们每次只能取到最上面的文件(pop),体现了其先进后出(FILO)的特性。虽然栈操作简单,但也有如单调栈等在栈内保持一定数据特性的变种。


操作系统中的堆和栈都是指内存空间,不同的是堆为按需申请、动态分配,例如 C 中的 malloc 函数和 C++ 中的 new 操作(当然 C++ 的 new 不仅仅是申请内存这么简单)。内存中的空闲空间并不是连续的,而是不同程序占用了不同的一块一块的内存,即使是同一个程序也可能占用了不同地方的多块内存。操作系统中则会对这些空间进行统一的管理,在应用程序提出申请时,就会从堆中按照一定算法找出一块可用内存,标记占用空间等信息之后返回其起始地址给程序。在程序结束之前,操作系统不会删除已经申请的内存,而是要靠程序主动提出释放的请求(free、delete),如果使用后忘记释放,就会造成所谓的内存泄漏问题。因此堆基本上可以理解为当前可以使用的空闲内存,但是其申请和释放都要程序员自己写代码管理。


而操作系统的栈则是程序运行时自动拥有的一小块内存,大小在编译期时由编译器参数决定,用于局部变量的存放或者函数调用栈的保存。在 C 中如果声明一个局部变量(例如 int a),它存放的地方就在栈中,而当这个局部变量离开其作用域之后,所占用的内存则会被自动释放,因此在 C 中局部变量也叫自动变量。栈的另一个作用则是保存函数调用栈,这时和数据结构的栈就有关系了。在函数调用过程中,常常会多层甚至递归调用。每一个函数调用都有各自的局部变量值和返回值,每一次函数调用其实是先将当前函数的状态压栈,然后在栈顶开辟新空间用于保存新的函数状态,接下来才是函数执行。当函数执行完毕之后,栈先进后出的特性使得后调用的函数先返回,这样可以保证返回值的有序传递,也保证函数现场可以按顺序恢复。操作系统的栈在内存中高地址向低地址增长,也即低地址为栈顶,高地址为栈底。这就导致了栈的空间有限制,一旦局部变量申请过多(例如开个超大数组),或者函数调用太深(例如递归太多次),那么就会导致栈溢出(Stack Overflow),操作系统这时候就会直接把你的程序杀掉。

继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续
03 栈的概念_
1667 播放 · 4 赞同
发布于 05-30· 1165 次播放
继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续
由两个栈组成的队列
966 播放
介绍了堆跟栈分别的区别,以及如何使用两个栈变成拥有队列的特点
发布于 06-10· 184 次播放
继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续

我自己也是傻傻分不清,所以必须想一些歪门邪道老帮助我的记忆.

比较形象的比较是通过有道词典的这两张图来做比较,然后展开联想.

区别一(who):

1.堆:图片为土堆,一堆土.堆上面的是程序员负责分配和负责释放的.而程序员又称作码农,农民不就是挖土的吗,活该不能智能的处理,只能农民(码农)手动处理.

2.栈:图片为书,读书人,有知识有文化,什么都是自动的,高科技.所以栈是不用我们关心的,是操作系统自己去申请和释放的.另一种记忆方法:栈是什么?客栈的栈,供旅客住宿的地方。计算机领域指数据暂时存储的地方,所以才有进栈、出栈的说法。你去客栈还需要自己打扫吗?不需要,所以对旅客来说不用自己去开辟,不用自己去申请和释放。只要给钱就行了。

区别二(where):

1.堆:因为是土堆,农业相关的词汇,农业就感觉比较传统,没有那么智能化,所以分配的时候会去查找合适的空间.另外,我们可以想象这样一个场景:在悬崖边的栈道(形似链表)上面放一堆土堆,那肯定是会全部漏下去的, 但是计算机相反,计算机内部偏偏不信邪,就要这么搞, 所以这里联想到栈道来分配堆的.即:堆的分配会在栈道(链表)上去找,找到能放下堆的容量的内存块的时候就分配给你.

2.栈:栈人家是书,是很智能化的,所以操作系统会直接给你了.

区别三(how):

1.堆:图片是土堆,所以只能够从地上网上堆,不可能相反,那样的土堆除非有502.所以是从下往上分配地址的.

2.栈:图为书,我们可以想像成一个未来的图书馆,图书馆都是把书放在天花板上面,从上往下放,而且不会掉下来.所以栈的分配是自顶向下的,而且肯定有空间限制.所以如果栈上空间不足了就overflow了.


区别四(result):

1.堆:图片是土堆,农业相关,所以什么都比较慢,所以分配就比较慢了,而且到处都是小土堆,这就是碎片.

2.栈:图片是书,高科技的,当然分配就很快,至少比堆块.而且不会有碎片,人家是高科技嘛.

继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续
什么是栈,栈的原理和应用
1.9 万播放 · 39 赞同
这个视频用一个动画告诉你什么是栈?看懂了就不会忘记,刻在你的DNA里,不用每次都去搜索复习了
发布于 07-14· 1.8 万次播放
继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续

这个问题, 长篇大论可以讲很多,深入探讨的话可以探讨出很多问题,感兴趣的,可以读读SICP这本书 Welcome to the SICP Web Site


我简单列个矩阵,但只包含新手最关心,也是前期必须要理解的几个方面,当然,也是脱离特定语言的。



继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续

我也产生过同样疑问,我猜测数据结构的堆和栈与操作系统说的堆和栈应该是有联系的,但是至今没有去查历史资料印证这个猜测。

关于栈就不多说了,我猜测先有了数据结构的“堆”,也许早期很原始,当时也许就是为了管理内存块用的,所以,可以合理推测当时是在数据结构“堆”的指导下实现了操作系统的堆。

我们把“堆”这个概念限制到关于malloc相关的范围,那么,在学习计算机系统课的时候,书上很明确说了历史上出现过多种堆的实现,即使当前,不同操作系统的堆也是不一样的。而且,为了特定目的可以实现自己需要的堆,在特定场景下更加有效的malloc,比如,用Priority Queue管理一堆预先划分好的确定大小的内存块。而且在linux操作系统上,运行某些系统命令都可以加载自己做的一套malloc相关的管理函数。

那么,我们可以推想一下,以前一定有人用数据结构的堆实现了一个操作系统的堆,数据结构讲的堆会很有效。分配内存的时候,要尽量快地找到一个刚好合适的块;释放内存以后,有些具体实现要完成碎片的合并,那么导致产生一块更大的块。这些用数据结构的堆来管理都很有效,可以实现快速的调整顺序和快速的按照大小查找。

继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续
继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续

在数据结构中经常有人说堆栈,堆栈之间有什么区别了?这些数据结构在算法思想中有哪些良好的运用了?

首先我们平常端盘子,都是知道盘子一般都是一个个堆叠起来的,而我们把盘子比作数据,而堆起来的盘子就很像栈这种数据结构



先进后出的这种结构,就是栈的数据结构,我们存数据时先存a,b,c,d,e 之后取e,d,c,b,a。

同样的堆也是一类特殊的数据结构,和栈有所不同的是,堆的内存是由所在语言系统环境管理的(比如python虚拟机)而栈申请内存时是由系统自动分配的,而且系统分配也是大小限制的,超过这个大小后就会内存溢出报错,类似如下定义的字符溢出。



堆内存是一般是由语言运行环境分配管理,如Python虚拟机控制内存和运行环境:



所以内存上可以组合关联起来,这样就不容易受系统限制



堆在数据存取上和栈有所不同,栈是先进后出,而堆是一种优先的队列(并不是队列,堆通常是一个可以被看做一棵树的数组对象。),所谓优先队列是按照元素的优先级取出元素。举个例子,一般在饭桌上,无论你是先来后到,应该先是爷爷奶奶辈先动筷子,后面是父母,之后是你,像这种:



有这样的优先级享受的,其严格的逻辑数据结构定义如下:



有了这定义我们来尝试一下用堆这种数据结构做一种排序叫堆排序,我们先得到需要排序的一组元素:

16,7,3,20,17,8

先构建一颗树:



按照堆数据结构的定义,即任何一非叶节点的数据不大于或者不小于其左右孩子节点的数据

,调整如下:









直到调整如上,就表示最大的在最上面,下面每个子节点都比父节点小,堆就完成了初始化。现在要对堆进行排序(注意),我们希望从左到右,按照从小到大的顺序排列,依照堆的性质,我们可以这样排:

首先我们将最大的和最后一个位置进行交换



除了红色标记的元素,其他数据按照堆的性质从新排列好。



继续将除红色标记外的最大元素移到最后面

















一直到只剩根节点时,这个时候排序就已经排好了,以上就是利用数据结构堆做的排序算法。我们用Python代码实现如下:

def heap_sort(lst):

def sift_down(start, end):

"""最大堆调整"""

root = start

while True:

child = 2 * root + 1

if child > end:

break

if child + 1 <= end and lst[child] < lst[child + 1]:

child += 1

if lst[root] < lst[child]:

lst[root], lst[child] = lst[child], lst[root]

root = child

else:

break

# 创建最大堆

for start in range((len(lst) - 2) // 2, -1, -1):

sift_down(start, len(lst) - 1)

# 堆排序

for end in range(len(lst) - 1, 0, -1):

lst[0], lst[end] = lst[end], lst[0]

sift_down(0, end - 1)

return lst

if __name__ == "__main__":

list = [16,7,3,20,17,8]

heap_sort(list)

print(list)

运行结果:



计算复杂度后我们发现堆排序也是比较优秀的一种排序,那栈了,其实这里突然想起一件事,就是学维特比算法时有个马尔科夫链,其中就包含了回溯算法,网上搜索发现栈这种数据结构正好对应这种算法思想,我们写个实际的例子来看看,首先我们看看,什么是回溯了,我举个例子。

如下图,现在有一只小蚂蚁P要在迷宫中找食物T,找的方式如下,我们把每个岔路口当成一个节点,记录下来,假设蚂蚁从节点1出发,沿着2、3、4都是死路,于是返回节点1,这个返回的过程就是回溯,当到达节点5时,往上碰壁返回来(回溯),左右碰壁回来(回溯),只有往下才找到食物,这个过程就是回溯算法体现。



为了方便代码实现,我们用1表示墙,0表示可以走的地方,666表示食物,矩阵表示整个迷宫:



想法和思路是这样:

1、将小蚂蚁走过的分岔路口记录下来

2、将小蚂蚁走过的路径记录记录下来(用栈这种数据结构)

3、当小蚂蚁发现这条路不通时,或者遇到相同的岔路口时,延原路返回(路径数据取出栈的数据)当回到岔路口时,将岔路口那个方向路不通的数据标记,延没有标记的方向继续前进(如果都标记了,继续延原路返回),直到找到食物。

具体的实现代码我就不贴出来了,这就是栈这种数据结构在回溯算法上的应用。

哈哈哈,折腾了一天希望有大佬能指出错误,共同进步。

参考书籍:

算法导论原书第三版

Python数据结构

原文来自:

数据结构-堆栈www.zxheyi.cn图标


继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续

首先说明这里的堆和栈不等同于数据结构中堆和栈的概念。这里的堆和栈都是内存中的一部分,有着不同的作用,而且一个程序需要在这片区域上分配内存。

栈内存(stack)

栈是用来存储函数内部(包括main函数)的局部变量和方法调用和函数参数值,是由系统自动分配的,一般速度较快;存储地址是连续且存在有限栈容量,会出现溢出现象。

堆内存(heap)

堆是由corder手动分配释放的,通过malloc和new等动态申请内存的语句使用,也需要用户手动回收(或可能在程序结束时OS自动回收),而对于面向对象程序来说,new出来的任何对象,无论是对象内部的成员变量,局部变量,类变量,他们指向的对象都存储在堆内存中(但指针本身存在栈中),一般速度较栈慢;存储地址通常是链式的,内存较大不会溢出。


个人的理解,有错希望大牛指出,谢谢。

继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续
就存储位置而言,在C/C++中,函数内部声明的局部变量以及形参,是存储在栈中的,由操作系统在调用函数时自动分配并在函数结束时回收。
对于全局变量以及静态变量,存储在全局数据区。
而通过alloc或new来动态分配的内存存储在堆中,堆的数量大,但是分配速度比栈慢,需要程序员自己维护,容易出现内存泄漏和内存碎片。
继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续

搬运一下在博客园看到的两篇文章,基本上可以回答题主的疑问了。

深入理解C语言内存管理 - tuhooo - 博客园www.cnblogs.com图标系统栈的工作原理 - BattleHeart - 博客园www.cnblogs.com图标


继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续

栈的概念常见于三个方面:1.数据结构;2.调用栈Call stack - Wikipedia;3.内存分配Stack-based memory allocation

数据结构中的“堆”和“栈”重点在于数据的存放方式FIFO和LIFO。

调用栈中栈表示程序中的子程序像积木一样层层调用。

操作系统中的“堆”和“栈”指的是基于堆栈的内存分配,

***

他们之间的联系就在于都是基于先进后出的原则以及英文中将Stack,Call stack, Stack-based memory allocation都缩写为Stack。

译名相同是为了和英文中的缩写同步,不是粗心。

继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续
如果论域是数据结构的话:
是满足一定限制的树型结构(比如父亲节点的权值要大于儿子节点的权值,左儿子又要大于右儿子)。
是元素有先进后出顺序的线性结构。可以考虑叠盘子,只能从最上面拿盘子,也只能往最上面放盘子。那这个盘子序列、包括上面两条规则就构成了一个栈。
~~~~~~~~~~~~~~~~~~~~~~
体会:
涉及到用堆的算法的题目,一般题目的结构优美,解答也优美。而且速度快,因为基本操作的复杂度都是O(log N)的。
堆算法本身(特别是二叉堆)是直接将树结构映射到线性表上(用到了满二叉树的性质),也体现出一种结构与结构直接的联系之美吧。
栈嘛,就是函数调用咯。最特别的感觉就是简洁,只注意当下几个状态的组合映射,不去考虑栈的底部有什么。(很漂亮的例子是汉诺塔和欧几里得算最大公约数)
继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续

数据结构

数据结构中的堆与栈比较简单,通常栈指具有先进后出的特殊数据结构,可以基于数组、动态内存或链表实现;而堆一般指一棵树的数组存储形态,通常由数组或树实现。

操作系统

在操作系统中,堆与栈的概念则更为复杂。

栈:计算机内存中的一块特殊区域,用来存储由函数创建的临时变量。一般由编译器自动分配释放,是临时的存储内存,当函数运行结束后,栈中变量内存将被擦除。栈部分主要由方法,局部变量以及引用变量组成。

堆:默认情况下,编程语言将全局变量存储在堆内存空间中,并支持内存的动态分配。堆一般由程序员分配释放,若程序员不释放,程序结束是可能由操作系统回收。堆不会自动管理,CPU对它也不会严格管理,更像是一个自由浮动的内存区域。

从上述描述中可以看出来,操作系统中堆与栈有着截然不同的作用,管理方式也相差很大。其实堆与栈的区别主要可以分为三个方面:数据结构、内存存取和分配释放。


数据结构类型线性分层
大小限制取决于操作系统对内存大小没有限制
是否能调整大小不能
实现方式数组、链表、动态内存等数组、树
存取速度高速存取相对栈较慢
存取权限仅访问局部变量允许全局访问变量
内存管理由操作系统管理,不会产生内存碎片由于内存可以动态分配,会产生内存碎片,空间使用效率不高
分配与释放由编译器指令自动完成程序员手动完成,若程序员不释放,则程序结束时可能会由操作系统回收
分配方式内存在连续块中分配内存以任何随机顺序分配
释放方式不需要取消分配变量需要显式取消分配
开销

由于内存分配是操作系统中的一大重点,因此操作系统中的堆与栈的区别重点在于内存的分配与释放上。

栈的内存分配:发生在连续的内存块中,每当调用一个函数的时候,编译器会去决定要分配的内存大小,接着函数中的变量就会在栈上分配内存。每当函数调用结束时,变量的内存就会被释放。

所有这些都使用编译器中的一些预定义例程进行,程序员不必担心内存分配和栈变量的释放。这种内存分配也称为临时内存分配,因为一旦方法执行完毕,该方法所属的所有数据就会自动从栈中清除。也就是说,只要该方法尚未完成执行且当前处于运行状态,就可以访问存储在栈内存中的任何值。

堆的内存分配:在程序员编写的指令执行期间分配内存。这里的堆与数据结构中的堆不同,之所以称为堆,是因为堆是可供程序员分配和取消分配的一堆内存空间。每当我们实例化一个对象时,它总是在堆空间中创建,并且这些对象的引用信息总是存储在栈存储器中。堆内存分配不如栈内存分配安全,这是因为存储在该空间中的数据可被所有线程访问或看到。如果程序员不能很好地处理此内存,则程序中可能会发生内存泄漏。

JVM中的堆与栈实例

通过一段代码来实际了解栈内存分配与堆内存分配。


class Product {
    int id;
    String name;

    public Product(int id, String name) {
	this.id = id;
	this.name= name;
    }
}

public class Factory {
    private static Product produce(int id, String name) {
	return new Product(id, name);
    }

    public static void main(String[] args) {
	int id = 6;
	String name = "Car";
	Product product = null;
        product = produce(id, name);
    }
}

在分析以上示例后,我们将得出以下结论:

  • 进入main()函数之后,将在虚拟机栈中创建一个内存空间来存储该方法的变量以及引用,其中原始数据类型(int)的值将会直接存储在栈内存空间中,其余的变量会以指针形式存储在栈内存空间中,指针指向堆中的实际对象。这里String类型的name引用将会指向堆中字符串池中的实际字符串的内存地址,product引用会在堆中创建Product类对象,并指向其内存地址。

  • 这里虽然创建了Product对象,但并不会调用Product类的构造函数,因此接着调用静态函数produce,在相同栈内存空间顶部分配空间,再次以上述方式存储变量。

  • 在静态函数produce中,调用Product类的构造函数,因此再将该函数以相同方式压入栈内存空间顶部。

  • 并且,对于新创建的Product类型的对象product,所有实例变量都将存储在堆内存中。


继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续

堆:堆中一般用来存放引用数据类型,索引一般存放在堆中

堆中内存大,所以存放引用数据类型

栈:栈中一般用来存放基本数据类型,栈中遵循一个原则,先进后出(最先进来的最后出去)

为什么是用来存放基本数据类型: 因为栈中 速度快,内存小


继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续

栈其实很好理解。

女生买口红就是一个栈。

最近买的被用的最多。然后过俩月没意思了,之前买的被放入栈底,再买新的放入栈顶。以此类推。

三四年后发现,最早买的一般都没用完。

继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续
堆 先进先出 排队吃饭
栈 先进后出 子弹夹
继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续

前言

其实一开始对栈、堆的概念特别模糊,只知道好像跟内存有关,又好像事件循环也沾一点边。面试薄荷的时候,面试官正好也问到了这个问题,当时只能大方的承认不会。痛定思痛,回去好好的研究一番。 我们将从JS的内存机制以及事件机制大量的 (例子)来了解栈、堆究竟是个什么玩意。概念比较多,不用死读,所有的 心里想一遍,浏览器console看一遍就很清楚了。 let's go

JS内存机制

因为JavaScript具有自动垃圾回收机制,所以对于前端开发来说,内存空间并不是一个经常被提及的概念,很容易被大家忽视。特别是很多不专业的朋友在进入到前端之后,会对内存空间的认知比较模糊。

在JS中,每一个数据都需要一个内存空间。内存空间又被分为两种,栈内存(stack)与堆内存(heap)

栈内存一般储存基础数据类型


Number String Null Undefined Boolean 
 (es6新引入了一种数据类型,Symbol)
复制代码

最简单的


var a = 1 
复制代码

我们定义一个变量a,系统自动分配存储空间。我们可以直接操作保存在栈内存空间的值,因此基础数据类型都是按值访问。

数据在栈内存中的存储与使用方式类似于数据结构中的堆栈数据结构,遵循后进先出的原则。

堆内存一般储存引用数据类型

堆内存的


var b = { xi : 20 }
复制代码

与其他语言不同,JS的引用数据类型,比如数组Array,它们值的大小是不固定的。引用数据类型的值是保存在堆内存中的对象。JavaScript不允许直接访问堆内存中的位置,因此我们不能直接操作对象的堆内存空间。看一下下面的图,加深理解。

比较


var a1 = 0;   // 栈 
var a2 = 'this is string'; // 栈
var a3 = null; // 栈

var b = { m: 20 }; // 变量b存在于栈中,{m: 20} 作为对象存在于堆内存中
var c = [1, 2, 3]; // 变量c存在于栈中,[1, 2, 3] 作为对象存在于堆内存中
复制代码

因此当我们要访问堆内存中的引用数据类型时,实际上我们首先是从栈中获取了该对象的地址引用(或者地址指针),然后再从堆内存中取得我们需要的数据。

测试


var a = 20;
var b = a;
b = 30;
console.log(a)
复制代码
var m = { a: 10, b: 20 }
var n = m;
n.a = 15;
console.log(m.a)
复制代码

同学们自己在console里打一遍,再结合下面的图例,就很好理解了

内存机制我们了解了,又引出一个新的问题,栈里只能存基础数据类型吗,我们经常用的function存在哪里呢?

浏览器的事件机制

一个经常被搬上面试题的


console.log(1)
let promise = new Promise(function(resolve,reject){
    console.log(3)
    resolve(100)
}).then(function(data){
    console.log(100)
})
setTimeout(function(){
    console.log(4);
})
console.log(2)
复制代码
上面这个demo的结果值是 1 3 2 100 4

对象放在heap(堆)里,常见的基础类型和函数放在stack(栈)里,函数执行的时候在栈里执行。栈里函数执行的时候可能会调一些Dom操作,ajax操作和setTimeout定时器,这时候要等stack(栈)里面的所有程序先走**(注意:栈里的代码是先进后出)**,走完后再走WebAPIs,WebAPIs执行后的结果放在callback queue(回调的队列里,注意:队列里的代码先放进去的先执行),也就是当栈里面的程序走完之后,再从任务队列中读取事件,将队列中的事件放到执行栈中依次执行,这个过程是循环不断的。

  • 1.所有同步任务都在主线程上执行,形成一个执行栈

  • 2.主线程之外,还存在一个任务队列。只要异步任务有了运行结果,就在任务队列之中放置一个事件。

  • 3.一旦执行栈中的所有同步任务执行完毕,系统就会读取任务队列,将队列中的事件放到执行栈中依次执行

  • 4.主线程从任务队列中读取事件,这个过程是循环不断的

概念又臭又长,没关系,我们先粗略的扫一眼,接着往下看。

举一个 说明栈的执行方式


var a = "aa";
function one(){
    let a = 1;
    two();
    function two(){
        let b = 2;
        three();
        function three(){
            console.log(b)
        }
    }
}
console.log(a);
one();
复制代码
demo的结果是 aa 2

图解





执行栈里面最先放的是全局作用域(代码执行有一个全局文本的环境),然后再放one, one执行再把two放进来,two执行再把three放进来,一层叠一层。

最先走的肯定是three,因为two要是先销毁了,那three的代码b就拿不到了,所以是先进后出(先进的后出),所以,three最先出,然后是two出,再是one出。

那队列又是怎么一回事呢?

再举一个


console.log(1);
console.log(2);
setTimeout(function(){
    console.log(3);
})
setTimeout(function(){
    console.log(4);
})
console.log(5);
复制代码
首先执行了栈里的代码,1 2 5。 前面说到的settimeout会被放在队列里,当栈执行完了之后,从队列里添加到栈里执行(此时是依次执行),得到 3 4

再再举一个


console.log(1);
console.log(2);

setTimeout(function(){
    console.log(3);
    setTimeout(function(){
        console.log(6);
    })
})
setTimeout(function(){
    console.log(4);
    setTimeout(function(){
        console.log(7);
    })
})
console.log(5)

复制代码
同样,先执行栈里的同步代码 1 2 5. 再同样,最外层的settimeout会放在队列里,当栈里面执行完成以后,放在栈中执行,3 4。 而嵌套的2个settimeout,会放在一个新的队列中,去执行 6 7.

再再再看一个


console.log(1);
console.log(2);

setTimeout(function(){
    console.log(3);
    setTimeout(function(){
        console.log(6);
    })
},400)
setTimeout(function(){
    console.log(4);
    setTimeout(function(){
        console.log(7);
    })
},100)
console.log(5)
复制代码
如上:这里的顺序是1,2,5,4,7,3,6。也就是只要两个set时间不一样的时候 ,就set时间短的先走完,包括set里面的回调函数,再走set时间慢的。(因为只有当时间到了的时候,才会把set放到队列里面去)
setTimeout(function(){
    console.log('setTimeout')
},0)
for(var i = 0;i<10;i++){
    console.log(i)
}
复制代码
这个demo的结果是 0 1 2 3 4 5 6 7 8 9 setTimeout

所以,得出结论,永远都是栈里的代码先行执行,再从队列中依次读事件,加入栈中执行

stack(栈)里面都走完之后,就会依次读取任务队列,将队列中的事件放到执行栈中依次执行,这个时候栈中又出现了事件,这个事件又去调用了WebAPIs里的异步方法,那这些异步方法会在再被调用的时候放在队列里,然后这个主线程(也就是stack)执行完后又将从任务队列中依次读取事件,这个过程是循环不断的。

再回到我们的第一个


console.log(1)
let promise = new Promise(function(resolve,reject){
    console.log(3)
    resolve(100)
}).then(function(data){
    console.log(100)
})
setTimeout(function(){
    console.log(4);
})
console.log(2)
复制代码
上面这个demo的结果值是 1 3 2 100 4
  • 为什么setTimeout要在Promise.then之后执行呢?

  • 为什么new Promise又在console.log(2)之前执行呢?

setTimeout是宏任务,而Promise.then是微任务 这里的new Promise()是同步的,所以是立即执行的。

这就要引入一个新的话题宏任务微任务(面试也会经常提及到)

宏任务和微任务

参考 Tasks, microtasks, queues and schedules(jakearchibald.com/2015/

概念:微任务和宏任务都是属于队列,而不是放在栈中

一个新的


console.log('1');

setTimeout(function() {
  console.log('setTimeout');
}, 0);

Promise.resolve().then(function() {
  console.log('promise1');
}).then(function() {
  console.log('promise2');
});

console.log('2');
复制代码
1 2 promise1 promise2 setTimeout

宏任务(task)

浏览器为了能够使得JS内部宏任务与DOM任务能够有序的执行,会在一个task执行结束后,在下一个 task 执行开始前,对页面进行重新渲染 (task->渲染->task->…) 鼠标点击会触发一个事件回调,需要执行一个宏任务,然后解析HTMl。但是,setTimeout不一样setTimeout的作用是等待给定的时间后为它的回调产生一个新的宏任务。这就是为什么打印‘setTimeout’在‘promise1 , promise2’之后。因为打印‘promise1 , promise2’是第一个宏任务里面的事情,而‘setTimeout’是另一个新的独立的任务里面打印的。

微任务 (Microtasks)

微任务通常来说就是需要在当前 task 执行结束后立即执行的任务 比如对一系列动作做出反馈,或者是需要异步的执行任务而又不需要分配一个新的 task,这样便可以减小一点性能的开销。只要执行栈中没有其他的js代码正在执行且每个宏任务执行完,微任务队列会立即执行。如果在微任务执行期间微任务队列加入了新的微任务,会将新的微任务加入队列尾部,之后也会被执行。微任务包括了mutation observe的回调还有接下来的例子promise的回调

一旦一个pormise有了结果,或者早已有了结果(有了结果是指这个promise到了fulfilled或rejected状态),他就会为它的回调产生一个微任务,这就保证了回调异步的执行即使这个promise早已有了结果。所以对一个已经有了结果的**promise调用.then()**会立即产生一个微任务。这就是为什么‘promise1’,'promise2’会打印在‘script end’之后,因为所有微任务执行的时候,当前执行栈的代码必须已经执行完毕。‘promise1’,'promise2’会打印在‘setTimeout’之前是因为所有微任务总会在下一个宏任务之前全部执行完毕。

还是


<div class="outer">
  <div class="inner"></div>
</div>
复制代码
//  elements
var outer = document.querySelector('.outer');
var inner = document.querySelector('.inner');


//监听element属性变化
new MutationObserver(function() {
  console.log('mutate');
}).observe(outer, {
  attributes: true
});

// click listener…
function onClick() {
  console.log('click');

  setTimeout(function() {
    console.log('timeout');
  }, 0);

  Promise.resolve().then(function() {
    console.log('promise');
  });

  outer.setAttribute('data-random', Math.random());
}

// 
inner.addEventListener('click', onClick);
outer.addEventListener('click', onClick);
复制代码
click promise mutate click promise mutate (2) timeout

很好的解释了,setTimeout会在微任务(Promise.then、MutationObserver.observe)执行完成之后,加入一个新的宏任务中

多看一些


console.log(1);
setTimeout(function(){
    console.log(2);
    Promise.resolve(1).then(function(){
        console.log('promise1')
    })
})
setTimeout(function(){
    console.log(3)
    Promise.resolve(1).then(function(){
        console.log('promise2')
    })
})
setTimeout(function(){
    console.log(4)
    Promise.resolve(1).then(function(){
        console.log('promise3')
    })
})

复制代码
1 2 promise1 3 promise2 4 promise3
console.log(1);
setTimeout(function(){
    console.log(2);
    Promise.resolve(1).then(function(){
        console.log('promise1')

        setTimeout(function(){
            console.log(3)
            Promise.resolve(1).then(function(){
                console.log('promise2')
            })
        })

    })
})
复制代码
1 2 promise1 3 promise2

总结回顾

  • 栈:

    • 存储基础数据类型

    • 按值访问

    • 存储的值大小固定

    • 由系统自动分配内存空间

    • 空间小,运行效率高

    • 先进后出,后进先出

    • 栈中的DOM,ajax,setTimeout会依次进入到队列中,当栈中代码执行完毕后,再将队列中的事件放到执行栈中依次执行。

    • 微任务和宏任务


  • 堆:

    • 存储引用数据类型

    • 按引用访问

    • 存储的值大小不定,可动态调整

    • 主要用来存放对象

    • 空间大,但是运行效率相对较低

    • 无序存储,可根据引用直接获取

广而告之

本文发布于薄荷前端周刊,欢迎Watch & Star ★,转载请注明出处。

作者:薄荷前端
链接:juejin.im/post/5b1deac0
来源:掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

觉得有用的话就点个赞吧,让更多人看到!

继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续
栈是计算机管理,堆是程序员管理~
栈不可随机存取,堆可以~
继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续
继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续

我的这篇文章中有关于栈的介绍人类身份验证 - SegmentFault


继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续



继续浏览内容
知乎
发现更大的世界
打开
Chrome
继续


普通分类: