提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

1 栈(stack)

栈的概述

1.栈是一个先进后出的有序列表。

2.栈是限制线性表中的元素的插入和删除只能在线性表的同一端进行的一种特殊的线性表。允许插入删 除的一端，为变化的一端，称为栈顶。另一端，固定不变的称为栈低。

3.根据栈的定义可知，最先放入栈中的元素在栈低，最后放入的元素在栈顶。而删除元素恰好相反，最 后放入的元素最先删除，最先放入的元素最后删除。

栈的模型图：

2 队列(queue)

**队列的概述： **队列是一个有序列表，可以用数组或是链表实现。遵循先进先出的原则。

队列模型图：

3 链表

链表概述：

1.链表是以节点的方式来存储的。

2.每个节点包含data域，next域：指向先一个节点

3.如图：发现链表的节点不一定是连续存储的。

4.链表分带头节点的链表和没有头节点的链表，根据具体情况来区分。

优点： 在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链 表中即可， 删除效率也很好)。

缺点： 在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)

链表模型图：

4 哈希表结构

5 树结构

5.1为什么需要树这种数据结构

1)数组存储方式的分析

优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。

缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低 [示意图]

**2)链式存储方式的分析 **

优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链 表中即可， 删除效率也很好)。

缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历) 【示意图】

**3)树存储方式的分析 **

能提高数据存储，读取的效率, 比如利用 二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度， 同时也可以保证数据的插入，删除，修改的速度。

5.2 二叉树

概述：

1)树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。

2)二叉树的子节点分为左节点和右节点。

3)如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉 树。

4)如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续， 倒数第二层的叶子节点在右边连续，我们称为完全二叉树

5)前序遍历：

前序遍历：先输出父节点，在遍历左子树和右子树

中序遍历：先遍历左子树，在输出父节点，再遍历右子树

后续遍历：先遍历左子树，再遍历右子树，最后输出父节点

示意图：

5.3 红黑树

红黑树规则：

红黑树添加原则：