堆和栈

曾经终败给现在 2022-10-25 04:42 213阅读 0赞

# 引言 #

经常提起堆和栈，堆和栈的区别和联系是什么，数据结构中存在堆和栈，java虚拟机中也有堆和栈的概念，同理js中也有堆和栈的概念，这三者是不同的，以防混淆。本文主要介绍前述3种情况中的堆和栈。

**堆** 是堆内存的简称。  
**        栈** 是栈内存的简称。

**堆**是动态分配内存，内存大小不一，也不会自动释放。**栈**是自动分配相对固定大小的内存空间，并由系统自动释放。

# 1. java中的堆和栈 #

简略说一下java虚拟机中的堆和栈。java虚拟机运行时在内存中开辟一片内存区域，JVM内存区域分为5片：寄存器、本地方法区、方法区、栈内存和堆内存。栈内存:栈内存首先是一片内存区域，存储的都是局部变量，凡是定义在方法中的都是局部变量（方法外的是全局变量），for循环内部定义的也是局部变量，是先加载函数才能进行局部变量的定义，所以方法先进栈，然后再定义变量，变量有自己的作用域，一旦离开作用域，变量就会被释放。栈内存的更新速度很快，因为局部变量的生命周期都很短。堆内存:存储的是数组和对象（其实数组就是对象），凡是new建立的都是在堆中，堆中存放的都是实体（对象），实体用于封装数据，而且是封装多个（实体的多个属性），如果一个数据消失，这个实体也没有消失，还可以用，所以堆是不会随时释放的，但是栈不一样，栈里存放的都是单个变量，变量被释放了，那就没有了。堆里的实体虽然不会被释放，但是会被当成垃圾，Java有垃圾回收机制不定时的收取。

# 2. 数据结构中的堆和栈         #

## 2.1  堆概念 ##

堆分为小根堆和大根堆，对于一个小根堆，它是具有以下特性的一颗完全二叉树。

（1）若根节点存在左孩子，则根节点的值小于等于左孩子节点的值。

（2）若根节点存在右孩子，则根节点的值小于等于右孩子节点的值。

（3）以左右孩子为根的子树又各是一个堆。

大根堆的定义和上述类似，只要把小于等于改为大于等于就可以了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvbmdsZjUyMQ_size_16_color_FFFFFF_t_70][]

图1 小根堆

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvbmdsZjUyMQ_size_16_color_FFFFFF_t_70 1][]

图2 大根堆

注释：若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都**连续集中在最左边**，这就是完全二叉树。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvbmdsZjUyMQ_size_16_color_FFFFFF_t_70 2][]

图3 完全二叉树

## 2.1.1 堆的抽象数据类型 ##

堆的抽象数据类型中的数据部分是按一种存储结构表示的堆，用标识符HBT表示，其存储类型使用标识符HeapType表示。堆的抽象数据类型中的操作部分通常为：向堆中插入一个元素、从堆中删除堆顶元素、初始化一个堆、清除一个堆和判断一个堆是否为空。

## 2.1.2  堆的存储结构 ##

堆同一班二叉树一样既可以采用顺序存储，也可以采用链式存储。但由于堆是一颗完全二叉树，所以适宜采用顺序存储，这样能够充分利用其存储结构。

对堆进行顺序存储时，首先要对堆中的所有节点进行编号，然后再以编号为下标存储到指定数组的对应元素中。为了利用数组的0号元素，堆中节点的编号从0而不是从1开始。编号顺序按照从上至下，同一层从左到右，若堆中含有n个节点，则编号范围为 0~ n-1。

堆中的节点从0开始编号后，编号为0至n/2-1的结点为分支结点，编号为 n/2~n-1的结点为叶子结点；当n为奇数时则每个分支结点既有左孩子又有右孩子，当那位偶数时，最大的一个分支结点只有左孩子，没有右孩子；对于每个编号为i的分支结点，其左孩子结点的编号为2i+1,右孩子的节点编号为2i+2；除编号为0的堆顶节点外，对于其余编号为i的节点，其双亲节点的编号为 (i-1)/2

# 2.2 栈概念 #

栈（stack）又称堆栈，它是一种运算受限的线性表，其限制是进允许在表的一端进行插入和删除运算。对栈进行运算的一端叫做栈顶，栈顶的第1个元素被称为栈顶元素，相对地，把另一端称为栈底。向一个栈插入元素又称为进栈或入栈，它是把该元素放在栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或者退栈，他是把栈顶元素删掉，使下面的相邻元素成为新的栈顶元素。

## 2.2.1  栈的顺序存储结构和操作实现 ##

