走近堆与栈

简介: 走近堆与栈

1 堆栈简介

众所周知,面试中被问到的的最高频话题就是进程与线程堆与栈

首先是概念的问题,平时我们所说的堆栈指的就是栈,而在内存中又区分为堆内存和栈内存。

关于栈内存和堆内存的对比见下表:

2 栈内存

在有的书中,对栈是这样定义的:栈是限定仅在表尾进行插入和删除的线性表

栈内存是为线程留出的临时空间,每个线程都有一个固定大小的栈空间,栈空间存储的数据只能由当前线程访问,所以是线程安全的,也就是线程与栈存在着一一对应的关系,一个萝卜一个坑。

栈空间的分配和回收是由系统来做的,我们不需要手动控制。

当一个函数调用时,系统就会为该函数的调用分配栈空间,当函数返回后,系统就会自动回收这块空间,同理,下次其它函数调用和返回,系统还是会自动分配和回收空间。

那么为什么在函数的调用和返回的时候必须用到栈内存呢?其他内存行不行呢?

因为函数调用、返回的机制与入栈、出栈非常吻合。当函数A调用了函数B的时候,需要完成跳转,需要先将其当前执行指令的地址0f007873入栈保护。因为这样当被调用函数执行完毕的时候,就可以根据首地址返回原来的函数继续执行其余部分代码。

其实真正函数的调用过程比这个复杂一些,包括将一些参数等都要压入栈。

所以这也解释了为什么我们在递归调用中经常会出现堆栈溢出的问题,当我们执行递归调用的时候,若是一直“”,则堆栈会一直进行入栈操作,有时候就会出现堆栈溢出的情况。

2 堆内存

堆内存实际上指的就是(满足堆内存性质的)优先队列的一种数据结构,第1个元素有最高的优先权。

我们平时在C语言和C++中使用mallocnew分配的内存就是堆内存,堆内存的一大特点就是大小不固定,可以动态扩容,空间由程序员动态分配,更加灵活。

然而,既然有优点也必然伴随着缺点。

  1. 第一个缺点就是它容易产生内存泄露,malloc出来的没有freenew出来的如果没有delete,都会产生内存泄露。
  2. 第二个缺点,容易产生内存碎片,在分配和回收时需要对很多内存碎片进行整理,效率较低。

分配过程:在堆内存分配时首先应该知道操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时,会遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序(所以堆内存分配必栈内存分配要慢)也就是我们常说的“首次适应算法”。

--------------------------------------------------------------------------------------------------------------

以上图为例,比方说程序的某个进程申请了15MB的内存空间,则操作系统会遍历该空闲分区链表,发现第一个节点的数值为20MB,也就是说,第一个空闲分区有20MB空间可以申请,所以就将第一个空闲分区提供给了当前进程。

--------------------------------------------------------------------------END-----------------------------------------------------

相关文章
|
1天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
28 9
|
23天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
24 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
4天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
23天前
初步认识栈和队列
初步认识栈和队列
52 10
|
17天前
数据结构(栈与列队)
数据结构(栈与列队)
15 1
|
22天前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
61 1
|
18天前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
13 0
|
23天前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
23天前
探索顺序结构:栈的实现方式
探索顺序结构:栈的实现方式
|
23天前
|
存储 C语言
栈和队列题目练习
栈和队列题目练习
14 0