【Java】基础24：数据的存与取

在计算机世界里面所有的一切皆是数据，其存在的形式为二进制，也就是只有0和1。

那么对于计算机来说，它需要做好两件事：

如何存这些数据？如何取这些数据？

这两件事情的过程就是数据结构。

所以不要看这个定义好像很复杂的样子，其实很好理解，就是如何存数据和如何取数据。

现在主要介绍简单的几个数据结构。

一、堆栈和队列

其实关于这两种数据结构，用中国的一个成语推陈出新就可以理解，这里面还牵扯到了一个小故事。

《九章算术》中记载：韩信投靠刘邦后，被派去管理杂乱无章的粮仓，但很快韩信就把新谷、陈粮分开。

旧粮仓只是上开口的，取粮食时，取的是最上面刚放进去的新粮食，这样旧粮食就一直堆积到最下面了。

后来韩信就将粮仓在下面开了一个口，这样每次取的粮食都是最旧的粮食。

• 旧粮仓存储粮食的数据结构类似堆栈。
• 新粮仓存储粮食的数据结构类似队列。

它们的数据结构如下图：

①堆栈：先进后出，后进先出。

• 适用场景有子弹压进弹夹。
• 栈的入口、出口的都是栈的顶端位置。
• 压栈就是存元素。
• 弹栈就是取元素。

Java虚拟机JVM的内存分布就有堆栈，其中就满足先进后出原则。我们最常见的mian方法，它是程序的主入口，先进堆栈，但是最后才出来。

②队列：先进先出，后进后出。

• 适用场景有过安检。
• 队列的入口、出口各占一侧。
• 入队就是存元素。
• 出队就是取元素。

如果还是不能理解，用最最通俗的语言解释就是：

• 堆栈：吃了吐，吐的是我刚吃的。
• 队列：吃了拉，拉的是我以前吃的。

二、数组

数组是有序的元素序列，它会在内存中开辟一段连续的空间，并在此空间存放元素，数据结构如下图：

①数组中的元素地址是连续的

②查询快（有索引）

通过索引，可以快速访问指定位置的元素，就像是一排出租屋，有100个房间，从001到100每个房间都有固定编号，通过编号就可以快速找到租房子的人。

③增删慢（长度固定）

数组的长度是固定的，无论是增加元素还是删除元素，因为长度都改变了，就都需要创建一个新的数组，再将原数组复制过去，自然也就慢了。

④使用场景

需要频繁查询的场景，这也是现实生活中一般情况下使用最多的场景。

比如：登录微信或者QQ，这个过程就是查询的过程，修改用户名密码就是修改的过程，基本每天都会登录，但是很少会修改。

三、链表

链表是由一系列结点组成，每个结点包括两个部分：

• 一个是存储数据元素的数据域。
• 另一个是存储下一个结点地址的指针域。

链表结构有单向链表与双向链表，主要介绍下单向链表：

①链表的元素地址是随机的

②查询慢

查找某个元素，需要通过连接的节点，依次向后查找指定元素，所以查询很慢。

③增删快

增加修改元素时，只需要修改连接下个元素的地址即可，所以增删很快。

④适用场景

需要频繁增加、删除元素的场景。

对于单向链表和双向链表用现实里的例子可以这么理解：

• 单向链表就好比玩“老鹰捉小鸡”这个游戏中的小鸡，我只拉着前面的人，后面的人拉着我。
• 双向链表就好比手牵着手围成一个圈，我即拉着左边的人，又拉着右边的人。

四、树结构

简单的理解，就是一种类似于我们生活中树的结构。

在日常的应用中，我们用的更多的是二叉树。

什么叫二叉树呢？

即每个结点不超过2的有序树：

其中查找树又是一种特殊的二叉树，遵循左小右大的原则，这样我们在查找数据时会更加的快：

比如我们要查找数字5，先查到的一个数字是2，这个时候左小右大，我们只需要往右边查就可以了，左边就不用管了，相对而言会更加的快些。

总而言之：二叉树是数组和链表的折中方案。

• 它增加删除元素较快，位于数组和链表之间。
• 它查询元素也是较快，位于数组和链表之间。

用现实生活中的例子来理解它们之间的区别：

• 数组就好比一个理科强的学生：他数学100分，但英语只能考50分。
• 链表就好比一个文科强的学生：她英语100分，但数学只能考60分。
• 树结构就好比一个较全面的学生：他数学英语都是80分。

关于树结构还有太多太多，平衡二叉树、红黑树、B+树等 ，在此就不展开讲了，主要是我自己也还没弄懂……

当然数据结构远远没有这么简单，除了这些，也还有表结构，图结构等。今天主要说明这几种简单的数据结构，随着后面的学习会将其逐渐完善。

总结