C# · 12月 19, 2021

堆,栈,队列详细介绍

一些自己理解的概念

(1)内存:内存是计算机重要的部件之一,任何程序都需要在内存中运行,是与cpu和外部存储设备数据沟通的桥梁。在计算机运行的过程中,cpu会把内存中的数据进行运算,当运行结束后,cpu会把迅速按结果暂时输出到内存。所以内存也决定着计算机的稳定运行。

(2)数据结构:数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。(百度)

(3)常用的数据结构:数组、栈、队列、堆、链表、树、图、散列表等。

(4)堆:可以看作是一个完全二叉树(若设二叉树的深度为h,除第h层外,其它各层(1~h-1)的结点数都达到最大个数,第h层所有的结点都连续集中在最左边,这就是完全二叉树。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。)堆要在程序运行时动态分配内存,存取速度较慢。

Stringstr1=”abc”;

Stringstr2=”abc”;

JVM创建了两个引用str1和str2,但只创建了一个对象,而且两个引用都指向了这个对象

堆先进先出

下面用过数组来模拟下(完全二叉树)

(5)栈:栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。(百度)

栈是后进先出

(6)队列:队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

队列先进先出

(7)内存中的堆内存和占内存(切记不是数据结构中的堆和栈)

堆内存栈内存空间分配

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

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

堆内存栈内存缓存方式

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

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

堆内存栈内存申请效率的比较

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

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

堆内存栈内存生成时间的比较

栈:在编译时确定的,不是在运行时.

堆:在运行时确定的,不是在编译时.

堆内存栈内存存储java数据类型的比较

栈:int,short,long,byte,float,double,boolean,char等基本类型和对象的引用(比如Carcar =new Car()中Carcar为对象的引用 ,而 new Car()是实际对象,存在于堆中)。

堆:包装类和真实的对象(String类型也存在于堆内存)

以上是本人对堆,栈,队列的一些浅薄理解,如果有错误,欢迎大家在留言指正,相互学习,共同进步!