什么是双端队列？
双端队列（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 的实现，它还考虑了线程安全相关的东西，这里只是简单的一个实现，了解双端队列的结构和运作方式。
PS: 清山绿水始于尘，博学多识贵于勤。我有酒，你有故事吗？微信公众号：「清尘闲聊」。欢迎一起谈天说地，聊代码。