ArrayDeque雙端隊列 使用&實現原理分析_貨運

ArrayDeque雙端隊列 使用&實現原理分析_貨運

※回頭車貨運收費標準

宇安交通關係企業,自成立迄今,即秉持著「以誠待人」、「以實處事」的企業信念

ArrayDeque雙端隊列 使用&實現原理分析

學習Okhttp實現源碼時,發現其任務分發時用到了ArrayDeque。因此了解一下ArrayDeque使用方式實現原理

一、Deque

deque(double-ended queue)雙端隊列,是一種具有隊列和棧的性質的數據結構。
雙端隊列中的元素可以從兩端彈出,其限定插入和刪除操作在表的兩端進行。假設兩端分別為端點A和端點B,在實際應用中:

  • 可以有輸出受限的雙端隊列(即端點A允許插入和刪除,端點B只允許插入的雙端隊列);
  • 可以有輸入受限的雙端隊列(即端點A允許插入和刪除,端點B只允許刪除的雙端隊列);
  • 如果限定雙端隊列從某個端點插入的元素只能從該端點刪除,則該雙端隊列就蛻變為兩個棧底相鄰的棧;

deque(double-ended queue)也是一種隊列,了解deque時首先需要回憶一下queue的使用和實現原理。
對於Queue(先進先出)的詳細使用方式和實現原理,可參考文章:
BlockingQueue使用方式 及 源碼閱讀
https://blog.csdn.net/xiaxl/article/details/80774479

Deque實現了以下功能方法,供開發者使用:

// 源碼來自:android-29/java/util/Deque
public interface Deque<E> extends java.util.Queue<E> {
/**
 * 添加元素
 */
 // 在隊列前邊 添加元素,返回是否添加成功
boolean offerFirst( E e);
// 在隊列後邊 添加元素,返回是否添加成功
boolean offerLast( E e);

// 在隊列前邊 添加元素
void addFirst(E e);
// 在隊列後邊添加元素
void addLast( E e);

/**
 * 刪除元素
 */
 // 刪除第一個元素,返回刪除元素的值;如果元素為null,將返回null;
E pollFirst();
// 刪除最後一個元素,返回刪除元素的值;如果為null,將返回null;
E pollLast();

// 刪除第一個元素,返回刪除元素的值;如果元素為null,將拋出異常;
E removeFirst();
// 刪除最後一個元素,返回刪除元素的值;如果為null,將拋出異常;
E removeLast();

// 刪除第一次出現的指定元素
boolean removeFirstOccurrence( java.lang.Object o);
// 刪除最後一次出現的指定元素
boolean removeLastOccurrence( java.lang.Object o);

/**
 * 取數據
 */
// 獲取第一個元素,沒有返回null;
E peekFirst();
// 獲取最後一個元素,沒有返回null;
E peekLast();

// 獲取第一個元素,如果沒有則拋出異常;
E getFirst();
// 獲取最後一個元素,如果沒有則拋出異常;
E getLast();


/**
 * 隊列方法------------------------------------------
 */
// 向隊列中添加一個元素。若添加成功則返回true;若因為容量限制添加失敗則返回false是。
boolean offer(E e);
// 刪除隊列頭的元素,如果隊列為空,則返回null;
E poll();
// 返回隊列頭的元素,如果隊列為空,則返回null;
E peek();

// 向隊列中添加一個元素。若添加成功則返回true;若因為容量限制添加失敗,則拋出IllegalStateException異常。
boolean add(E e);
// 刪除隊列頭的元素,如果隊列為空,則拋出異常;
E remove();
// 返回隊列頭的元素,如果隊列為空,將拋異常;
E element();

/**
 * 堆棧方法------------------------------------------
 */
// 棧頂添加一個元素
void push( E e);
// 移除棧頂元素,如果棧頂沒有元素將拋出異常
E pop();
}

二、ArrayDeque 源碼學習

2.1、變量說明

// 源碼來自:android-29/java/util/ArrayDeque

// 用數組存放隊列元素;
transient Object[] elements; 
// 頭部index
transient int head;
// 下一個要添加到尾步的index (除tail=0時,當前的尾部為tail-1);
transient int tail;

