常见抽象数据类型

一、栈

结构：栈顶、栈底

特点：后进先出。从栈顶压入栈，从栈顶压出栈

二、队列

1、队列

• 结构

  队头、队尾

• 特点

  先进先出。从队尾入队列，从队头出队列

2、双端队列

结构：队头、队尾

特点：队头队尾均可入队/出队

3、优先级队列

三、树

1、树

结构：

• 一种分层的结构，由根节点 + 根节点的子孙节点（子树）组成

重要概念：

• 节点

  根节点、内部节点、外部节点（叶子节点）

  父亲节点、兄弟节点、孩子节点（左孩子、右孩子）

• 边

  一对父子节点(u,v)

• 路径

  指一系列的节点，其中任意两个连续的节点都是一条边

• 深度

  节点祖先的个数，根节点的深度是0

• 高度

  从叶子节点往上数的层数，叶子节点的高度是0

• 层

  同一深度的所有节点位于1层，根节点是第0层

2、二叉树

特点：每个节点最多有两个孩子节点（被称为左孩子或右孩子）

2.1 满二叉树

特点：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。

2.2 完全二叉树

特点：和满二叉树的区别是，它的最后一行可能不是完整的，但绝对是右方的连续部分缺失。即叶子结点只可能在最大的两层出现

2.2.1 堆（headq）

• 特点：

  堆是一颗完全二叉树

  除了根节点之外的每个位置，该位置中存储的键值大于等于其父节点的键值

2、AVL树

3、伸展树

4、(2,4)树

5、红黑树

四、图

1、图

2、无向图

3、有向图

五、映射

1、映射

每个唯一的关键字（key）都被关联到对应的一个值（value）上。这种关系被称为映射（map）或关联数组。

2、哈希表

一种，支持使用键作为索引的结构，语法如M[key]

2.1 哈希函数

哈希函数 h ：将每个键k映射到[0,N-1]区间内的整数，其中N是哈希表桶数组的容量

• 哈希码
• 压缩函数

2.2 桶数组

2.3 负载因子

3、跳跃表

六、集合