java 双向队列 java双端队列作用

文章插图
LinkedBlockingDeque概述LinkedBlockingDeque是由链表构成的界限可选的双端阻塞队列，支持O(1)的时间复杂度从两端插入和移除元素，如不指定边界，则为Integer.MAX_VALUE 。
由一个ReentrantLock保证同步，使用conditions来实现等待通知。
linkLast在last节点后加入节点node ，更新last 。如果插入之后超出容量，返回false 。

private boolean linkLast(Node node) {http:// assert lock.isHeldByCurrentThread();if (count >= capacity)return false;Node l = last;node.prev = l;last = node;if (first == null)first = node;elsel.next = node;++count;notEmpty.signal();http:// 满足notEmpty条件return true;}

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

private E unlinkFirst() {http:// assert lock.isHeldByCurrentThread();Node f = first;if (f == null)return null;Node n = f.next;E item = f.item;f.item = null;f.next = f; http:// help GCfirst = n;if (n == null)last = null;elsen.prev = null;--count;notFull.signal();http:// 满足notFull条件return item;}

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

void unlink(Node x) {http:// assert lock.isHeldByCurrentThread();Node p = x.prev;Node n = x.next;http:// 移除的是firstif (p == null) {unlinkFirst();http:// 移除的是last} else if (n == null) {unlinkLast();} else {http:// 移除的是中间节点p.next = n;n.prev = p;x.item = null;http:// Don't mess with x's links.They may still be in use byhttp:// an iterator.http:// 这里x的prev和next指针都没有改变 ， 因为他们可能在被iterator使用--count;notFull.signal();}}

总结【java 双向队列 java双端队列作用】LinkedBlockingDeque是由链表构成的界限可选的双端阻塞队列，支持O(1)的时间复杂度从两端插入和移除元素，如不指定边界，则为Integer.MAX_VALUE 。
由一个ReentrantLock保证同步，使用conditions来实现等待通知。
上面介绍的所有操作基本上就是核心方法啦，诸如putFirst、putLast、takeFirst、takeLast等方法都会调用上面的核心方法，而且实现上面也是比较简单的，就是双端链表的基本操作，不懂的可以画画图帮助理解哈。

声明：本文由本站【创业者资源平台】作者编辑发布，更多技术关注万年技术！