Algorithm Note --- 堆与栈

Posted on

前言：

作为野生程序员，总是提到堆栈，堆栈，其实长久以来并不理解其真正的区别，今天深入学习之后，记录记录，加深记忆！！！

堆栈的区分

0x00、写代码的时候所说的堆与栈

  • 栈，一种先进后出（FILO）的数据结构，如同一个箱子，往里面放书进去，想要拿到箱子底部的那本书就必须把上面的书全部取出来之后才能拿到。
  • 堆, 一种经过排序的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小或最大（因此也有最小堆和最大堆之分），且根结点的两个子树也是一个堆。由于堆的这个特性，常用来实现优先队列，堆的存取是随意，就像一栋大楼的不同单元，每层又像一个子树，知道楼栋单元号就可以直接去拜访，而不需要一层一层的找

0x01、计算机内存分配上所说的堆与栈–堆区与栈区

以C语言程序内存分配为例，这里所说的堆和栈就是指计算机内存中的堆区和栈区，我们知道程序在运行时需要将代码拷贝到内存中执行，计算机系统会在内存中分配空间来分别存储代码运行时所需的不同信息：
栈区和堆区就是其中两个空间。除此之外，还有BSS段、数据段、代码段等分区。
2474121-e6e531010176eb33.png

  • 栈区、作为内存中存储结构，通常存放程序临时创建的局部变量，即函数括大括号 “{ }” 中定义的变量，其中还包括函数调用时其形参，调用后的返回值等。 栈是由到高地址向低地址扩展的数据结构。即依次定义两个局部变量，首先定义的变量的地址是高地址，其次变量的地址是低地址。栈还具有“小内存、自动化、可能会溢出”的特点。栈顶的地址和栈的最大容量一般是系统预先规定好的，通常不会太大。由于栈中主要存放的是局部变量，而局部变量的占用的内存空间是其所在的代码段或函数段结束时由系统回收重新利用，所以栈的空间是循环利用自动管理的，一般不需要人为操作。如果某次局部变量申请的空间超过栈的剩余空间时就有可能出现 “栈的溢出”，进而导致意想不到的后果。所以一般不宜在栈中申请过大的空间，比如长度很大的数组、递归调用重复次数很多的函数等等。
  • 堆区、通常存放程序运行中动态分配的存储空间。堆是低地址向高地址扩展的数据结构，是一块不连续的内存区域。在标准C语言上，使用malloc等内存分配函数是从堆中分配内存的，在Objective-C中，使用new创建的对象也是从堆中分配内存的。
    堆具有“大内存、手工分配管理、申请大小随意、可能会泄露”的特点，堆内存是操作系统划分给堆管理器来管理的，管理器向使用者（用户进程）提供API（malloc和free等）来使用堆内存。需要程序员手动分配释放，如果程序员在使用完申请后的堆内存却没有及时把它释放掉，那么这块内存就丢失了（进程自身认为该内存没被使用，但是在堆内存记录中该内存仍然属于这个进程，所以当需要分配空间时又会重新去申请新的内存而不是重复利用这块内存），就是我们常说的-内存泄漏，所以内存泄漏指的是堆内存被泄露了。
  • BSS段、
    Block Started by Symbol的简称，通常是指用来存放程序中未初始化的全局变量和静态变量。
  • 数据段、 通常是指用来存放程序中已初始化的全局变量和静态变量以及字符串常量
  • 代码段、
    通常是指用来存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定。

    0x03、典型关于各种变量在内存中分配位置的例子

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    #include <stdio.h>
    int a = 0;                  // 全局初始化区
    char p1;                    // 全局未初始化区
    int main(int argc, const char * argv[]) {
          int b ;                 // 栈
          char s[] = "abc";       // 栈
          char p2 ;               // 栈
          char p3 = "123456";     // 123456在常量区，p3在栈上。
          static int c = 0 ;      // 全局（静态）初始化区
          p1 = (char )malloc(10); // 分配的10字节的区域就在堆区
          p2 = (char )malloc(20); // 分配的20字节的区域就在堆区
          printf("%p\n",p1);      // 0xffffffb0
          printf("%p\n",p2);      // 0xffffffc0
          return 0;                
    //p1 变量的地址 0xffffffb0 比 p2 变量的地址 0xffffffc0 要小
    }

参考链接：

https://www.cnblogs.com/jiahuafu/p/8575044.html
https://www.jianshu.com/p/b2380e47d005