专栏首页编程拯救世界谈谈堆与栈:数据结构和内存角色

谈谈堆与栈:数据结构和内存角色

说起堆[1]栈[2],我们一般都会想到它们是一种数据结构,具有某些特性。

然而,除此之外,它们在计算机的内存中也扮演着不同的角色

数据结构

  • 一种特殊的、基于树的数据结构
  • 通常可以有两种类型:
    1. 最大堆:根结点的键值是所有堆结点键值中最大者的堆
    2. 最小堆:根结点的键值是所有堆结点键值中最小者的堆

堆(图片来自 GeeksforGeeks)

  • 一种线性的数据结构
  • 遵循执行操作的特定顺序:后进先出FIFO

栈(图片来自 GeeksforGeeks)

内存的用途

在计算机中,内存的用途大致可以分为四个方面:

  1. 代码区:放置二进制代码
  2. 数据区:用于存储全局变量等
  3. 堆区:为动态分配预留的内存空间
  4. 栈区:为执行线程留出的内存空间

堆区

堆是为动态分配预留的内存空间。

和栈不一样,从堆上分配和重新分配块没有固定模式,你可以在任何时候分配和释放它

堆包含一个链表来维护已用和空闲的内存块。在堆上新分配(用 new 或者 malloc)内存是从空闲的内存块中找到一些满足要求的合适块,这个操作会更新堆中的块链表。这些元信息也存储在堆上,经常在每个块的头部一个很小的区域。

栈区

栈是为执行线程留出的内存空间。

  1. 当函数被调用的时:系统栈会为这个函数开辟一个新的栈帧(包含局部变量、函数参数、返回值等),并把它压入栈中。这个栈帧中的内存空间被它所属的函数独占,正常情况下是不会和别的函数共享。
  2. 当函数执行完毕时:系统栈会弹出该函数所对应的栈帧。

栈帧:也叫过程活动记录,是编译器用来实现函数调用过程的一种数据结构。

举个例子:

package main

func A() {
    // ...
    B()
}

func B() {
    // ...
}

func main() {
    A()
}

在上述代码片段中,main() 函数调用了函数 A(),函数 A() 又调用了函数 B()。执行过程如下:

  1. main() 函数开始执行:将自己的栈帧压入栈
  2. main() 函数调用函数 A():将函数 A() 的栈帧压入栈
  3. A() 函数调用函数 B():将函数 B() 的栈帧压入栈
  4. B() 函数执行完毕,从栈顶弹出 B() 的栈帧,此时 A() 的栈帧被暴露在栈顶,处理器能根据其中的返回地址跳回 A() 的代码区继续执行代码
  5. A() 函数执行完毕,从栈顶弹出 A() 的栈帧,此时 main() 函数的栈帧被暴露在栈顶,处理器根据其中的返回地址跳回 main() 的代码区继续指定代码

栈要受到内存块的限制,不断的函数嵌套或为局部变量分配太多的空间,可能会导致栈溢出。也就是我们常说「递归导致栈溢出」的原因了。

总结

  • 堆是一种特殊的、基于树的数据结构,通常有最大堆和最小堆两种类型
  • 堆区是为动态分配预留的内存空间

  • 栈是一种线性的数据结构,遵循后进先出
  • 栈区是为执行线程留出的内存空间

参考资料

[1]

堆: https://www.geeksforgeeks.org/heap-data-structure/

[2]

栈: https://www.geeksforgeeks.org/stack-data-structure/

本文分享自微信公众号 - 编程拯救世界(CodeWarrior_),作者:江子抑

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 搞定面试算法系列 | 贪心算法与正确性归纳证明

    贪心算法就是让计算机模拟一个「贪心的人」来做出决策。这个贪心的人是目光短浅的,他每次总是:

    江不知
  • 图解精选 TOP 面试题 007 | 杨辉三角

    杨辉三角可以说是一道大家非常熟悉的题目了,一开始学 C 语言的时候就经常做打印杨辉三角的作业。

    江不知
  • 工具安利 | docsify 入坑指南与我放弃 Gitbook 的那些理由

    leetcode-notebook[1] 的题解越来越多,原先选择 Gitbook[2] 构建解题本的弊端逐渐显现出来,每次补充一道题解重新 build 项目时...

    江不知
  • 云计算技术对大企业的影响

    如今,突飞猛进的科技正在迅速改变人们的生活。云计算技术是传统计算技术的重大转变,对各种规模的企业带来极大的影响。但对大企业来说,其影响是非常积极的。

    静一
  • LevelDB 完全解析(3):SSTable

    SSTable 全称 Sorted String Table,顾名思义,里面的 key-value 都是有序保存的。除了两个 MemTable,LevelDB ...

    linjinhe
  • 【Java】12 Map 集合

       Map 用于保存具有映射关系的数据,因此 Map 集合里保存着两组值,一组值用于保存 Map 里的 key,另外一组值用于保存 Map 里的 value,...

    Demo_Null
  • 算法+数据解构(第04篇)空间复杂度你真的懂了吗?

    在本系列第1篇《走下神坛吧!算法》中提到了:计算复杂度分为时间复杂度与空间复杂度,第3篇《KO!大O——时间复杂度》详细介绍了时间复杂度,本篇文章来讲讲空间复杂...

    用户5224393
  • 网站漏洞修复方案防止SQL注入攻击漏洞

    SQL注入漏洞在网站漏洞里面属于高危漏洞,排列在前三,受影响范围较广,像asp、.net、PHP、java、等程序语言编写的代码,都存在着sql注入漏洞,那么如...

    网站安全专家
  • 1125-smallest-Sufficient-Team

    $S$表示一个二进制集合.$S$中第$i$位是$1$表示该集合包含标号是$i$的技能

    xiaohejun
  • 闲聊数据结构之list

    依稀记得有一次有人问,在你写一些代码的时候,你会选用什么数据结构呢?有什么选择的标准呢。。。当时也就当为了笑谈,好像并无什么特别的喜好,也没什么特别的感...

    SRE运维实践

扫码关注云+社区

领取腾讯云代金券