[数据结构与算法]Queue（单项队列）和Deque（双端队列）的知识点整理

1、Queue（单向队列）

1.1 定义

常见队列就是FIFO（先进先出）队列，可以实现前端删除（peek/pop from front），后端添加（push to back）的功能。

1.2 实现（既可以用数组-顺序队列，也可以用链表-链式队列）

子接口：BlockingQueue

1. Java中的单项队列是用链表实现的；
2. 后面的Deque（双端队列）继承了Queue，是重点，也是一个好东西。
3. Queue本身是一个接口，继承了Collection集合；
4. 其中有基本的队列抽象方法，三类，队尾插入元素，队头取出元素，以及删除队头元素；

方法：抛出异常 / 返回默认值(false / null)
添加元素：add / offer
删除：remove / poll
查找：element / peek

2、Deque（双端队列）

1.1 定义

双端队列，顾名思义，就是不光是FIFO（先进先出），也可以后进先出（LIFO），也有优先级队列。。。

1.2 实现

双端队列（Deque）继承了单向队列（Queue），也继承了其中所有的抽象方法，所以也包括基本队列的增删查方法。

实现类：LinkedList、ArrayDeque、ConcurrentLinkedDeque、LinkedBlockingDeque

1.3 方法

Deque额外实现的方法如下：（首尾均可以增删查）

Deque可以当作Queue使用，即先进先出队列。

Queue可以当作Stack使用。

Deque中额外的方法还有一个删除第一次或者最后一次匹配到的元素。

boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);

参考文献：
1、Queue、Deque、LinkedList、ArrayDeque关系及方法
2、深入理解Java集合之—Deque
3、为什么java不推荐使用vector