解析java中的栈和堆

青旅半醒 2022-01-31 01:15 282阅读 0赞

堆（Heap）与栈（Stack）是常用的两种数据结构；也是两种内存管理方式。

### 一、JVM中的堆和栈： ###

**堆内存**： 用来存放new创建的对象和数组，由java jvm的垃圾回收器来管理；堆内存的特点就是：先进先出，后进后出；堆可以动态地分配内存大小，生存期也不必事先告诉编译器；缺点是存取速度较慢。

**栈内存**：由操作系统自动分配释放 ，用来存放基本类型变量和对象的引用变量等。其操作方式类似于数据结构中的栈；栈的优势是：存取的速度都比堆要快，仅次于寄存器；栈数据可以共享，但是缺点时，栈空间中的数据大小和生存期必须是确定的，缺乏灵活性。

**栈内存和堆内存的区别：**1.栈是后进先出，先进后出；2.先进先出，后进后出；3.栈内存用来存放方法或者局部变量等 ；4.堆用来存放new创建的对象和数组。

### 二、数据结构中的堆和栈 ###

**栈**是一种运算受限的线性表；只允许在表的一端进行删除和插入操作，此端被称为栈顶（top）；相对来说，另一端就是栈底（Bottom）；新元素放入栈顶被称为入栈、压栈(push)或者进栈；把栈顶的元素删除被称为出栈或者退栈（Pop）;栈具有‘先进后出’的特性，简称FILO。

栈是一种线性结构，其底层数据结构可以使用数组或链表（单向链表、双向链表或循环链表），因此栈包含两种：顺序栈和链式栈；

顺序栈：使用数组实现底层数据结构。

链式栈：使用链表实现底层数据结构。

栈数据结构图如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjIyODk1MA_size_16_color_FFFFFF_t_70][]

**堆**是一种特殊的完全二叉树，当且仅当满足所有节点的值总是不大于或不小于其父节点的值的完全二叉树被称之为堆。其分为两种：大根堆和小根堆；大根堆：根节点最大的堆；小根堆：根节点最小的堆。

大根堆和小根堆如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjIyODk1MA_size_16_color_FFFFFF_t_70 1][]

堆也可以使用数组来存储，存储结构如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjIyODk1MA_size_16_color_FFFFFF_t_70 2][]

**如果当前节点的索引为index，那么：**

当前节点的父节点 = (index - 1) / 2

当前节点的左子节点 = index \* 2 + 1

当前节点的左子节点 = index \* 2 + 2

**堆的实现：**

1.创建：如果数组具有对应的树表示形式不符合堆的条件时会重新排列元素。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjIyODk1MA_size_16_color_FFFFFF_t_70 3][]

2.插入（insert）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjIyODk1MA_size_16_color_FFFFFF_t_70 4][]

3.删除（pop）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjIyODk1MA_size_16_color_FFFFFF_t_70 5][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjIyODk1MA_size_16_color_FFFFFF_t_70]: /images/20220131/a919617c9bd44c4eac18f4a14896f4e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjIyODk1MA_size_16_color_FFFFFF_t_70 1]: /images/20220131/d8855d957b214fe7b0afbf5bf4b9e39b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjIyODk1MA_size_16_color_FFFFFF_t_70 2]: /images/20220131/ebf24b7200fe4feaacedd970f6c65e87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjIyODk1MA_size_16_color_FFFFFF_t_70 3]: /images/20220131/d6c6b959108b4c9cbdbb3d3f3a051b7d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjIyODk1MA_size_16_color_FFFFFF_t_70 4]: /images/20220131/fb99574c22804ef8858c62fdb6ec11b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjIyODk1MA_size_16_color_FFFFFF_t_70 5]: /images/20220131/7f14e7e060fa465196b88ef8a854aecd.png