Java数据结构章节第一篇 初识数据结构，了解数组、链表、队列

提莫Teemo。

哈喽大家好，我是提莫。从这一节开始就正式进入数据结构的章节了，本节的内容也比较简单。这一节先来看一下数组、链表、队列和栈这4种结构。在之前的课程中是不是已经说过了数组？这里再来简单的回顾一下数组。

假如这里是我的一块内存，在内存中我声明了一个数组，在这里数组长度是不是为5，一共五个方块。数组有什么特征？它的长度是不是固定的，并且在内存中的位置是连续的。可以看到这五个方块是不是挨着排列的。

它有什么特点？在这里对数组的元素进行查找的时候是不是很快？这里可以根据它的下标01234来找，例如现在要找到下标为4的位置的元素，是不是可以快速定位到这个元素？

但是大家想一下数组这种结构有些什么缺点？例如现在要添加一个元素，之前提到过数组的长度是不是不可变的？所以如果要添加一个元素，它会在内存中再去开辟一块空间出来，长度就是所需要的长度。把原来数组里面的元素给复制过去，在新的位置添加上元素，这是一种场景。

还有种场景是什么？想在数组的中间去添加一个元素，是不是也要开辟一个新的数组空间，把原来的位置的元素复制过去，并且在这里插入元素之后要把后面的元素也复制过去。所以数组里面在数组中间进行插入或者是删除元素，消耗的时间成本是很高的。

说完了数组之后再来看一下第二种数据结构，是链表。跟数组不同的是链表在内存中并不是连续存储的，它可以东一块西一块。这样怎么去找到所有的元素？它可以在每一个节点指向下一个节点，这样即使每一个元素都在内存中的不同位置，但是是不是可以寻着这个线路，然后把你们一一的给找到。

但是大家想一下这种结构有哪些缺点，是不是不能够像数组一样通过索引快速找到某一个元素。例如我现在想找到这一个元素，是不是必须去找到这一个元素，然后通过它来进行向后面的依次寻找才能够找到它。

所以对链表而言查询操作是比较慢的，但是这样也有好处，也就是说在对它的中间元素进行修改的时候需要去复制一个新的链表，然后把它转移过去吗？并不需要，只需要在这里找到一块空间，然后把这一个位置的引用指向它，然后再去指向这一个元素就可以了，只需要改动一个引用就可以，这样是不是非常方便？

所以在链表里面查询比较慢，但是修改删除是很快的，并且链表的大小是不是可以动态的变化，因为它并不是连续的空间，所以当新增元素的时候只需要再去额外的开辟一块空间出来就可以了。

讲完了链表，接下来再来讲一下队列。队列其实是一种很简单的结构，就好像排队一样，当排队的时候是不是排在前面的人最先出去，越是后面排的人就越后出去，所以有一个先进先出的原则。

对于队列而言主要有两个操作，第一个就是入队，从外面进入队列，还有一个操作就是出队，也就是从队列里面出来。给大家演示一下这种入队出队的操作，是不是从这边进去，然后从这边出来。队列既可以使用数组来做它的底层实现，也可以使用链表来做底层实现。

除了队列以外还有一种结构是不是栈？这个栈是一种什么样的结构？其实它就相当于纸盒子，假如这里是一个纸箱，想一下通常在放东西的时候是不是先放进去的东西会被压在最下面，而后放进去的东西是不是在上面？这样在取这个东西的时候是不是从最上面开始取？也就是栈是遵循后进先出的原则。主要有两个操作，一个操作是把元素放进栈里面，这个操作叫压栈。还有一个是从栈里把元素拿出来，这个叫做弹栈。

接下来我来演示一下怎么进行压栈和弹栈。首先把b元素给压栈进去，是不是放入了栈里面？而后面的a元素在压栈的时候会在栈顶，弹栈的时候是不是a元素最先被取出来，接着再使b元素被取出来，这就是后进先出原则。同理栈的底层也可以使用数组或者是链表来实现，这个都是可以的。

这节主要是理解数组、链表、队列跟栈的几个特点，以及数组和链表各有什么优缺点。这一节关于数组、链表、队列和栈就先讲到这里，下一节再见。