算法中的基本数据结构，从逻辑上分可划分为两大类：线性结构、非线性结构。
注：线性和非线性，不代表存储结构是线性或是非线性，这只是一种逻辑上的划分，比如可以用数组存储二叉树；一般而言，有前驱和后继的，属线性结构，比如数组和链表。
线性结构
线性结构有：数组、栈、链表、队列；
数组（array）
数组几乎在每种语言入门时都会学习到，这里不再专门介绍；
栈
"栈" 这个名称，可类比于一组物体的堆叠，比如一摞书（更直观的类比，如将子弹压入弹夹，最后压入的最先射出）。
栈也是一种受限的序列，只能够操作栈顶，不管入栈还是出栈，都是在栈顶操作。
计算机科学中，栈 (stack) 是一种抽象数据类型，用于表示元素的集合，具有两种主要操作：
- push, 添加元素到栈的顶端（末尾）；
- pop, 移除栈最顶端（末尾）的元素；
以上两种操作可简单概括为后进先出 (LIFO = last in, first out)；
此外，应有一个 peek 操作用于访问栈当前顶端（末尾）的元素（只返回不弹出）。
队列（queue）
队列，这个名称，可类比为现实生活中的排队（不插队的那种）；
计算机科学中，队列 是一种特殊的抽象数据类型集合，集合中的实体按顺序保存。
和数组不同，队列是一种受限的序列；
受限就受限于它只能操作 队尾和队首，并只能在队尾添加元素，在队首删除元素，不像数组可以任意操作。
队列作为一种常见数据结构，有着非常广泛的应用， 比如消息队列。
队列的基本操作有两种：
向队列的末端位置添加实体，称为入队；
从队列的前端位置移除实体，称为出队。
队列中的元素先进先出 FIFO (first in, first out) ：
FIFO
队列的应用
做过性能优化的朋友，对于 “HTTP 1.1 的队头阻塞问题” 应该不会陌生；
具体来说就是 HTTP2 解决了 HTTP1.1 中的队头阻塞问题。
什么是 HTTP1.1 的队头阻塞问题，以及 HTTP2 怎么解决的，这里简单说下：
其实队头阻塞是一个专有名词，不仅仅在 HTTP 中存在，交换器等其他地方也会涉及这个问题；
实际上引起这个问题的根本原因是使用了队列这种数据结构。
HTTP 协议规定， 对于同一个 tcp 连接，所有的 http1.0 请求放入队列中，只有前一个请求的响应收到了，才能发送下一个请求，这个时候就发生了阻塞，并且这个阻塞主要发生在客户端。
就好比等红绿灯，即使旁边的绿灯亮了，你当前所在的车道依然是红灯，你还是不能走，还是要等着。
HTTP/1.1 的改进
在HTTP/1.0 中每一次请求都需要建立一个 TCP 连接，请求结束后立即断开连接；
在HTTP/1.1 中，每一个连接都默认是长连接 (persistent connection)；
对于同一个 tcp 连接，允许一次发送多个 http1.1 请求，也就是说，不必等前一个响应收到，就可以发送下一个请求了；
这样就解决了 http1.0 的客户端的队头阻塞，这也就是HTTP/1.1中管道 (Pipeline)的概念了。
依然存在的问题
但是，HTTP.1 规定，服务器端的响应（response）要根据请求被接收的顺序排队；
也就是说，先接收到的请求，其对应的响应也要先发送。
这样造成的问题是，如果最先收到的请求的处理时间长的话，响应生成也慢，就会阻塞已经生成了的响应的发送，这也会造成队头阻塞。可见，HTTP1.1 的队头阻塞问题依然没解决，不过是将问题从 客户端 转嫁到了 服务器端。
HTTP/2 相比于 HTTP/1.1 的改进
为了解决HTTP/1.1中的服务端队首阻塞，HTTP/2采用了二进制分帧 和 多路复用 等方法。
帧是HTTP/2数据通信的最小单位。在 HTTP/1.1 中数据包是文本格式，而 HTTP/2 的数据包是二进制格式的，也就是二进制帧。
采用帧的传输方式可以将请求和响应的数据分割得更小，且二进制协议可以被高效解析；
HTTP/2中，同域名下的所有通信都在单个连接上完成，该连接可以承载任意数量的双向数据流；
每个数据流都以消息的形式发送，而消息又由一个或多个帧组成，多个帧之间可以乱序发送，根据帧首部的流标识在客户端重新组装。
多路复用，替代了原来的队列和阻塞机制：
在HTTP/1.1中，并发多个请求需要多个 TCP 链接，且单个域名有 6-8 个 TCP 链接请求的限制（浏览器端做的限制，不同浏览器的数量也可能不同）；
在HTTP/2中，同一域名下的所有通信在单个链接完成，仅占用一个 TCP 链接，且在这一个链接上可以并行请求和响应，互不干扰；
非线性结构
非线性结构有：树、图；
树
树的遍历方式有【前中后序遍历】和层次遍历，很多人对前中后这三种遍历方式的印象比较模糊，其实换个方式就很好理解，也容易记住：
所谓的【前中后】其实指的是遍历时的根节点的位置，其他位置按照先左后右的顺序排列即可。
前序遍历：根左右；
中序遍历：左根右；
后序遍历：左右根；
树的重要性质
1、如果有n个顶点，则有 n-1 条边；
2、任一子节点到达根节点的路径【唯一】，且路径长度为节点所处的深度；
二叉树
二叉树是节点不超过二的树，是树的一种特殊子集，属于被限制的树结构，有意思的是，它却能够表示和实现所有的树；
二叉树是LC的主要考点之一，以下为和其相关的题目列表：
- LC-94.binary-tree-inorder-traversal
- LC-102.binary-tree-level-order-traversal
- LC-103.binary-tree-zigzag-level-order-traversal
- LC-144.binary-tree-preorder-traversal
- LC-145.binary-tree-postorder-traversal
- LC-199.binary-tree-right-side-view
真·二叉树
所有节点的度数只能是偶数，即0或2；
堆
堆，其实是一种优先级队列，一种典型的实现就是二叉堆，也是最常考的类型。
二叉堆的特点
1、最小堆（min heap）：如果P是C的一个父节点，那么P的key或value应小于等于C对应的值；基于这个性质，可以得出结论，堆顶元素一定是最小的；
一般我们可以利用此特性，求最小值或第k小值。
2、最大堆（max heap）：和最小堆相反，P的key或value应大于等于C对应的值。
二叉堆相关考题：
- LC-295.find-median-from-data-stream
注：优先队列不只是【堆】这一种，还要更为复杂的，但原理类似。
二叉查找树
二叉查找树（Binary Search Tree），又叫做 Binary Sort Tree（二叉排序树），俗称，二叉搜索树。
二叉查找树性质如下：
- 若
左子树不为空，则左子树下的所有节点的值，均小于其根节点的值； - 若
右子树不为空，则右子树下的所有节点的值，均大于其根节点的值； - 左右子树也均为二叉查找树；
- 没有键值相等的节点；
对于一个二叉查找树，常规操作有查找、插入、删除、寻找父节点、求最大最小值等。
之所以将其命名为查找树，是因为其非常适合查找。
举个栗子，如下一棵二叉查找树，愈查找节点值小于且最接近 58 的节点，搜索的流程如图：
[图片上传失败...(image-1c4a10-1653623219302)]
二叉查找树还有一个特性是： 中序遍历的结果，是一个有序数组，有时候我们可以利用到这个性质。
LC-相关题目：
- 98.validate-binary-search-tree
二叉平衡树
平衡树是计算机科学中的一类数据结构，是一种改进后的二叉查找树，一般来讲，二叉查找树的查询复杂度取决于目标节点到根节点的距离，即树的深度，因此当节点的深度普遍较大时，查询的时间复杂度也会随之提升。
为了实现更高效的查询，就诞生了平衡树。
这里所说的平衡，指的是所有叶子的深度趋于平衡，广义上指的是在树上所有可能的查找的均摊复杂度更低。
一些数据库的引擎使用的就是这种数据结构，其目标是为了将查询的时间复杂度降到 logn，可以简单理解为，树在数据结果层面实现了二分查找算法。
二叉平衡树的基本操作
- 旋转
- 插入
- 删除
- 查询前驱
- 查询后继
AVL 树（大致了解就好）
AVL树，得名于它的两个发明者的名字首字母，是最早被发明的自平衡二叉查找树，其任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。
AVL树本质上还是一棵二叉搜索树，它的特点是：
1.其本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1（1, 0, -1），所以带有平衡因子 -2 或 2 的节点就会被认为是不平衡的，需要重新平衡这棵树。
也就是说，AVL树，本质上是自带了平衡功能的二叉查找树。
红黑树
又被称为"对称二叉 B 树"，红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中很高效：它可以在 O(logn) 时间内完成查找，插入和删除（n 是树中元素的数目）。
字典树（前缀树）
又称 Trie（[traɪ]） 树，典型应用是统计场景，排序和保存大量的字符串（但并不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树要高。
特性：
- 根节点不包含字符，除根节点外的所有子节点都只包含一个字符；
- 将从根节点到某一子节点的路径上的字符串联起来，为该节点对应的字符串；
- 每个节点的所有子节点包含的字符都不相同。
字典树（前缀树）
LC-相关算法：
- LC-208.implement-trie-prefix-tree
- LC-211.add-and-search-word-data-structure-design
- LC-212.word-search-ii
网友评论