head 與 tail 對應的index位置示例如下圖所示:

  • addFirst 方法:在隊列前面 添加元素;
    代碼實現中:從數組的末尾向前添加數據,如上圖添加順序為 E1、E2、…;
  • addLast方法:在隊列後面 添加元素;
    代碼實現中:在數組的前邊向後添加數據,如上圖添加順序為 Ea、Eb、…;
  • head 為當前頭部的index;
  • tail 為下一個要添加的尾部的index;

2.2、構造方法

// 源碼來自:android-29/java/util/ArrayDeque

// 構造方法:默認數組長度為8
public ArrayDeque() {
    // 創建一個長度為16的數組
    elements = new Object[16];
}

// 構造方法:根據自定義長度 分配數組空間
public ArrayDeque(int numElements) {
    // 根據輸入長度 分配數組空間
    allocateElements(numElements);
}
// 找到大於需要長度的最小的2的冪整數
private void allocateElements(int numElements) {
	// MIN_INITIAL_CAPACITY為8
    int initialCapacity = MIN_INITIAL_CAPACITY;
	// 假設用戶輸入的為9
    if (numElements >= initialCapacity) {
		// initialCapacity = 9; 
        initialCapacity = numElements;
		// initialCapacity = 9 | ( 9 >>> 1)
		// initialCapacity = ( 1001 ) | ( 0100 ) = 1101 = 13;
        initialCapacity |= (initialCapacity >>>  1);
		// initialCapacity = 13 | ( 13 >>> 2)
		// initialCapacity = ( 1101 ) | ( 0011 ) = 1111 = 15;
        initialCapacity |= (initialCapacity >>>  2);
		// initialCapacity = 15 | ( 15 >>> 4)
		// initialCapacity = ( 1111 ) | ( 0000 ) = 1111 = 15;
        initialCapacity |= (initialCapacity >>>  4);
		// initialCapacity = 15 | ( 15 >>> 8)
		// initialCapacity = ( 1111 ) | ( 0000 ) = 1111 = 15;
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
		// 15+1 = 16;
        initialCapacity++;

        if (initialCapacity < 0)    // Too many elements, must back off
            initialCapacity >>>= 1; // Good luck allocating 2^30 elements
    }
	// 創建數組(數組的長度為:大於需要長度的最小的2的冪整數)
    elements = new Object[initialCapacity];
}

以上兩個構造方法實現中:

  • 第一個構造方法,創建一個默認長度為8的數組;
  • 第二個構造方法,如代碼中註釋舉例,其會通過allocateElements(numElements)將數組的長度定義為2的倍數(找到大於需要長度的最小的2的冪整數);
  • allocateElements(numElements)方法:可以將一個任意的初始值轉化為2^n的值。
    如果本身傳進來的值就是2^n 的值,那麼經過轉化會變成2^(n+1);
    如果傳入的值大於等於2^30,那麼經過轉化會變成負值,即< 0,此時會把初始值設置為2^30, 即最大的容量只有2^30;

2.3、隊列首部添加元素

offerFirst(E e)、addFirst(E e) 源碼實現

// 源碼來自:android-29/java/util/ArrayDeque

//  在隊列前邊 添加元素,返回是否添加成功
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

// 在隊列前邊 添加元素
public void addFirst(E e) {
	// 存入空數據時,拋出異常NullPointerException
    if (e == null)
        throw new NullPointerException();
	// 這樣寫 當head=0時,添加到的位置為elements.length - 1
	// 從數組的末尾 向前 依次添加數據
    elements[head = (head - 1) & (elements.length - 1)] = e;
	// 空間不足
    if (head == tail)
        doubleCapacity(); // 擴容
}

offerFirst(E e)、addFirst(E e) 在數組前面添加元素:源碼實現中,從數組的末尾向前依次添加數據元素

2.4、隊列首部刪除元素

pollFirst()、removeFirst()源碼實現

// 源碼來自:android-29/java/util/ArrayDeque

// 刪除第一個元素,返回刪除元素的值;如果元素為null,將拋出異常;
public E removeFirst() {
    E x = pollFirst();
	// 若為空,則拋出異常;
    if (x == null)
        throw new NoSuchElementException();
    return x;
}
// 刪除第一個元素,返回刪除元素的值;如果元素為null,將返回null;
public E pollFirst() {
	// 數組
    final Object[] elements = this.elements;
	// 頭部index
    final int h = head;
	// 頭部元素
    E result = (E) elements[h];
    // 如果頭部元素為null,則返回null
    if (result != null) {
		// 數據元素出隊列
        elements[h] = null; // Must null out slot
		// 指向下一個元素
        head = (h + 1) & (elements.length - 1);
    }
    return result;
}

