什么是双端队列？
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
双端队列
双端队列怎么实现？
双端队列的存储结构
public class LinkedBlockingDeque<E> {
//队头
Node<E> first;
//队尾
Node<E> last;
//元素个数
int count;
static final class Node<E> {
//存储元素
E item;
//上一个元素
Node<E> prev;
//下一个元素
Node<E> next;
}
}
从队头入队
public boolean offerFirst(Node<E> node) {
//头节点临时变量
Node<E> f = first;
//把当前的下一个节点指向头节点
node.next = f;
//更新当前节点为头节点
first = node;
//假如尾节点为空，则把当前节点设置为尾节点
if (last == null)
last = node;
//就把以前的头节点指向当前节点
else
f.prev = node;
//总数加一
++count;
return true;
}
从队头出队
public E pollFirst() {
Node<E> f = first;
//头节点的下一个节点
Node<E> n = f.next;
//获取头节点元素
E item = f.item;
//置空
f.item = null;
//孤立头节点，不指向任何节点
f.next = f; // help GC
//重置头节点
first = n;
//说明是最后一个节点
if (n == null)
last = null;
//否则把头节点的上一个节点置空
else
n.prev = null;
//总数减一
--count;
return item;
}
从队尾入队
public boolean offerLast(Node<E> node) {
//尾节点临时变量
Node<E> l = last;
if (l == null)
return null;
//把当前的上一个节点指向尾节点
node.prev = l;
//更新当前节点为尾节点
last = node;
//假如头节点为空，则把头节点置为当前节点
if (first == null)
first = node;
//否则把临时的尾节点的下一个节点指向当前节点
else
l.next = node;
//总数加一
++count;
return true;
}
从队尾出队
public E pollLast() {
Node<E> l = last;
if (l == null)
return null;
//最后节点的上一个节点
Node<E> p = l.prev;
//获取元素
E item = l.item;
//置空
l.item = null;
//孤立尾节点
l.prev = l; // help GC
//更新尾节点
last = p;
//假如是最后一个元素，置空头节点
if (p == null)
first = null;
//否则置空下一个节点指向
else
p.next = null;
//总数减一
--count;
return item;
}
总结
双端队列其实和队列差不多的，只是更加灵活了，队头和队尾均可进行入队和出队操作。这里是基于链表的双端队列实现，具体详情可查看 JDK 的 LinkedBlockingDeque 的实现，它还考虑了线程安全相关的东西，这里只是简单的一个实现，了解双端队列的结构和运作方式。
