栈堆

发表于 更新于

数据结构的栈和堆

  • 栈：只能在表的一端进行插入和删除的线性表。具有先进后出的性质，可以理解为装数据的桶。
  • 堆：经过排序的树形数据结构。

内存分配的栈和堆（以c++编译程序为例）

存放区域

区域 作用
栈区（stack） 由编译器自动分配和释放，存放函数的参数值，局部变量的值等。操作方式类似与数据结构中的栈
堆区（heap） 一般由程序员分配和释放，若程序员不释放，程序结束时可能由操作系统回收。与数据结构中的堆是两码事，分配方式类似于链表。
全局区（静态区）（static） 全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的还有一块区域。程序结束后由系统释放
文字常量区 常量字符串，程序结束后由系统释放
程序代码区 存放函数体的二进制代码

没有手动释放堆区的情况

1 从C语言本身设计来说，不会释放。
所谓动态内存，是由malloc系列函数进行申请的内存，除非在程序中使用free释放，否则该段内存不会被释放掉。
从这个角度来说，即使进程结束，该段内存也会被占用。这种现象被称为内存泄露。
2 大多数操作系统可以智能释放。
动态内存由于是进程使用，向操作系统控制方申请的内存，所以操作系统内核可以记录哪些内存由哪个进程使用，这样为了减少内存泄露的危害，操作系统内核均实现了在进程退出后，进程分配的自用内存自动回收的机制。

图片

来看一个例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//main.cpp
int a = 0;//全局初始化区
char *p1;//全局未初始化区，p1是以地址为数据么？
main(){
    int b;//栈
    char s[] = "abc";//栈 “abc”也是在栈区么？还是在常量区？与p3的区别？数组在定义初始化的时候就在栈区开辟了一段连续的内存空间
    char *p2 ;//栈
    char *p3 = "123456";//p3在栈区；"12345\0"在常量区，为什么不在堆区？因为没有申请储存空间，只能存放在常量区
    static int c =0;
    p1 = (char *)malloc(10);
    p2 = (char *)malloc(20);//分配得来得10和20字节的区域就在堆区。
    strcpy(p1,"123456");//123456\0放在常量区。编译器可能会将它与p3所指向的"123456"优化成一个地方
    strcpy(p2,"abcdef");//把常量区的"abcdef"拷贝一份到申请的堆区
}

申请后系统的响应

  • 栈：仅仅要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。
  • 堆：首先应该知道操作系统有一个记录空暇内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空暇结点链表中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内存空间中的首地址处记录本次分配的大小，这样。代码中的delete语句才干正确的释放本内存空间。所以堆是不连续的内存区域。
    （栈区和全局区的内存分布也不是连续的）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
int g1=0, g2=0, g3=0;
int main(){
    static int s1=0, s2=0, s3=0;
    int v1=0, v2=0, v3=0;
    //打印出各个变量的内存地址
    printf("0x%08x\n",&v1);//打印各本地变量的内存地址
    printf("0x%08x\n",&v2);
    printf("0x%08x\n\n",&v3);
    printf("0x%08x\n",&g1); //打印各全局变量的内存地址
    printf("0x%08x\n",&g2);
    printf("0x%08x\n\n",&g3);
    printf("0x%08x\n",&s1); //打印各静态变量的内存地址
    printf("0x%08x\n",&s2);
    printf("0x%08x\n\n",&s3);
    return 0;
}

另外。因为找到的堆结点的大小不一定正好等于申请的大小。系统会自己主动的将多余的那部分又一次放入空暇链表中。

能够申请的内存大小

  • 栈：在Windows下,栈是向低地址扩展的数据结构。是一块连续的内存的区域栈顶的地址和栈的最大容量是系统预先规定好的。
  • 堆：堆是向高地址扩展的数据结构，是不连续的内存区域。堆的大小受限于计算机系统中有效的虚拟内存。

参考链接

0%