栈的顺序存储结构同样需要使用一个数组和一个整型变量来实现，利用数组来顺序存储栈中的所有元素，利用整型变量来存储栈顶元素的下标位置。栈数组用stack\[MaxSize\]表示，表示栈顶元素位置的整型变量用top表示，则元素类型为ElemType的栈的顺序存储结构可定义如下： ElementType stack\[MaxSize\]; int top。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvbmdsZjUyMQ_size_16_color_FFFFFF_t_70 3][]

图4

# 2.2.3  栈的链接存储结构 #

**栈的链接存储结构**与**线性表**的存储结构相同，是通过由节点构成的**单链表**实现的，此时表头指针称为**栈顶指针，**由栈顶指针指向的表头节点叫做**栈顶结点**，整个单链表被称为**链栈，**即链接存储的栈。

当向一个链栈中插入一个元素时，是把该元素插入到栈顶，即使该元素的指针域指向原来的栈顶结点，而栈顶指针修改指向该元素节点，使该节点称为新的栈顶结点。

当从一个链栈中删除元素时，是把栈顶元素结点删除掉，即取出栈顶元素后，是栈顶指针指向原栈顶结点的指针域指向的结点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvbmdsZjUyMQ_size_16_color_FFFFFF_t_70 4][]

图5   原有栈

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvbmdsZjUyMQ_size_16_color_FFFFFF_t_70 5][]

图6  插入一个结点 D

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvbmdsZjUyMQ_size_16_color_FFFFFF_t_70 6][]

图7 删除结点 C 和 D

# 3.  JavaScript中的堆和栈 #

## 3.1  JavaScript内存机制 ##

`JavaScript`具有自动垃圾回收机制，周期性会检查没有使用的变量，进行回收释放。所以在闭包中，如果引用了外部的变量，则无法进行释放和回收，一般会传参进去。

垃圾回收：找出那些不再继续使用的变量，然后释放其占用的内存，垃圾收集器会按照固定的时间间隔周期性地执行这一操作。

在`JS`中，每一个数据都需要一个内存空间，内存空间又分为栈内存(stack)与堆内存(heap)。

## 3.2 栈 ##

栈内存一般储存基础数据类型(Undefined、Null、Boolean、Number和String)的数据。

我们定义一个变量 var `num = 1`，系统自动分配存储空间。我们可以直接操作保存在栈内存空间的值，因此基础数据类型都是按值访问。

数据在栈内存中的存储与使用方式类似于数据结构中的栈数据结构，遵循 **后进先出**的原则。

## 3.3 堆 ##

堆内存一般储存引用数据类型（Function，Array，Object）。

`JS`的引用数据类型，比如数组`Array`，它们值的大小是不固定的。引用数据类型的值是保存在堆内存中的对象。`JavaScript`不允许直接访问堆内存中的位置，因此我们不能直接操作对象的堆内存空间。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvbmdsZjUyMQ_size_16_color_FFFFFF_t_70 7][]

图8  引用类型数据在内存中的存放

因此当我们要访问堆内存中的引用数据类型时，实际上我们首先是从栈中获取了该对象的指针，然后再从堆内存中取得我们需要的数据。

所以，基本类型赋值相互不影响，引用类型赋值，会影响原对象。

## 3.4 javascript存放数据特点 ##

1.  JavaScript具备自动垃圾回收机制
2.  JS内存分为堆内存和栈内存
3.  引用类型在栈中保存指针，在堆中保存对象值
4.  栈内存数据遵循 **先进后出**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvbmdsZjUyMQ_size_16_color_FFFFFF_t_70]: /images/20221024/c4ce300ee92143f780a3ae99f9940363.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvbmdsZjUyMQ_size_16_color_FFFFFF_t_70 1]: /images/20221024/db3066e775cf4b05b907efa39c6d7687.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvbmdsZjUyMQ_size_16_color_FFFFFF_t_70 2]: /images/20221024/faba3e9619fe45849bcb5b4f0fa02b9a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvbmdsZjUyMQ_size_16_color_FFFFFF_t_70 3]: /images/20221024/5b49fed492474efbbf60e9074bf7a948.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvbmdsZjUyMQ_size_16_color_FFFFFF_t_70 4]: /images/20221024/93706c20d4d44c20af8556455b0a31ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvbmdsZjUyMQ_size_16_color_FFFFFF_t_70 5]: /images/20221024/2b91e2b5239b447ea39515b784eca963.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvbmdsZjUyMQ_size_16_color_FFFFFF_t_70 6]: /images/20221024/54643af2788a401cb098a045fb6d1251.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NvbmdsZjUyMQ_size_16_color_FFFFFF_t_70 7]: /images/20221024/8c928b99ab1845b4aad0817cad8175cd.png