数据结构

• 数组结构

数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。

示例图：
形象图：

[video(video-523RVe1F-1580798044976)(type-bilibili)(url-https://player.bilibili.com/player.html?aid=66417559&page=6)(image-https://ss.csdn.net/p?http://i0.hdslb.com/bfs/archive/ab2b52b3230a1b956a599778ff9430d5f4c45e62.jpg)(title-)]

优点：

1. 按照索引查询元素速度快
2. 按照索引遍历数组方便

缺点：

1. 数组的大小固定后就无法扩容了
2. 数组只能存储一种类型的数据
3. 添加，删除的操作慢，因为要移动其他的元素。

---

• 栈结构

栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。
栈的特点是：只有一个开口方向，元素只能==先进后出==，从栈顶放入元素的操作叫入栈，取出元素叫出栈。

示例图：

形象图：

那么是不是第一个放进去的书最后一个才能被取出来？而最后放进去的书倒是可以第一个取出来？

栈的结构就像一个集装箱，越先放进去的东西越晚才能拿出来，所以，栈常应用于实现递归功能方面的场景，例如斐波那契数列。

[video(video-kw16NRSr-1580748298497)(type-bilibili)(url-https://player.bilibili.com/player.html?aid=66417559&page=7)(image-https://ss.csdn.net/p?http://i0.hdslb.com/bfs/archive/ab2b52b3230a1b956a599778ff9430d5f4c45e62.jpg)(title-)]

---

• 队列结构

队列与栈相似，也是一种线性表，不同的是队列可以在一端添加元素，在另一端取出元素，也就是：==先进先出==原则。从一端放入元素的操作称为入队，另外一端取出元素称为出队

示例图：

因为队列先进先出的特点，在多线程阻塞队列管理中非常适用。

形象图：

[video(video-nR77T42t-1580748379177)(type-bilibili)(url-https://player.bilibili.com/player.html?aid=66417559&page=13)(image-https://ss.csdn.net/p?http://i0.hdslb.com/bfs/archive/ab2b52b3230a1b956a599778ff9430d5f4c45e62.jpg)(title-)]

---

优先级队列

优先级如字面意义优先，优先级队列的数据都带有优先标记。队列中的数据都会进行比较 优先处理序号排前的数据，其他数据的操作方式和队列结构的处理方式一样。

示例图：

形象图：

[video(video-GpeH4iza-1580748400000)(type-bilibili)(url-https://player.bilibili.com/player.html?aid=66417559&page=18)(image-https://ss.csdn.net/p?http://i0.hdslb.com/bfs/archive/ab2b52b3230a1b956a599778ff9430d5f4c45e62.jpg)(title-)]

---

• 链表结构

链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。

示例图：

形象图：

优点：
链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素；
添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；

缺点：
因为含有大量的指针域，占用空间较大；
查找元素需要遍历链表来查找，非常耗时。

适用场景：
数据量较小，需要频繁增加，删除操作的场景

[video(video-xHpuh4cs-1580796399930)(type-bilibili)(url-https://player.bilibili.com/player.html?aid=66417559&page=21)(image-https://ss.csdn.net/p?http://i0.hdslb.com/bfs/archive/ab2b52b3230a1b956a599778ff9430d5f4c45e62.jpg)(title-)]

---