队列(Queue)

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头 （Head/Front）

队列的使用

列表的模拟实现

单链表实现

如果单链表加上一个标记尾节点的引用，入队可以采用尾插法，出队可以采用删除头节点

注意：就算有尾节点的标记，也不能从头节点入队，因为删除还是需要找最后一个节点的前一个节点

双向链表实现

如果是双向链表实现，链表的头和尾都是可以进行入队的

如果是数组去实现队列，怎么去实现

正常的数组是难以实现先进先出的操作，可以通过加入循环来实现，这种队列称作循环队列

循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。 环形队列通常使用数组实现。

问题1：当front与rear相等并且都在0位置是，此时队列为空，那下面这种情况应该怎么判断？

正确判断空和满有三种办法：

1.定义size

2.添加标记，定义boolean元素

3.浪费一个空间（判断rear的下一个是不是front）

这种情况rear的下一个空间是front，rear空间不会存入数据

问题2：rear或者front下标怎么从7位置到0位置的？

（rear+1）%array.length（同时也是向下一个下标移动的方法）

数组下标循环的小技巧

1. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length

2. 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length

设计循环队列

双端队列 (Deque)

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

Deque是一个接口，使用时必须创建LinkedList的对象。（这种一般是链表的双端队列）

在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口

第一行可以当作栈，队列，双端队列（其底层是个数组）

第二行可以当作链表，栈，队列，双端队列

以后用栈或者队列优先用以上两种办法（Stack和ArrayList依然可以用）

用队列实现栈

用两个队列模拟实现栈

用栈实现队列

树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看 起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点

1.有一个特殊的结点，称为根结点，根结点没有前驱结点

2.除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每一个集合Ti (1 <= i <= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继

3.树是递归定义的。

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

树的表现形式

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法， 孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。

二叉树

一棵二叉树是结点的一个有限集合，该集合：

1. 或者为空

2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

3. 二叉树不存在度大于2的结点

4. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

两种特殊的二叉树

1. 满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵 二叉树的层数为K，且结点总数是 ，则它就是满二叉树。

2. 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n 个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完 比特就业课 全二叉树。 要注意的是满二叉

树是一种特殊的完全二叉树。

二叉树的性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)(i>0)个结点

2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是2^(k-1) (k>=0)

3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1

4. 具有n个结点的完全二叉树的深度k为log2的（n+1） 上取整

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i 的结点有：

若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点 若2i+1

若2i+1<n，左孩子序号：2i+1，否则无左孩子

若2i+2<n，右孩子序号：2i+2，否则无右孩子