java 雙向隊列實現雙端隊列 _實現雙端隊列

文章插圖

文章插圖
【java 雙向隊列實現雙端隊列】LinkedBlockingDeque概述
LinkedBlockingDeque是由鏈表構成的界限可選的雙端阻塞隊列，支持O(1)的時間復雜度從兩端插入和移除元素，如不指定邊界，則為Integer.MAX_VALUE 。
由一個ReentrantLock保證同步，使用conditions來實現等待通知。

類圖結構及重要字段

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;elsef.prev = node;++count;notEmpty.signal();return true;}

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;elsel.next = node;++count;notEmpty.signal();// 滿足notEmpty條件return true;}

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 GCfirst = n;if (n == null)last = null;elsen.prev = null;--count;notFull.signal();// 滿足notFull條件return item;}

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 GClast = p;if (p == null)first = null;elsep.next = null;--count;notFull.signal(); // 滿足notFull條件return item;}

unlink
移除任意一個節點，注意這里并沒有操作x本身的連接，因為它可能仍被iterator使用著。

void unlink(Node<E> x) {// assert lock.isHeldByCurrentThread();Node<E> p = x.prev;Node<E> n = x.next;// 移除的是firstif (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();}}

總結
LinkedBlockingDeque是由鏈表構成的界限可選的雙端阻塞隊列，支持O(1)的時間復雜度從兩端插入和移除元素，如不指定邊界，則為Integer.MAX_VALUE 。
由一個ReentrantLock保證同步，使用conditions來實現等待通知。
上面介紹的所有操作基本上就是核心方法啦，諸如putFirst、putLast、takeFirst、takeLast等方法都會調用上面的核心方法，而且實現上面也是比較簡單的，就是雙端鏈表的基本操作，不懂的可以畫畫圖幫助理解哈。

java 雙向隊列 實現雙端隊列

java 雙向隊列實現雙端隊列