数据结构——Queue队列

队列
支持FIFO(First Input First Output先进先出),尾部添加，头部删除。类似于生活中的排队。

队列类型：

• 单队列
• 循环队列

单队列
单队列就是常见的队列，每次添加元素都是添加在队尾。

单队列

由上述动画会发现，元素会一直在队后加入，队头拿出去的元素后，会一直空着，这就是单队列的“假溢出”情况。

针对这种情况，解决办法就是后面满了，就再从头开始，也就是头尾相接的循环。这就是 “循环队列” 的概念。

循环队列
循环队列中，
Head= (Tail- size) % size

循环队列

当 Tail > Head 时，队列中元素个数 = Tail - Head;

当 Tail < Head 时，队列中元素分为两部分： size - Head 和 Tail ,也就是 Tail + size - Head 。

Java 集合框架中的队列 Queue
Java 集合中的 Queue 继承自 Collection 接口 ，Deque, LinkedList, PriorityQueue, BlockingQueue 等类都实现了它。 Queue 用来存放 等待处理元素 的集合，这种场景一般用于缓冲、并发访问。 除了继承 Collection 接口的一些方法，Queue 还添加了额外的 添加、删除、查询操作。

添加删除查询操作

Queue方法

• add(E),offer(E)在尾部添加

boolean add(E e);
boolean offer(E e);

共同点：
建议实现类禁止添加 null 元素，否则会报空指针 NullPointerException；
不同点：
add() 方法在添加失败（比如队列已满）时会报 一些运行时错误；
而 offer() 方法即使在添加失败时也不会奔溃，只会返回 false。

• remove(),poll()删除并返回头部

E remove();
E poll();

当队列为空时：
remove() 方法会报 NoSuchElementException 错;
poll() 不会奔溃，只会返回 null。

• element(), peek() 获取但不删除

E element();
E peek();

当队列为空时 element() 抛出异常；
peek() 不会奔溃，只会返回 null。