【Java】常用的数据结构

博主： Fivk
发布时间：2021 年 10 月 06 日
1122 次浏览
暂无评论
5053字数
分类： Java

> 数据存储的常用结构有：栈、队列、数组、链表和红黑树。
> 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
> 数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

这些数据结构java已经封装好了，只需要我们调用就行了。可以查看手册即可。

</div>

# 1、栈

* stack,又称堆栈，它是运算受限的线性表，其限制是仅允许在标的一端进行插入和删除操作，不允许在其 他任何位置进行添加、查找、删除等操作。
* 栈结构的集合，对元素的存取有如下特点：
  1. 先进后出（即先存进去的元素，要在它后面的元素依次取出后，才能取出该元素）。
  2. 栈的入口、出口的都是栈的顶端位置。

![堆栈.png](https://blog.fivk.cn/usr/uploads/2021/11/3961094656.png)

* 压栈：就是存元素。即，把元素存储到栈的顶端位置，栈中已有元素依次向栈底方向移动一个位置。
* 弹栈：就是取元素。即，把栈的顶端位置元素取出，栈中已有元素依次向栈顶方向移动一个位置。

### Stack 使用API

| 返回类型 | 实现方法         | 功能介绍                                     |
| ---------- | ------------------ | ---------------------------------------------- |
| boolean  | empty()          | 测试栈是否为空                               |
| E        | peek()           | 查看堆栈顶部的对象，但不从堆栈中移除它       |
| E        | pop()            | 移除堆栈顶部的对象，并作为函数的之返回该对象 |
| E        | push(E item)     | 把项压入堆栈顶部                             |
| int      | search(Object o) | 返回对象在堆栈中的位置，以1为基数            |

### 参考案例

```java
import java.util.Stack;

public class My_Stack {
    public static void main(String[] args) {
        Stack<Integer> sta = new Stack<>();
        sta.push(1);
        sta.push(2);
        sta.push(4);

while(!sta.empty()) {
            System.out.println(sta.pop());
        }
    }
}
```

以上实例编译运行结果如下：

```out
4
2
1
```

# 2、队列

* queue,简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入， 而在表的另一端进行删除。
* 队列结构的集合，对元素的存取有如下特点：
  1. 先进先出（即后存进去的元素，要在后它前面的元素依次取出后，才能取出该元素）。
  2. 队列的入口、出口各占一侧。

![队列.bmp](https://blog.fivk.cn/usr/uploads/2021/11/47950111.bmp)

### Queue 使用API

| 返回类型 | 实现方法   | 功能介绍                                                                                                                                              |
| ---------- | ------------ | ------------------------------------------------------------------------------------------------------------------------------------------------------- |
| boolean  | add(E e)   | 将指定的元素插入此队列（如果立即可行且不会违反容量限制），在成功时返回true，如果没有可用空间，则抛出IllegalStateException                             |
| E        | element()  | 获取，但是不移除此队列的头                                                                                                                            |
| boolean  | offer(E e) | 将指定的元素插入此队列（如果立即可行且不会违反容量限制），当使用有容量限制的队列时，此方法通常要优于 add(E)，后者可能无法插入元素，而只是抛出一个异常 |
| E        | peek()     | 获取但不移除此队列的头；如果此队列为空，则返回 null                                                                                                   |
| E        | poll()     | 获取并移除此队列的头，如果此队列为空，则返回 null                                                                                                     |
| E        | remove()   | 获取并移除此队列的头                                                                                                                                  |

注意：Queue没有empty()，Queue为 abstract；无法实例化，下面案例使用LinkedList进行实例化。

</div>

### 参考案例

队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。

LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

以下实例演示了队列（Queue）的用法：

```java
import java.util.LinkedList;
import java.util.Queue;

public class My_Queue {
    public static void main(String[] args) {
        Queue<Integer> que = new LinkedList<>();
        que.add(1);
        que.add(2);
        que.add(5);
        que.add(4);

while(que.size() > 0) {
            System.out.println(que.remove());
        }
    }
}
```

以上实例编译运行结果如下：

```out
1
2
5
4
```

# 3、数组

* Array：是有序的元素序列，数组是在内存中开辟一段连续的空间，并在此空间存放元素。
* 查找元素快：通过索引，可以快速访问指定位置的元素

![数组查询快.png](https://blog.fivk.cn/usr/uploads/2021/11/767740691.png)

* 增删元素慢
  * 指定索引位置增加元素：需要创建一个新数组，将指定新元素存储在指定索引位置，再把原数组元素根 据索引，复制到新数组对应索引的位置。
  * 指定索引位置删除元素：需要创建一个新数组，把原数组元素根据索引，复制到新数组对应索引的位 置，原数组中指定索引位置元素不复制到新数组中。

# 4、链表

* linked list,由一系列结点node（链表中每一个元素称为结点）组成，结点可以在运行时i动态生成。每 个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。链表结构有单向链表与双向链表。
* 单向链表–无序；双向链表–有序。

![单链表结构特点.png](https://blog.fivk.cn/usr/uploads/2021/11/3067625884.png)

* 链表结构的集合，对元素的存取有以下特点：
  1. 多个结点之间，通过地址进行连接。

![单链表结构特点.png](https://blog.fivk.cn/usr/uploads/2021/11/1810159288.png)

1. 查找元素慢：想查找某个元素，需要通过连接的节点，依次向后查找指定元素。
2. 增删元素快：
   * 增加元素：只需要修改连接下个元素的地址即可
   * 删除元素：只需要修改连接下个元素的地址即可

# 5、红黑树

* 二叉树：binary tree ,是每个结点不超过2的有序树（tree）。

> 二叉树是每个节点最多有两个子树的树结构。顶上的叫根结点，两边被称作“左子树”和“右子树”
  >

![二叉树.bmp](https://blog.fivk.cn/usr/uploads/2021/11/1648269889.bmp)
* 红黑树：红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然 是一颗二叉查找树。也就意味着，树的键值仍然是有序的。
* 红黑树的约束：

1. 节点可以是红色的或者黑色的
  2. 根节点是黑色的
  3. 叶子节点(特指空节点)是黑色的
  4. 每个红色节点的子节点都是黑色的
  5. 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同
  6. 元素有大小顺序，左子树小，右子树大
* 红黑树的特点
  速度很快,趋近平衡树,红黑树查找叶子元素的最少次数和最多次数不大于二倍

> 感谢小伙伴们的关注！
> 你的点赞、评论、关注、收藏是对博主的最大鼓励！
> 持续更新JavaSE学习笔记！欢迎订阅专栏！

最后修改：2021 年 11 月 11 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

本当迷
哈哈时过境迁再看一遍帆的文章质量还是那么高
挺胸的打工人
感谢博主分享
菜菜
一天就学一些我不知道的东西(´இ皿இ｀)
zhanqy
博主赛高！
null ？？［］
还可以把扩展运算符加上呀，这个很有用［…arr］，用于数组合...

【Java】常用的数据结构

Fivk • 2021 年 10 月 06 日

这些数据结构java已经封装好了，只需要我们调用就行了。可以查看手册即可。

</div>

# 1、栈

![堆栈.png](https://blog.fivk.cn/usr/uploads/2021/11/3961094656.png)

### Stack 使用API

### 参考案例

```java
import java.util.Stack;

public class My_Stack {
    public static void main(String[] args) {
        Stack<Integer> sta = new Stack<>();
        sta.push(1);
        sta.push(2);
        sta.push(4);

while(!sta.empty()) {
            System.out.println(sta.pop());
        }
    }
}
```

以上实例编译运行结果如下：

```out
4
2
1
```

# 2、队列

![队列.bmp](https://blog.fivk.cn/usr/uploads/2021/11/47950111.bmp)

### Queue 使用API

注意：Queue没有empty()，Queue为 abstract；无法实例化，下面案例使用LinkedList进行实例化。

</div>

### 参考案例

队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。

LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

以下实例演示了队列（Queue）的用法：

```java
import java.util.LinkedList;
import java.util.Queue;

public class My_Queue {
    public static void main(String[] args) {
        Queue<Integer> que = new LinkedList<>();
        que.add(1);
        que.add(2);
        que.add(5);
        que.add(4);

while(que.size() > 0) {
            System.out.println(que.remove());
        }
    }
}
```

以上实例编译运行结果如下：

```out
1
2
5
4
```

# 3、数组

* Array：是有序的元素序列，数组是在内存中开辟一段连续的空间，并在此空间存放元素。
* 查找元素快：通过索引，可以快速访问指定位置的元素

![数组查询快.png](https://blog.fivk.cn/usr/uploads/2021/11/767740691.png)

# 4、链表

![单链表结构特点.png](https://blog.fivk.cn/usr/uploads/2021/11/3067625884.png)

* 链表结构的集合，对元素的存取有以下特点：
  1. 多个结点之间，通过地址进行连接。

![单链表结构特点.png](https://blog.fivk.cn/usr/uploads/2021/11/1810159288.png)

# 5、红黑树

* 二叉树：binary tree ,是每个结点不超过2的有序树（tree）。

> 二叉树是每个节点最多有两个子树的树结构。顶上的叫根结点，两边被称作“左子树”和“右子树”
  >

> 感谢小伙伴们的关注！
> 你的点赞、评论、关注、收藏是对博主的最大鼓励！
> 持续更新JavaSE学习笔记！欢迎订阅专栏！

【Java】常用的数据结构

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

【C】极域电子教室学生端解除控制

【开发技巧】@CrossOrigin注解解决跨域问题

【Fivk】文章归档

回忆刚入天柱二中的我

【开发工具】zabbix3监控工具

第一次使用C语言

【Java】集合之HashMap

【C++】STL常用容器_queue容器

【动态规划】数字三角形

【Java】常用的数据结构

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【Java】常用的数据结构

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款