队列（queue）是一种先进先出的数据结构（FIFO, First-In-First-Out），就像大家排队买票一样，先来的先买，没有特殊窗口，也没有 VIP 通道，所有人都一样。队列可以使用链表或数组来实现，队列只允许在后端（tail）插入，在前端（head）删除。
队列的实现方式
队列常见有两种实现方式，一种是使用链表，一种是使用数组。使用单向链表实现队列不会出现溢出的问题，队列长度也没有限制，但删除的时间代价较高，所以我们一般使用双向链表，使用两个指针，一个指向队列的头，一个指向队列的尾，删除的时候只能删除头（head）节点，添加的时候只能在尾部（tail）添加，如下图所示。
队列的链表实现
先来看下队列的链表实现，其实他和我们前面讲的双向链表一样，唯一区别就是不能在中间进行添加和删除操作，并且在队列的两头只能一个添加一个删除，先来看下队列的节点类。
class QueueNode<E> {
E val;// 节点值。
QueueNode pre;// 指向前一个节点。
QueueNode next;// 指向后一个节点。
public QueueNode(E val, QueueNode pre, QueueNode next) {
this.val = val;
this.pre = pre;
this.next = next;
}
}
来看下使用链表实现队列的完整代码，具体的添加和删除细节可以参考下双向链表，这里就不在重复介绍。
public class Queue<E> {
private QueueNode<E> head;// 队列的头。
private QueueNode<E> tail;// 队列的尾。
private int size;// 队列中元素的个数。
// 往队列中添加元素。
public void add(E val) {
if (isEmpty()) {// 如果队列为空。
head = new QueueNode(val, null, null);
tail = head;
} else {// 如果不为空就添加到末尾。
tail = new QueueNode<>(val, tail, null);
tail.pre.next = tail;
}
size++;
}
// 删除队列的头部元素。
public E remove() {
if (isEmpty())// 队列为空，没法删除。
throw new NullPointerException("队列为空");
E res = head.val;
if (size() == 1) {// 只有一个节点，全部删除。
head = null;
tail = null;
} else {// 否则删除头节点。
QueueNode headNext = head.next;
head.next = null;
headNext.pre = null;
head = headNext;
}
size--;
return res;
}
// 获取队列头部元素。
public E top() {
if (isEmpty())
throw new NullPointerException("队列为空");
return head.val;
}
// 队列中元素的个数。
public int size() {
return size;
}
// 队列是否为空。
public boolean isEmpty() {
return size == 0;
}
}
队列的数组实现
除了使用链表实现队列以外，还可以使用数组来实现。使用链表是没有长度限制的，但使用数组需要给一个固定的大小，如果队列满了还会涉及到队列的扩容。使用两个指针，一个指向队列头 head ，一个指向队列尾 tail ，这里我们让 tail 指向下一个可以存放数据的位置，如下图所示。
来看下代码：
public class Queue2<E> {
private final Object[] data; // 队列中存放元素的数组
private final int maxSize;// 队列的最大容量
private int size; // 队列中元素的个数
private int head = 0;// 队列的头，只能删除，指向队列的第一个元素
private int tail = 0; // 队列的尾，只能添加，指向队列最后一个元素的下一个位置
public Queue2(int maxSize) {
if (maxSize <= 0)
throw new IllegalArgumentException("队列容量必须大于0 : " + maxSize);
this.maxSize = maxSize;
data = new Object[this.maxSize];
}
//这地方可以扩容也可以抛异常，为了方便这里我们就不在扩容了，关于扩容，大家可以自己去实现
public void add(E val) {
if (isFull())
throw new IllegalStateException("队列已经满了，无法再加入……");
data[tail++] = val;
size++;
}
// 删除
public E remove() {
if (isEmpty())
throw new IllegalStateException("队列是空的，无法删除……");
E res = (E) data[head];
data[head++] = null;
size--;
return res;
}
// 获取队列头部元素
public E top() {
if (isEmpty())
throw new IllegalStateException("队列为空");
return (E) data[head];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return tail == maxSize;
}
public int size() {
return size;
}
}
| 数组，滚动数组，差分数组，树状数组 | |
| 链单向表，双向链表，循环链表，跳表，异或链表 | |
| 队列，循环队列，双端队列 | |
| 栈 | |
| 散列表 | |
| 二叉树，二叉搜索树，AVL树，红黑树，字典树，哈夫曼树，线段树，笛卡尔树 | |
| 堆 | |
| 图的介绍，图的遍历，Dijkstra算法，Bellman-Ford算法，SPFA算法，Floyd算法，Prim算法，Kruskal算法，Boruvka算法，拓扑排序 |
