概述

队列(queue) 是一种 先进先出(FIFO) 的、操作受限的线性表

算法一看就懂之「队列」 - 知乎 (zhihu.com)

队列的主要种类:

[顺序队列](# 1、顺序队列)
[链式队列](# 2、链式队列)
[循环队列](# 3、循环队列)
[优先队列](# 4、优先队列)
[双端队列](# 5、双端队列)
[单调队列](# 6、单调队列)

1、顺序队列

2、链式队列

3、循环队列

4、优先队列

优先队列 - 知乎 (zhihu.com)

5、双端队列

抛砖引玉 | 图解双端队列Deque - 知乎 (zhihu.com)

双端队列又名double ended queue，简称deque，双端队列没有队列和栈这样的限制级，它允许两端进行入队和出队操作，也就是说元素可以从队头出队和入队，也可以从队尾出队和入队。

1	public interface Deque<E> extends Queue<E> {}

Deque是一个双端队列接口，继承自Queue接口，Deque的实现类是LinkedList、ArrayDeque、LinkedBlockingDeque，

其中LinkedList是最常用的。

Deque有三种用途：

普通队列(一端进另一端出):
Queue queue = new LinkedList()或Deque deque = new LinkedList()
双端队列(两端都可进出)
Deque deque = new LinkedList()
堆栈
Deque deque = new LinkedList()

注意：Java堆栈Stack类已经过时，Java官方推荐使用Deque替代Stack使用。Deque堆栈操作方法：push()、pop()、peek()。

此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。插入操作的后一种形式是专为使用有容量限制的 Deque 实现设计的；在大多数实现中，插入操作不能失败。

	第一个元素 (头部)		最后一个元素 (尾部)
	抛出异常	特殊值	抛出异常	特殊值
插入	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
删除	removeFirst()	pollFirst()	removeLast()	pollLast()
检查	getFirst()	peekFirst()	getLast()	peekLast()

Deque 中有下面几种添加元素的方法：

add():可以使用 Deque的addFirst()方法在Deque的头部添加元素, 如果Deque不能添加元素，addFirst()方法会抛异常， offerFirst()方法则返回 false。
addLast()addLast()方法也可以在 Deque的尾部添加元素，这是Deque接口与从Queue接口继承的add（）方法等效
addFirst() 可以使用 Deque的addFirst()方法在Deque的头部添加元素
offer() offer()方法可以在Deque的尾部添加元素，如果元素没满则添加成功返回true，否则返回false
offerFirst() offerFirst()方法是在 Deque 的头部添加元素，如果添加成功返回true，否则返回false
offerLast() offerLast()方法在Deque的尾部添加元素
push()push()方法是在Deque的头部添加元素，如果Deque中的元素满了，则会抛异常，

可以查看Deque中的元素

可以查看Deque中的第一个或者最后一个元素，查看元素意味着获取元素的引用而不是移除元素，有下面几种方法：

peek()peek()返回Deque中的第一个元素并且不删除，如果Deque是空则返回null
peekFirst() peekFirst()方法返回Deque的第一个元素，如果Deque是空则返回null，这和 peek()非常相似
peekLast()peekLast()方法返回最后一个元素，如果Deque是空则返回null
getFirst()getFirst()方法获取Deque的第一个元素并且不删除，如果Deque是空则抛异常
getLast() getLast()获取Deque的最后一个元素，如果Deque是空则返回null

Deque接口扩展(继承)了 Queue 接口。在将双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法，

Queue方法	等效Deque方法
add(e)	addLast(e)
offer(e)	offerLast(e)
remove()	removeFirst()
poll()	pollFirst()
element()	getFirst()
peek()	peekFirst()

双端队列也可用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法，如下表所示：

堆栈方法	等效Deque方法
push(e)	addFirst(e)
pop()	removeFirst()
peek()	peekFirst()

Deque的使用场景
在一般情况，不涉及到并发的情况下，有两个实现类，可根据其自身的特性进行选择，分别是：

LinkedList 大小可变的链表双端队列，允许元素为插入null。
ArrayDeque 大下可变的数组双端队列，不允许插入null。
ConcurrentLinkedDeque 大小可变且线程安全的链表双端队列，非阻塞，不允许插入null。
LinkedBlockingDeque 为线程安全的双端队列，在队列为空的情况下，获取操作将会阻塞，直到有元素添加。

注意：LinkedList 和 ArrayDeque 是线程不安全的容器。

6、单调队列

算法学习笔记(66): 单调队列 - 知乎 (zhihu.com)

单调队列 - OI Wiki (oi-wiki.org)

单调队列是一种主要用于解决滑动窗口类问题的数据结构，

即，在长度为 n 的序列中，求每个长度为 m 的区间的区间最值。它的时间复杂度是 O(n) ，
“单调” 指的是元素的的 “规律”——递增（或递减）
“队列” 指的是元素只能从队头和队尾进行操作

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}

public interface Deque<E> extends Queue<E> {}
public interface Queue<E> extends Collection<E> {}