又名堆栈，是一种运算受限的线性表
栈和队列是比较常见的受限线性结构
- 后进先出（LIFO last in first out），后进入元素最先弹出栈空间
- 限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。
- 向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素
- 从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素
先进先出（FIFO first in first out）
只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作
进行插入操作的端称为队尾，进行删除操作的端称为队头。
数字越小优先级越高，即优先级数字越小的元素先被处理。这是因为在优先级队列中，我们希望将具有较高优先级的元素（如紧急任务）放在队列的前面，这些元素将更快地得到处理。
数组中的元素在内存中是连续的空间，链表不必是连续的空间
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在 行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间。
数组访问任何一个位置的元素时，都要从头开始访问，无法通过下标直接访问元素
单向链表和双向链表的主要区别在于节点的指向。
单向链表中，每个节点都只有一个指针，指向下一个节点。因此，只能从链表的头节点开始依次遍历每个节点才能找到特定的节点。这也就使得在单向链表中删除一个节点，需要将该节点的前一个节点的 next 指针跳过该节点，指向该节点的下一个节点。而在单向链表中插入或删除节点，需要遍历整个链表寻找正确的位置，因此其时间复杂度为 O(n)。
双向链表中，每个节点有两个指针，分别指向前一个节点和后一个节点。因此，在双向链表中可以从头尾两端开始遍历节点，也可以快速找到某个节点的前后节点。同时，在双向链表中，插入或删除节点只需要调整当前节点的前后指针，使其指向正确的节点即可，因此其时间复杂度为 O(1)。
总的来说，单向链表有一个优势，就是节点存储标识，空间上比双向链表少一半，因为双向链表每个节点都需要额外保存一个指针，占用额外空间。但在操作效率方面，双向链表具有更好的优势，因为它支持双向遍历，而且对于插入和删除操作，具有更好的效率。
计算机科学中，集合是一组可变数量的数据项(也可能是0个)的组合，这些数据项可能共享某些特征，需要以某种操作方式一起进行操作。一般来讲，这些数据项的类型是相同的，或基类相同。列表(或数组)通常不被认为是集合，因为其大小固定，但事实上它常常在实现中作为某些形式的集合使用。
没有顺序，没有重复元素，不能通过下标值进行访问
是根据关键码值(Key value)而直接进行访问的数据结构，通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
没有顺序，不能遍历，key不能重复，不能充分利用所有单元，不能快速找出最大最小值等特殊元素
它是由n(n≥0)个有限节点组成一个具有层次关系的集合。
每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点（r）；除了根节点外，每个子节点可以分为多个不相交的子树（subtree）。
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
节点的度：一个节点含有的子节点的个数称为该节点的度；
树的度：一棵树中，最大的节点的度称为树的度；
叶节点或终端节点：度为0的节点称为叶节点；
非终端节点或分支节点：度不为0的节点；
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
兄弟节点：具有相同父节点的节点互称为兄弟节点；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；
堂兄弟节点：双亲在同一层的节点互为堂兄弟；
节点的祖先：从根到该节点所经分支上的所有节点；
子孙：以某节点为根的子树中任一节点都称为该节点的子孙；
森林：由棵互不相交的树的集合称为森林。
叶节点个数=度为2的非页节点个数+1
无序树：树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树； 有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树； 二叉树：每个节点最多含有两个子树的树称为二叉树； 满二叉树/完美二叉树：叶节点除外的所有节点均含有两个子树的树被称为满二叉树； 完全二叉树：除最后一层外，所有层都是满节点，且最后一层缺右边连续节点的二叉树称为完全二叉树； 哈夫曼树（最优二叉树）：带权路径最短的二叉树称为哈夫曼树或最优二叉树。
二叉搜索树，又称二叉查找树、有序二叉树，是一种特殊的二叉树。它具有以下特点：
- 左子树上所有节点的值均小于它的根节点的值
- 右子树上所有节点的值均大于它的根节点的值
- 左右子树也分别为二叉搜索树（递归定义）
这些特性保证了二叉搜索树中的任何节点，在树中搜索时的时间复杂度为 O(log n)，使得二叉搜索树成为一种非常高效的数据结构。（实际上是二分查找的思想）
二叉搜索树可以支持插入、查找、删除等操作。对于插入一个节点，我们从根节点开始比较，根据节点值大小，分别向左或向右遍历直到找到合适的插入位置。查找和删除操作也是类似的，都需要从根节点开始遍历树，找到对应的节点进行查找或删除。
需要注意的是，二叉搜索树是基于节点值大小实现的，而不是根据节点位置实现的。如果节点值的分布特别不均匀，很可能会导致二叉搜索树退化成链表，使得树的操作变得非常低效。因此，在实际使用二叉搜索树时，需要对节点的值分布进行平衡，常见的平衡二叉搜索树有 AVL 树和红黑树。
数据结构——二叉树先序、中序、后序及层次四种遍历（C语言版）_中序遍历_正弦定理的博客-CSDN博客
- 先序遍历
- 访问根节点
- 先序遍历左子树
- 先序遍历右子树
- 中序遍历
- 中序遍历其左子树
- 访问根节点
- 中序遍历其右子树
中序遍历可以看成，二叉树每个节点，垂直方向投影下来（可以理解为每个节点从最左边开始垂直掉到地上），然后从左往右数，得出的结果便是中序遍历的结果
- 后序遍历
- 后续遍历其左子树
- 后序遍历其右子树
- 访问根节点
如果插入连续数据是有序数据，分布的不均匀，查询效率低下（O(N)），被称为非平衡树
为了能较快操作一棵树，应该保证树总是平衡的，每个节点左右两边的子孙节点数应尽可能相等
是一种自平衡二叉查找树
红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。 在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求: 性质1. 结点是红色或黑色。 性质2. 根结点是黑色。 性质3. 所有叶子都是黑色。（叶子是NIL结点） 性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点） 性质5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
插入节点为N，其父节点为P，祖父节点为G，父节点同级的兄弟节点为U
情况一：新节点N位于树的根上，没有父节点
直接将N红色变换成黑色
情况二：P节点是黑色
尽管新节点N有两个黑色叶子节点（NIL），但是N节点是红色，所以性质5仍然满足（N替换了旧的NIL但是又带来了新的NIL）
情况三：P是红色，U也是红色
PU变黑色，G变红色
情况四：P红色G黑色U黑色且N是左子
对G依次右旋转，P成为G的父节点，交换P和G的颜色
情况五：P红U黑G黑N右子节点
P为中心左旋转，G为中心右旋转，改变颜色
| 符号 | 名称 |
|---|---|
| O(1) | 常数级 |
| O(log(n)) | 对数级 |
| O(n) | 线性级 |
| O(nlog(n)) | 线性和对数乘积 |
| O(n²) | 平方 |
| O(2ⁿ) | 指数 |
推导大O表示法的方式：
- 用常量1取代运行时间中所有加法常量
- 只保留最高阶项
- 如果最高存在且不为1则去除这个项的系数
O(N)< 时间复杂度 <O(N²)
希尔排序的时间复杂度是O(n log n)到O(n^2)，具体取决于选用的间隔序列。希尔排序是一种不稳定的排序算法。虽然其最坏时间复杂度为O(n^2)，但在大多数情况下，它的平均时间复杂度仍然很好，并且比其他O(n^2)的排序算法更快。
O(nlog2n)