数据结构之「双端队列」
什么是双端队列?
双端队列(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:
清山绿水始于尘,博学多识贵于勤。
我有酒,你有故事吗?
微信公众号:「清尘闲聊」。
欢迎一起谈天说地,聊代码。
相关推荐
boneix 2020-10-21
seanzed 2020-10-15
ifconfig 2020-10-14
学留痕 2020-09-20
往后余生 2020-09-17
kka 2020-09-14
redis 2020-09-07
lzccheng 2020-09-06
soyo 2020-08-31
stonerkuang 2020-08-18
LxyPython 2020-08-17
raksmart0 2020-08-17
Lzs 2020-08-14
MrHaoNan 2020-07-31
80530895 2020-07-05
lengyu0 2020-06-28
YarnSup 2020-06-28
huanglianhuabj00 2020-06-27