java-queue(队列)
================

### 1\. 队列

#### 1.1 队列介绍

Queue用于模拟队列这种数据结构，队列通常是指**先进先出**（FIFO）的容器。新元素插入（offer）到队列的尾部，访问元素（poll）操作会返回队列头部的元素。通常，队列不允许随机访问队列中的元素。

#### 1.2 关系图

![1638371649957.png](http://39.107.103.48:8600//blog/admin/png/2021/12/1/1638371649964.png)

#### 1.3 队列种类介绍

##### 1.3.1 双端队列

我们知道，`Queue`是队列，只能一头进，另一头出。

如果把条件放松一下，允许两头都进，两头都出，这种队列叫双端队列（Double Ended Queue），学名 `Deque`。

Java集合提供了接口 `Deque`来实现一个双端队列，它的功能是：

* 既可以添加到队尾，也可以添加到队首；
* 既可以从队首获取，又可以从队尾获取。

##### 1.3.2 阻塞队列

阻塞队列是一个支持两个附加操作的队列：

* 在队列为空时，获取元素的线程会等待队列变为非空；
* 当队列满时，存储元素的线程会等待队列可用。

因此，当一个线程试图对一个已经满了的队列进行入队列操作时，它将会被堵塞，除非有另一个线程做了出队列的操作；同样，当一个线程试图对一个空队列进行出队列操作时，它将会被阻塞，除非有另外一个线程进行了入队列的操作。

##### 1.3.3 非阻塞队列

基于锁的算法会带来一些活跃度失败的风险。如果线程在持有锁的时候因为阻塞I/O、页面错误、或其他原因发生延迟，很可能所有的线程都不能工作了。一个线程的失败或挂起不应该影响其他线程的失败或挂起，这样的算法称为**非阻塞算法**；如果算法的每一个步骤中都有一些线程能够继续执行，那么这样的算法称为**锁自由（lock-free）算法**。\*\*在线程间使用CAS进行协调，这样的算法如果能构建正确的话，它既是非阻塞的，又是锁自由的。\*\*java中提供了基于CAS非阻塞算法实现的队列，比较有代表性的有ConcurrentLinkedQueue和LinkedTransferQueue，它们的性能一般比阻塞队列的好。

#### 1.4 queue常用队列

* **PriorityQueue**：非阻塞、非线程安全、无边界，支持优先级队列实现类。
* **ConcurrentLinkedQueue**：非阻塞、线程安全、无边界，基于链接节点的队列实现类。
* **ArrayBlockingQueue**：阻塞、线程安全、有边界，一旦创建容量不可改变实现类。
* **LinkedBlockingQueue**：阻塞、线程安全、可选有边界，一个由链表结构组成的可选有界阻塞队列实现类，如果未指定容量，那么容量将等于 `Integer.MAX_VALUE`。
* **PriorityBlockingQueue**：阻塞、线程安全、无边界，支持优先级排序的无边界阻塞队列实现类。
* **DelayQueue**：阻塞、线程安全、无边界，使用优先级队列实现的无界阻塞队列实现类，只有在延迟期满时才能从中提取元素。
* **SynchronousQueue**：阻塞、线程安全、无数据队列，不存储元素、没有内部容量的阻塞队列实现类。
* **LinkedBlockingDeque**：阻塞、线程安全、无边界，由链表结构组成的可选范围双向阻塞队列实现类，如果未指定容量，那么容量将等于 `Integer.MAX_VALUE`。
* **ArrayDeque**: 非阻塞、非线程安全、无边界数组双端队列，当用作栈时，性能优于Stack，当用于队列时，性能优于LinkedList

### 2\. 队列详解

#### 2.1 PriorityQueue

PriorityQueue即优先队列，**优先队列的作用是能保证每次取出的元素都是队列中权值最小的**（优先队列每次取最小元素）。这里牵涉到了大小关系，**元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器**（Comparator）。

　　PriorityQueue不允许放入 `null`元素。其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的**小顶堆**（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。

　　**定义一个PriorityQueue的方式有如下几种**：

```java
//创建一个PriorityQueue队列，初始化一个容量为11的且以自然顺序排序元素的优先队列
PriorityQueue<String> queue = new PriorityQueue<String>(); 
//创建一个PriorityQueue队列，初始化指定大小的容量的优先队列，且以自然顺序排列元素
queue = new PriorityQueue<String>(30);
//创建一个PriorityQueue队列，包含collection
queue = new PriorityQueue<String>(new ArrayList<String>());
//创建一个PriorityQueue队列，初始化指定大小(不能少于1)和比较器的优先队列
queue = new PriorityQueue<String>(30, new Comparator<String>(){
    @Override
    public int compare(String o1, String o2) {
        return o1.compareTo(o2);
    }
});
```

PriorityQueue有很多常用方法，add、offer、poll、peek、element、remove、clear、size、isEmpty等，关于其他方法可以查看API。

　　**常用方法说明如下**：

```java
//往优先队列中插入元素，插入元素失败时会抛出异常
boolean add(E e);
//往优先队列中插入元素，插入元素失败时会返回false
boolean offer(E e);
//获取并删除队列的第一个元素或队列头部的元素，删除元素失败时会返回null
E poll();
//获取队列第一个元素或队列头部的元素，不删除队列中的元素，获取不到返回null
E peek();
//获取队列第一个元素或队列头部的元素，不删除队列中的元素，获取不到会抛出异常
E element();
//从队列中删除元素的单个实例
E remove();
//删除优先级队列的所有内容
void clear();
//返回队列中存在的元素数
int size();
//判断改队列是否为空
boolean isEmpty();
```

#### 2.2 ConcurrentLinkedQueue

ConcurrentLinkedQueue是基于链接节点的无界线程安全队列。**此队列按照FIFO（先进先出）原则对元素进行排序**。队列的头部是队列中时间最长的元素，队列的尾部 是队列中时间最短的元素。新的元素插入到队列的尾部，队列获取操作从队列头部获得元素。当**多个线程共享访问一个公共collection时，ConcurrentLinkedQueue是一个恰当的选择**，此队列不允许使用null元素。

　　**定义一个ConcurrentLinkedQueue的方式有如下几种**：

```java

//创建一个ConcurrentLinkedQueue队列
ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<String>();
//将其他类型的集合转为ConcurrentLinkedQueue队列
queue = new ConcurrentLinkedQueue<String>(new ArrayList<String>());
```

　ConcurrentLinkedQueue有很多常用方法，add、offer、poll、peek、remove、clear、size、isEmpty等，关于其他方法可以查看API。

#### 2.3 ArrayBlockingQueue

ArrayBlockingQueue是一个阻塞式的队列，继承自AbstractBlockingQueue,间接的实现了Queue接口和Collection接口。底层以数组的形式保存数据(实际上可看作一个循环数组)。

　　ArrayBlockingQueue通过使用**全局独占锁**实现同时**只能有一个线程进行入队或者出队操作**，有点类似在**方法上添加synchronized**。其中offer、poll操作通过简单的加锁进行入队出队操作，而put、take则使用了条件变量实现如果队列满则等待，如果队列空则等待，然后分别在出队和入队操作中发送信号激活等待线程实现同步。另外相比LinkedBlockingQueue，ArrayBlockingQueue的size操作的结果是精确的，因为计算前加了全局锁。

　　**定义一个ArrayBlockingQueue的方式有如下几种**：

```java
//创建一个ArrayBlockingQueue队列，设置初始容量 
ArrayBlockingQueue<String> queue = new ArrayBlockingQueue<String>(2);
//创建一个ArrayBlockingQueue队列，设置初始容量和是否为公平锁
queue = new ArrayBlockingQueue<String>(2, false);
//设置初始容量和是否为公平锁并且将其他类型的集合转为ArrayBlockingQueue队列
queue = new ArrayBlockingQueue<String>(2, false, new ArrayList<String>());
```

ArrayBlockingQueue有很多常用方法，add、offer、put、poll、take、element、peek、remove、clear、size、isEmpty等，关于其他方法可以查看API。

　　**常用方法说明如下**：

```java
//将指定的元素插入到此队列的尾部，里面调用了offer方法，如果队列满了则抛出异常
boolean add(E e);
//将指定的元素插入到此队列的尾部（如果立即可行且不会超过该队列的容量），在成功时返回 true，如果此队列已满，则返回 false
boolean offer(E e);
//将指定的元素插入此队列的尾部，如果该队列已满则产生阻塞等待，直至可以添加元素为止
void put(E e);
//获取并移除此队列的头，如果此队列为空，则返回 null
E poll();
//获取并移除此队列的头部，如果没有元素则等待，直至获取元素为止
E take();
//获取但不移除此队列的头，如果此队列为空，则返回 null
E peek();
//从此队列中移除指定元素的单个实例
E remove();
```

#### 2.4 LinkedBlockingQueue

LinkedBlockingQueue是一个基于已链接节点的、范围任意的blocking queue。**此队列按FIFO（先进先出）排序元素**。队列的头部 是在队列中时间最长的元素。队列的尾部是在队列中时间最短的元素。新元素插入到队列的尾部，并且队列获取操作会获得位于队列头部的元素。链接队列的吞吐量通常要高于基于数组的队列，但是在大多数并发应用程序中，其可预知的性能要低。

　　LinkedBlockingQueue中也有两个Node分别用来存放首尾节点，并且里面有个初始值为0的原子变量count用来记录队列元素个数，另外里面有两个ReentrantLock的独占锁，分别用来控制元素入队和出队加锁，其中takeLock用来控制同时只有一个线程可以从队列获取元素，其他线程必须等待，putLock控制同时只能有一个线程可以获取锁去添加元素，其他线程必须等待。另外notEmpty和notFull用来实现入队和出队的同步。 另外由于出入队是两个**非公平独占锁**，所以**可以同时又一个线程入队和一个线程出队**，其实这个是个生产者-消费者模型。

　　**定义一个LinkedBlockingQueue的方式有如下几种**：

```java
//创建一个LinkedBlockingQueue队列，初始容量为Integer.MAX_VALUE
LinkedBlockingQueue<String> queue = new LinkedBlockingQueue<String>();
//创建一个LinkedBlockingQueue队列，设置初始容量
queue = new LinkedBlockingQueue<String>(30);
//设置初始容量为Integer.MAX_VALUE并且将其他类型的集合转为LinkedBlockingQueue队列
queue = new LinkedBlockingQueue<String>(new ArrayList<String>());
```

LinkedBlockingQueue有很多常用方法，add、offer、put、poll、take、element、peek、remove、clear、size、isEmpty等，关于其他方法可以查看API。

　　**常用方法说明如下**：

```java
//将对象塞入队列，如果塞入成功返回true, 否则返回异常
boolean add(E e);
//将对象塞入到队列中，如果设置成功返回true, 否则返回false
boolean offer(E e);
//将元素塞入到队列中，如果队列中已经满了，则该方法会一直阻塞，直到队列中有多余的空间
void put(E e);
//从队列中取对象，如果队列中没有对象，线程会一直阻塞，直到队列中有对象，并且该方法取得了该对象
E take();
//在给定的时间里，从队列中获取对象，时间到了直接调用普通的poll方法，为null则直接返回null
E poll(long timeout, TimeUnit unit);
//获取队列中剩余长度
int remainingCapacity();
//从队列中移除指定的值
boolean remove(Object o);
//判断队列中是否包含该对象
public boolean contains(Object o);
//将队列中对象，全部移除，并加到传入集合中
int drainTo(Collection<? super E> c);
```

#### 2.5 PriorityBlockingQueue

　PriorityBlockingQueue是一个支持优先级的无界阻塞队列，虽然此队列逻辑上是无界的，**但是资源被耗尽时试图执行 add 操作也将失败**（导致OutOfMemoryError错误）。**默认情况下元素采用自然顺序升序排列。也可以自定义类实现compareTo()方法来指定元素排序规则，或者初始化PriorityBlockingQueue时，指定构造参数Comparator来对元素进行排序**。但需要注意的是不能保证同优先级元素的顺序。PriorityBlockingQueue也是基于最小二叉堆实现，使用基于CAS实现的自旋锁来控制队列的动态扩容，保证了扩容操作不会阻塞take操作的执行。

　　由于这是一个优先级队列所以有个比较器comparator用来比较元素大小。l\*\*ock独占锁对象用来控制同时只能有一个线程可以进行入队出队操作。\*\*notEmpty条件变量用来实现take方法阻塞模式。这里没有notFull条件变量是因为这里的put操作是非阻塞的，为啥要设计为非阻塞的是因为这是无界队列。

　　**定义一个PriorityBlockingQueue的方式有如下几种**：

```java
//创建一个PriorityBlockingQueue队列，初始容量为11
PriorityBlockingQueue<String> queue = new PriorityBlockingQueue<String>();
//创建一个PriorityBlockingQueue队列，设置初始容量
queue = new PriorityBlockingQueue<String>(12);
//将其他类型的集合转为PriorityBlockingQueue队列
queue = new PriorityBlockingQueue<String>(new ArrayList<String>());
//创建一个PriorityBlockingQueue队列，初始化指定大小和比较器的优先队列
queue = new PriorityBlockingQueue<String>(12, new Comparator<String>(){
    @Override
    public int compare(String o1, String o2) {
        return o1.compareTo(o2);
    }
});
```

　PriorityBlockingQueue有很多常用方法，add、offer、put、poll、take、element、peek、remove、clear、size、isEmpty等，关于其他方法可以查看API。

　　**常用方法说明如下**：

```java
//向此队列添加指定的元素
boolean add(E o);
//将指定的元素插入到优先级队列中
boolean offer(E o);
//将指定的元素添加到优先级队列中
void put(E o);
//检索，但是不移除此队列的头，如果此队列为空，则返回 null
E peek();
//检索并移除此队列的头部，如果此队列中没有任何元素，则等待指定等待的时间（如果有必要）
E poll();
//检索并移除此队列的头部，如果此队列不存在任何元素，则一直等待
E take();
//判断队列中是否包含该对象
boolean contains(Object o);
//移除此队列中所有可用的元素，并将它们添加到给定 collection中
int drainTo(Collection<? super E> c);
```

#### 2.6 DelayQueue

DelayQueue是Delayed元素的一个无界阻塞队列，**只有在延迟期满时才能从中提取元素**。该队列的头部是延迟期满后保存时间最长的Delayed元素。如果延迟都还没有期满，则队列没有头部，并且poll将返回null。

　　DelayQueue中内部使用的是PriorityQueue存放数据，使用ReentrantLock实现线程同步，可知是阻塞队列。另外**队列里面的元素要实现Delayed接口**，一个是获取当前剩余时间的接口，一个是元素比较的接口，因为这个是有优先级的队列。

　　**定义一个DelayQueue的方式有如下几种**：

```java
public DelayQueue() {}
public DelayQueue(Collection<? extends E> c) {
    this.addAll(c);
}
```

DelayQueue有很多常用方法，add、offer、put、poll、take、element、peek、remove、clear、size、isEmpty等，关于其他方法可以查看API。

　　**常用方法说明如下**：

```java
//将指定的元素插入此延迟队列
boolean add(E e);
//将指定的元素插入此延迟队列
boolean offer(E e);
//将指定的元素插入此延迟队列
void put(E e);
//检索但不删除此队列的头，如果此队列为空，则返回null
E peek();
//检索并删除此队列的头， 如果此队列没有延迟过期的元素，则返回null
E poll();
//检索并删除此队列的头，如有必要，请等待直到延迟过期的元素在此队列上可用
E take();
//从指定队列中删除指定元素的单个实例（如果存在），无论它是否已过期
boolean remove(Object o);
//从此队列中删除所有可用的元素，并将它们添加到给定的集合中
int drainTo(Collection<? super E> c);
```

#### 2.7 SynchronousQueue

　SynchronousQueue是一个不存储元素、**没有内部容量的阻塞队列，其中每个插入操作必须等待另一个线程的对应移除操作**，反之亦然。同步队列没有任何内部容量，甚至连一个队列的容量都没有。不能在同步队列上进行peek，因为仅在试图要移除元素时，该元素才存在.除非另一个线程试图移除某个元素，否则也不能（使用任何方法）插入元素。**也不能迭代队列，因为其中没有元素可用于迭代**。队列的头是尝试添加到队列中的首个已排队插入线程的元素。如果没有这样的已排队线程，则没有可用于移除的元素并且 `poll()`将会返回null。对于其他collection方法（例如contains），SynchronousQueue作为一个空collection。

　　对于正在等待的生产者和使用者线程而言，此类**支持可选的公平排序策略，默认情况下不保证这种排序**。但是，使用公平设置为 `true`所构造的队列可保证线程以FIFO的顺序进行访问。

　　**定义一个SynchronousQueue的方式有如下几种**：

```java
//创建一个SynchronousQueue队列，不保证顺序
SynchronousQueue<String> queue = new SynchronousQueue<String>();
//创建一个SynchronousQueue队列，保证顺序
queue = new SynchronousQueue<String>(true);
```

SynchronousQueue有很多常用方法，add、offer、put、poll、take、drainTo等，关于其他方法可以查看API。

　　**常用方法说明如下**：

```java
//如果另一个线程正在等待接收指定的元素，则将其插入此队列
boolean offer(E e);
//将指定的元素添加到此队列，如果有必要，等待另一个线程接收它
void put(E o);
//如果另一个线程当前正在使元素可用，则检索并删除此队列的头部
E poll();
//始终返回null
E peek();
//检索并删除此队列的头，如有必要，等待其他线程将其插入
E take();
//从此队列中删除所有可用的元素，并将它们添加到给定的集合中
int drainTo(Collection<? super E> c);
//始终返回false
boolean contains(Object o);
```

#### 2.8 LinkedBlockingDeque

LinkedBlockingDeque是双向链表实现的双向并发阻塞队列。**该阻塞队列同时支持FIFO和FILO两种操作方式**，即可以从队列的头和尾同时操作(插入/删除)；并且，该阻塞队列是支持线程安全。LinkedBlockingDeque还是**可选容量**的(防止过度膨胀)，即可以指定队列的容量。如果不指定，默认容量大小等于Integer.MAX\_VALUE。

　　**定义一个LinkedBlockingDeque的方式有如下几种**：

```java
//创建一个LinkedBlockingDeque队列，初始容量为Integer.MAX_VALUE
LinkedBlockingDeque<String> queue = new LinkedBlockingDeque<String>();
//创建一个LinkedBlockingDeque队列，设置初始容量
queue = new LinkedBlockingDeque<String>();
//设置初始容量为Integer.MAX_VALUE并且将其他类型的集合转为LinkedBlockingDeque队列
queue = new LinkedBlockingDeque<String>(new ArrayList<String>());
```

LinkedBlockingDeque有很多常用方法，add、addFirst、、offer、put、poll、take、drainTo等，关于其他方法可以查看API。

　　**常用方法说明如下**：

```java
//在此双端队列的末尾插入指定的元素，除非会违反容量限制
boolean add(E e);
//如果可以在不违反容量限制的情况下立即执行此操作，则将指定的元素插入此双端队列的前面，如果当前没有可用空间，则抛出IllegalStateException
void addFirst(E e);
//如果可以立即执行此操作，而不会违反容量限制，则在此双端队列的末尾插入指定的元素，如果当前没有可用空间，则抛出IllegalStateException
void addLast(E e);
//如果可以在不违反容量限制的情况下立即执行操作，则将指定的元素插入此双端队列表示的队列中（换句话说，在此双端队列的末尾），如果成功则返回true，如果当前没有可用空间，则返回 false
boolean offer(E e);
//如果可以立即执行此操作，而不会违反容量限制，则在此双端队列的前面插入指定的元素；如果成功，则返回true；如果当前没有可用空间，则返回false
boolean offerFirst(E e);
//将指定的元素插入此双端队列的前面，如果空间足够，则需要等待指定的等待时间
boolean offerFirst(E e, long timeout, TimeUnit unit);
//如果可以立即执行此操作，而不会违反容量限制，则在此双端队列的末尾插入指定的元素；如果成功，则返回true；如果当前没有可用空间，则返回false
boolean offerLast(E e);
//将指定的元素插入此双端队列表示的队列中（换句话说，在此双端队列的末尾），如有必要，请等待空间变为可用
void put(E e);
//将指定的元素插入此双端队列的前面，如有必要，请等待空间变大
void putFirst(E e);
//将指定的元素插入此双端队列的末尾，如有必要，请等待空间变大
void putLast(E e);
//检索并删除此双端队列表示的队列的头部（换句话说，此双端队列的第一个元素），如果此双端队列为空，则返回 null
E poll();
//检索并删除此双端队列代表的队列的头部（换句话说，此双端队列的第一个元素），如果有必要使元素变为可用，则等待指定的等待时间
E poll(long timeout, TimeUnit unit);
//检索并删除此双端队列的第一个元素，如果此双端队列为空，则返回null
E pollFirst();
//检索并删除此双端队列的第一个元素，并在必要时等待指定的等待时间，以使元素变为可用
E pollFirst(long timeout, TimeUnit unit);
//检索并删除此双端队列的最后一个元素，如果此双端队列为空，则返回null
E pollLast();
//检索并删除此双端队列的最后一个元素，并在必要时等待指定的等待时间，以使元素变为可用
E pollLast(long timeout, TimeUnit unit);
//检索并删除此双端队列代表的队列的头部（换句话说，此双端队列的第一个元素），如有必要，请等待直到某个元素变为可用
E take();
//检索并删除此双端队列的第一个元素，如有必要，请等待直到元素可用
E takeFirst();
//检索并删除此双端队列的最后一个元素，如有必要，请等待直到元素可用
E takeLast();
//检索但不删除此双端队列代表的队列的头（换句话说，此双端队列的第一个元素），如果此双端队列为空，则返回null
E peek();
//检索但不删除此双端队列的第一个元素，如果此双端队列为空，则返回null
E peekFirst();
//检索但不删除此双端队列的最后一个元素，如果此双端队列为空，则返回null
E peekLast();
//检索但不删除此双端队列代表的队列的头
E element();
//检索但不删除此双端队列的第一个元素
E getFirst();
//检索但不删除此双端队列的最后一个元素
E getLast();
//检索并删除此双端队列代表的队列的头部
E remove();
//从此双端队列删除指定元素的第一次出现
boolean remove(Object o);
//检索并删除此双端队列的第一个元素
E removeFirst();
//从此双端队列删除指定元素的第一次出现
boolean removeFirstOccurrence(Object o);
//检索并删除此双端队列的最后一个元素
E removeLast();
//从此双端队列移除最后一次出现的指定元素
boolean removeLastOccurrence(Object o);
//从原子上删除此双端队列中的所有元素
void clear();
//从此队列中删除所有可用的元素，并将它们添加到给定的集合中
int drainTo(Collection<? super E> c);
//从此队列中最多移除给定数量的可用元素，并将它们添加到给定的集合中
int drainTo(Collection<? super E> c, int maxElements);
//从此双端队列表示的堆栈中弹出一个元素
E pop();
//将一个元素压入此双端队列表示的堆栈上
void push(E e);
//此双端队列是否包含指定的元素
boolean    contains(Object o);
//返回此双端队列理想情况下（在没有内存或资源约束的情况下）可以接受而不会阻塞的其他元素的数量
int remainingCapacity();
//返回此双端队列的元素数量
int size();
```

#### 2.9 ArrayDeque（数组双端队列）

非阻塞、非线程安全、无边界数组双端队列，当用作栈时，性能优于Stack，当用于队列时，性能优于LinkedList

**定义一个ArrayDeque的方式有如下几种**：

```java
public ArrayDeque() {  
    elements = (E[]) new Object[16]; // 默认的数组长度大小  
}  
public ArrayDeque(int numElements) {  
    allocateElements(numElements); // 需要的数组长度大小  
}  
public ArrayDeque(Collection<? extends E> c) {  
    allocateElements(c.size()); // 根据集合来分配数组大小  
    addAll(c); // 把集合中元素放到数组中  
} 
```

ArrayDeque有很多常用方法，add、addFirst、、offer、put、poll、take、drainTo等，关于其他方法可以查看API。

　　**常用方法说明如下**：

```java
	//1.添加元素
        addFirst(E e)//在数组前面添加元素
        addLast(E e)//在数组后面添加元素
        offerFirst(E e)// 在数组前面添加元素，并返回是否添加成功
        offerLast(E e)// 在数组后天添加元素，并返回是否添加成功

  //2.删除元素
        removeFirst()//删除第一个元素，并返回删除元素的值,如果元素为null，将抛出异常
        pollFirst()//删除第一个元素，并返回删除元素的值，如果元素为null，将返回null
        removeLast()//删除最后一个元素，并返回删除元素的值，如果为null，将抛出异常
        pollLast()//删除最后一个元素，并返回删除元素的值，如果为null，将返回null
        removeFirstOccurrence(Object o) //删除第一次出现的指定元素
        removeLastOccurrence(Object o) //删除最后一次出现的指定元素
   

   //3.获取元素
        getFirst() //获取第一个元素,如果没有将抛出异常
        getLast() //获取最后一个元素，如果没有将抛出异常
   

    //4.队列操作
        add(E e) //在队列尾部添加一个元素
        offer(E e) //在队列尾部添加一个元素，并返回是否成功
        remove() //删除队列中第一个元素，并返回该元素的值，如果元素为null，将抛出异常(其实底层调用的是removeFirst())
        poll()  //删除队列中第一个元素，并返回该元素的值,如果元素为null，将返回null(其实调用的是pollFirst())
        element() //获取第一个元素，如果没有将抛出异常
        peek() //获取第一个元素，如果返回null
  

    //5.栈操作
        push(E e) //栈顶添加一个元素
        pop(E e) //移除栈顶元素,如果栈顶没有元素将抛出异常
  

    //6.其他
        size() //获取队列中元素个数
        isEmpty() //判断队列是否为空
        iterator() //迭代器，从前向后迭代
        descendingIterator() //迭代器，从后向前迭代
        contain(Object o) //判断队列中是否存在该元素
        toArray() //转成数组
        clear() //清空队列
        clone() //克隆(复制)一个新的队列
```

### 3\. 链接地址

> https://www.liaoxuefeng.com/wiki/1252599548343744/1265122668445536
>
> https://www.cnblogs.com/bl123/p/13879243.html
>
> https://blog.csdn.net/truelove12358/article/details/106424619