【Java】基础24：数据结构
image
在计算机世界里面所有的一切皆是数据，其存在的形式为二进制，也就是只有0和1。
那么对于计算机来说，它需要做好两件事：
如何存这些数据？如何取这些数据？
这两件事情的过程就是数据结构。
所以不要看这个定义好像很复杂的样子，其实很好理解，就是如何存数据和如何取数据。
现在主要介绍简单的几个数据结构。
一、堆栈和队列
其实关于这两种数据结构，用中国的一个成语推陈出新就可以理解，这里面还牵扯到了一个小故事。
《九章算术》中记载：韩信投靠刘邦后，被派去管理杂乱无章的粮仓，但很快韩信就把新谷、陈粮分开。
旧粮仓只是上开口的，取粮食时，取的是最上面刚放进去的新粮食，这样旧粮食就一直堆积到最下面了。
后来韩信就将粮仓在下面开了一个口，这样每次取的粮食都是最旧的粮食。
-
旧粮仓存储粮食的数据结构类似堆栈。
-
新粮仓存储粮食的数据结构类似队列。
它们的数据结构如下图：
image
①堆栈：先进后出，后进先出。
-
适用场景有子弹压进弹夹。
-
栈的入口、出口的都是栈的顶端位置。
-
压栈就是存元素。
-
弹栈就是取元素。
Java虚拟机JVM的内存分布就有堆栈，其中就满足先进后出原则。我们最常见的mian方法，它是程序的主入口，先进堆栈，但是最后才出来。
②队列：先进先出，后进后出。
-
适用场景有过安检。
-
队列的入口、出口各占一侧。
-
入队就是存元素。
-
出队就是取元素。
如果还是不能理解，用最最通俗的语言解释就是：
-
堆栈：吃了吐，吐的是我刚吃的。
-
队列：吃了拉，拉的是我以前吃的。
二、数组
数组是有序的元素序列，它会在内存中开辟一段连续的空间，并在此空间存放元素，数据结构如下图：
image
①数组中的元素地址是连续的
②查询快（有索引）
通过索引，可以快速访问指定位置的元素，就像是一排出租屋，有100个房间，从001到100每个房间都有固定编号，通过编号就可以快速找到租房子的人。
③增删慢（长度固定）
数组的长度是固定的，无论是增加元素还是删除元素，因为长度都改变了，就都需要创建一个新的数组，再将原数组复制过去，自然也就慢了。
④使用场景
需要频繁查询的场景，这也是现实生活中一般情况下使用最多的场景。
比如：登录微信或者QQ，这个过程就是查询的过程，修改用户名密码就是修改的过程，基本每天都会登录，但是很少会修改。
三、链表
链表是由一系列结点组成，每个结点包括两个部分：
-
一个是存储数据元素的数据域。
-
另一个是存储下一个结点地址的指针域。
链表结构有单向链表与双向链表，主要介绍下单向链表：
image
①****链表的元素地址是随机的
②查询慢
查找某个元素，需要通过连接的节点，依次向后查找指定元素，所以查询很慢。
③增删快
增加修改元素时，只需要修改连接下个元素的地址即可，所以增删很快。
④适用场景
需要频繁增加、删除元素的场景。
对于单向链表和双向链表用现实里的例子可以这么理解：
-
单向链表就好比玩“老鹰捉小鸡”这个游戏中的小鸡，我只拉着前面的人，后面的人拉着我。
-
双向链表就好比手牵着手围成一个圈，我即拉着左边的人，又拉着右边的人。
四、树结构
简单的理解，就是一种类似于我们生活中树的结构。
在日常的应用中，我们用的更多的是二叉树。
什么叫二叉树呢？
即每个结点不超过2的有序树：
image
其中查找树又是一种特殊的二叉树，遵循左小右大的原则，这样我们在查找数据时会更加的快：
比如我们要查找数字5，先查到的一个数字是2，这个时候左小右大，我们只需要往右边查就可以了，左边就不用管了，相对而言会更加的快些。
总而言之：二叉树是数组和链表的折中方案。
-
它增加删除元素较快，位于数组和链表之间。
-
它查询元素也是较快，位于数组和链表之间。
用现实生活中的例子来理解它们之间的区别：
-
数组就好比一个理科强的学生：他数学100分，但英语只能考50分。
-
链表就好比一个文科强的学生：她英语100分，但数学只能考60分。
-
树结构就好比一个较全面的学生：他数学英语都是80分。
关于树结构还有太多太多，平衡二叉树、红黑树、B+树等 ，在此就不展开讲了，主要是我自己也还没弄懂……
当然数据结构远远没有这么简单，除了这些，也还有表结构，图结构等。今天主要说明这几种简单的数据结构，随着后面的学习会将其逐渐完善。
总结
image
