当前位置:首页 > 知识库 > 正文

java双端队列作用(java三种队列详解)

LinkedBlockingDeque概述

LinkedBlockingDeque是由链表构成的界限可选的双端阻塞队列,支持O(1)的时间复杂度从两端插入和移除元素,如不指定边界,则为Integer.MAX_VALUE。

由一个ReentrantLock保证同步,使用conditions来实现等待通知。

java双端队列作用(java三种队列详解)  第1张

类图结构及重要字段

java双端队列作用(java三种队列详解)  第2张public class LinkedBlockingDeque<E> extends AbstractQueue<E> implements BlockingDeque<E>, java.io.Serializable { private static final long serialVersionUID = -387911632671998426L; /** 双向链表节点 */ static final class Node<E> { E item; Node<E> prev; Node<E> next; Node(E x) { item = x; } } /** * 指向第一个节点 * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first; /** * 指向最后一个节点 * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last; /** 节点数量 */ private transient int count; /** 队列容量 */ private final int capacity; /** 保证同步 */ final ReentrantLock lock = new ReentrantLock(); /** take操作发生的条件 */ private final Condition notEmpty = lock.newCondition(); /** put操作发生的条件 */ private final Condition notFull = lock.newCondition(); }

linkFirst

尝试将节点加入到first之前,更新first,如果插入之后超出容量,返回false。

private boolean linkFirst(Node<E> node) { // assert lock.isHeldByCurrentThread(); if (count >= capacity) return false; Node<E> f = first; node.next = f; first = node; if (last == null) last = node; else f.prev = node; ++count; notEmpty.signal(); return true; }java双端队列作用(java三种队列详解)  第3张

linkLast

在last节点后加入节点node,更新last。如果插入之后超出容量,返回false。

private boolean linkLast(Node<E> node) { // assert lock.isHeldByCurrentThread(); if (count >= capacity) return false; Node<E> l = last; node.prev = l; last = node; if (first == null) first = node; else l.next = node; ++count; notEmpty.signal();// 满足notEmpty条件 return true; }java双端队列作用(java三种队列详解)  第4张

unlinkFirst

移除first节点,并返回其item值,如果队列为空,则返回full。

private E unlinkFirst() { // assert lock.isHeldByCurrentThread(); Node<E> f = first; if (f == null) return null; 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; notFull.signal();// 满足notFull条件 return item; }java双端队列作用(java三种队列详解)  第5张

unlinkLast

移除last节点,并返回其item值,如果队列为空,则返回full。

private E unlinkLast() { // assert lock.isHeldByCurrentThread(); 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; notFull.signal(); // 满足notFull条件 return item; }java双端队列作用(java三种队列详解)  第6张

unlink

移除任意一个节点,注意这里并没有操作x本身的连接,因为它可能仍被iterator使用着。

void unlink(Node<E> x) { // assert lock.isHeldByCurrentThread(); Node<E> p = x.prev; Node<E> n = x.next; // 移除的是first if (p == null) { unlinkFirst(); // 移除的是last } else if (n == null) { unlinkLast(); } else { // 移除的是中间节点 p.next = n; n.prev = p; x.item = null; // Don't mess with x's links. They may still be in use by // an iterator. // 这里x的prev和next指针都没有改变,因为他们可能在被iterator使用 --count; notFull.signal(); } }java双端队列作用(java三种队列详解)  第7张

总结

LinkedBlockingDeque是由链表构成的界限可选的双端阻塞队列,支持O(1)的时间复杂度从两端插入和移除元素,如不指定边界,则为Integer.MAX_VALUE。

由一个ReentrantLock保证同步,使用conditions来实现等待通知。

上面介绍的所有操作基本上就是核心方法啦,诸如putFirst、putLast、takeFirst、takeLast等方法都会调用上面的核心方法,而且实现上面也是比较简单的,就是双端链表的基本操作,不懂的可以画画图帮助理解哈。

微信号:sansui663(长安复制)

发表评论