背景

数据结构是我们开发过程中最常用到的基本知识，比如表，方法调用栈等等。熟练的掌握基本的数据结构，有助于提升我们对数据的增删查的效率。我在这里简单总结了我们常见的数据结构知识，包括表、栈、队列和二叉树。

表

表的有两种常见的实现方式：数组和链表

结构	优点	缺点
数组实现	get和set调用常数时间	插入和删除代价昂贵
链表实现	插入和删除开下很小	不容易索引，get调用昂贵

栈

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶。对栈的基本操作有push(进栈)和pop(出栈)，前者相当于插入，后者则是删除最后插入的元素。

栈的实现

数组和链表均可实现栈，效率相当。

栈的应用

• 平衡符号

检验是否每件事情都能成对出现。序列[()]是合法的

做一个空栈。读入字符直到文件结尾。如果字符是一个开发符号，则将其推入栈中。如果字符是一个封闭符号，则当栈空时报错。否则，将栈元素弹出。如果弹出的符号不是对应的开发符号，则报错。在文件结尾，如果栈非空则报错。

• 后缀表达式

4.991.06+5.99+6.991.06=

可以书写如下:

4.99 1.065.99+6.00 1.06+

例如: 6 5 2 3 + 8 + 3

读入前4个数字，栈中的值3 2 6 5(栈尾)；
下一个读到”+”号，所以3和2从栈中弹出并且它们的和5被压入栈中，栈中的值5 5 6(栈尾);
接着8进栈，栈中的值8 5 5 6(栈尾)

• 方法调用栈

当调用一个新方法时，主调例程的所有局部变量需要由系统存储起来，否则被调用的新方法将会重写由主调例程的变量所使用的内存。

需要存储的所有重要信息，诸如寄存器的值(对应变量的名字)和返回地址等信息称为活动记录或叫作栈帧

队列

像栈一样，队列也是表。队列是插入在一端进行而删除则在另一端进行。
队列的基本操作是入队，在表的末端插入一个元素。和出队它是删除在表的开头元素

实现

数组和链表均可实现，效率相当。链表实现比较简单。

应用

• 打印机的实现
• 排队买票

二叉树

对于大量的输入数据，链表的线性访问时间太慢，不宜使用，而二叉树的大部分操作运行时间平均为O(logN)。

二叉树是一个树，其中每个节点都不能多于两个的儿子

树的实现是通过链表

二叉树的一种重要的应用是查找

二叉查找树

对于树中的每个节点，它的左子树中所有项的值小于X中的项，而它的右子树中所有的值大于X中的项

此树对于查找效率比较高。

AVL树

AVL树是带有平衡条件的二叉查找树。
一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树
如果打破了平衡，则通过旋转来解决平衡

• 单旋转
• 双旋转

B树

减少高度，增加分支，从而能够减少深度。
阶为M的B树。如5阶B树，即是5个分叉

应用场景:磁盘数据的查找

二叉堆

堆是一棵完全填满的二叉树。例外就是底层，底层上的元素从左到右填入。又称完全二叉树。

完全二叉树可以用一个数组表示而不需要使用链

插入：上滤
删除：下滤

最小堆

最小元素在根上。任意子树也是一个堆，任意节点都小于它的所有后裔。

最大堆

左式堆

对于堆中的每一个节点X，左儿子的零路径长不小于右儿子的零路径长

任一节点X的零路径长npl(X)定义为从X到一个不具有两个儿子的节点的最短路径的长。具有0个或一个儿子的节点的npl为0。

左式堆的基本操作是合并

红黑树

红黑树是AVL树的一种变种。

红黑色是具有下列着色性质的二叉查找树：

• 每一个节点或者着成红色，或者着成黑色
• 根是黑色的
• 如果一个节点是红色的，那么它的子节点必须是黑色的
• 从一个节点到一个null引用的每一条路径必须包含相同数目的黑色节点。

给大家推荐一个iOS高级开发群：624212887！小编也从群中跟大佬交流学习到很多！非常不错，值得入驻提升！