執行pollFirst()、removeFirst()方法,進行數據出隊列時,其數據的刪除示意圖如下圖所示:

2.5、隊列尾部添加元素

offerLast(E e)、addLast(E e) 源碼實現

// 源碼來自:android-29/java/util/ArrayDeque

// 在數組后添加元素,返回是否添加成功
public boolean offerLast(E e) {
    addLast(e);
    return true;
}
// 在數組後面添加元素
public void addLast(E e) {
	// 存入空數據時,拋出異常NullPointerException
    if (e == null)
        throw new NullPointerException();
	// 存入數據
    elements[tail] = e;
	// (tail + 1) == head 空間已滿
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
		// 擴容
        doubleCapacity();
}

offerLast(E e)、addLast(E e) 在數組后添加元素: 源碼實現中,從數組的前端向後依次添加數據元素

※智慧手機時代的來臨,RWD網頁設計為架站首選

網動結合了許多網際網路業界的菁英共同研發簡單易操作的架站工具,及時性的更新,為客戶創造出更多的網路商機。

2.6、隊列尾部移除元素

pollLast()、removeLast()源碼實現

// 源碼來自:android-29/java/util/ArrayDeque

// 刪除最後一個元素,返回刪除元素的值;如果為null,將拋出異常;
public E removeLast() {
    E x = pollLast();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}
// 刪除最後一個元素,返回刪除元素的值;如果為null,返回null;
public E pollLast() {
	// 數組元素
    final Object[] elements = this.elements;
	// tail-1
    final int t = (tail - 1) & (elements.length - 1);
    // 獲取當前元素
    E result = (E) elements[t];
    if (result != null) {
		// 當前元素置空
        elements[t] = null;
		// 將tail-1 賦值給 tail
        tail = t;
    }
    return result;
}

執行pollLast()、removeLast()方法,進行數據出隊列時,其數據的刪除示意圖如下圖所示:

2.7、擴容 doubleCapacity()

向數組中添加元素時,若數組容量不足,會調用doubleCapacity()方法,擴容為當前容量的兩倍:

// 源碼來自:android-29/java/util/ArrayDeque

// 空間不足:擴容
private void doubleCapacity() {
    assert head == tail;
	// 頭部 index
    int p = head;
	// 數組長度
    int n = elements.length;
	// 
    int r = n - p;
	// 容量擴展為當前的2倍
    int newCapacity = n << 1;
	// 新的容量超過2^30,拋出異常
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
	// 創建一個新的數組
    Object[] a = new Object[newCapacity];
	// 拷貝原數組從 head位置到結束的數據  
    System.arraycopy(elements, p, a, 0, r);
	// 拷貝原數組從 開始到head的數據  
    System.arraycopy(elements, 0, a, r, p);
	// elements置空,保證其中元素可被垃圾回收
    Arrays.fill(elements, null);
	// elements被重新賦值
    elements = a;
	// header 和tail重新賦值
    head = 0;
    tail = n;
}

擴容后的數組為原始數組空間的兩倍:

三、ArrayDeque 隊列應用

3.1 入隊列

// 向隊列中添加一個元素。若添加成功則返回true;若因為容量限制添加失敗則返回false是。
boolean offer(E e);

ArrayDeque入隊列時:offer會調用offerLast實現入隊列

3.2 出隊列

// 刪除隊列頭的元素,如果隊列為空,則返回null;
E poll();

ArrayDeque出隊列時:poll會調用pollFirst實現出隊列

四、ArrayDeque 堆棧應用

4.1 入堆棧

// 棧頂添加一個元素
void push( E e);

ArrayDeque入堆棧時:push會調用offerLast實現入堆棧

4.2 出堆棧

// 移除棧頂元素,如果棧頂沒有元素將拋出異常
E pop();

ArrayDeque出堆棧時:poll會調用pollFirst實現出堆棧

參考

百度百科deque
https://baike.baidu.com/item/deque/849385?fr=aladdin

========== THE END ==========

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

※評比南投搬家公司費用收費行情懶人包大公開

搬家價格與搬家費用透明合理,不亂收費。本公司提供下列三種搬家計費方案,由資深專業組長到府估價,替客戶量身規劃選擇最經濟節省的計費方式