看書上講解OkHttp源碼時候,使用到了Deque,看朋友也都在用,這就有必要好好學習一心
轉自:
http://blog.csdn.net/buaaroid/article/details/51315860
http://blog.csdn.net/Buaaroid/article/details/51315970
說明:
一 隊列:
隊列是一種特殊的線性表，它隻允許在表的前端（front）進行删除操作，而在表的後端（rear）進行插入操作。進行插入操作的端稱為隊尾，進行删除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。
這與我們生活中的隊列是一緻的,前面消費,後邊插入
二 雙端隊列:
雙端隊列,顧名思義,兩端都能操作(操作一下嗎?),兩端都可以進行插入和删除的操作,即:即可在表的前端,進行插入和删除操作,又可以在表後端進行插入和删除操作
三 栗子與應用
在OkHttp3.4.1的源碼中,看到了如下的應用
public final class Dispatcher {
private int maxRequests = 64;
private int maxRequestsPerHost = 5;
/** Executes calls. Created lazily. */
private ExecutorService executorService;
/** Ready async calls in the order they'll be run. */
private final Deque<AsyncCall> readyAsyncCalls = new ArrayDeque<>();
/** Running asynchronous calls. Includes canceled calls that haven't finished yet. */
private final Deque<AsyncCall> runningAsyncCalls = new ArrayDeque<>();
/** Running synchronous calls. Includes canceled calls that haven't finished yet. */
private final Deque<RealCall> runningSyncCalls = new ArrayDeque<>();
public Dispatcher(ExecutorService executorService) {
this.executorService = executorService;
}
可見,OkHttp,用ArrayDeque 作為了請求隊列,下面,我們來介紹ArrayDeque
1 繼承關系
public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable
實作了Deque、Cloneable和Serializable接口。實作Cloneable和Serializable接口的主要目的是為了實作克隆和序列化,
繼承了AbstractCollection 抽象類
2 成員變量:
ArrayDeque 類中,定義了4個成員變量,代碼如下:
/**
* The array in which the elements of the deque are stored.
* The capacity of the deque is the length of this array, which is
* always a power of two. The array is never allowed to become
* full, except transiently within an addX method where it is
* resized (see doubleCapacity) immediately upon becoming full,
* thus avoiding head and tail wrapping around to equal each
* other. We also guarantee that all array cells not holding
* deque elements are always null.
*/
transient Object[] elements; // non-private to simplify nested class access
/**
* The index of the element at the head of the deque (which is the
* element that would be removed by remove() or pop()); or an
* arbitrary number equal to tail if the deque is empty.
*/
transient int head;
/**
* The index at which the next element would be added to the tail
* of the deque (via addLast(E), add(E), or push(E)).
*/
transient int tail;
/**
* The minimum capacity that we'll use for a newly created deque.
* Must be a power of 2.
*/
private static final int MIN_INITIAL_CAPACITY = 8;
-
Object[] elements;
存儲deque元素的數組。
deque的容量是這個數組的長度，它總是2的幂。
該數組永遠不會變為滿，除了在addX方法中暫時調整大小（請參閱doubleCapacity），當它變為滿時，
進而避免頭部和尾部纏繞在彼此相等。
我們也保證所有不帶deque元素的數組單元都是空的。
簡言之: Object[] elements 存儲元素的 數組
-
transient int head;
在隊列head 處的元素的index(索引),即,接下來調用remove() 或 pop()方法來移除的元素的索引,
如果,對列為空,這個值 = tail的值
-
transient int tail;
-
private static final int MIN_INITIAL_CAPACITY = 8;
我們将用于新建立的deque的最小容量。 必須是2的力量。
總結:
其中
elements
是元素集合數組，
head
是指向隊首的下标，
tail
是指向隊尾的下一個位置的下标。
MIN_INITIAL_CAPACITY
定義了在建立隊列是，如果有指定長度，而且指定長度小于
MIN_INITIAL_CAPACITY
，則使用
MIN_INITIAL_CAPACITY
作為數組的最小長度。
3 構造函數:
構造函數有3,
- 1 無參構造:
public ArrayDeque() {
elements = new Object[16];
}
預設元素,數組大小 16
- 2 指定大小的構造:
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
調用了
allocateElements(numElements)
方法,
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// Find the best power of two to hold elements.
// Tests "<=" because arrays aren't kept full.
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1; // Good luck allocating 2^30 elements
}
elements = new Object[initialCapacity];
}
制定了:元素數組的大小,如果傳入的大小,小于
MIN_INITIAL_CAPACITY
，則使用
MIN_INITIAL_CAPACITY
作為數組的最小長度。
- 2 指定元素構造:
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
傳入一個元素集合,這個構造内部完成了:構造Object[] 數組,和填充元素的操作
4 常用方法:
這裡要從Queue接口開始寫起:
轉自 : http://blog.csdn.net/Buaaroid/article/details/51315970
5 . Queue
在java5中新增加了Java.util.Queue接口，用以支援隊列的常見操作。該接口擴充了java.util.Collection接口。
public interface Queue<E> extends Collection<E> {
//...
}
是以除了基本的Collection操作,隊列還支援:插入,提取和檢查操作
- 類結構
| :抛異常: | :傳回特殊值: | |
|---|---|---|
| 插入 | add(e) | offer(e) |
| 移除 | remove() | pool() |
| 檢查 | element() | peek() |
隊列通常（但并非一定）以 FIFO（first in first out 先進先出）的方式排序各個元素。不過優先級隊列和 LIFO（last in first out 後進先出） 隊列（或堆棧）例外，優先級隊列根據提供的比較器或元素的自然順序對元素進行排序，LIFO隊列按 LIFO的方式對元素進行排序。
在 FIFO 隊列中，所有的新元素都插入隊列的末尾，移除元素從隊列頭部移除。
Queue
使用時要盡量避免
Collection
的
add()
和
remove()
方法，而是要使用
offer()
來加入元素，使用
poll()
來擷取并移出元素。它們的優點是通過傳回值可以判斷成功與否，add()和remove()方法在失敗的時候會抛出異常。 如果要使用前端而不移出該元素，使用
element()
或者
peek()
方法。
| 傳回值 | 方法名 | 說明 |
|---|---|---|
| 增加 | ||
| boolean | add(E e) | 是Collection接口裡的方法,将指定元素插入此隊列的tail(如果立即可執行,且不會違反容量限制),在成功時傳回true,如果目前沒有可用空間,則抛出IllegalStateException |
| boolean | offer(E e) | 是Queue接口裡的方法,将指定元素插入此隊列的tail(如果立即可執行,且不會違反容量限制),傳回true,否則傳回false, 當使用有容量限制的隊列時,此方法通常要優于add(E),add(e)方法可能無法插入,抛出異常, |
| 檢查 | ||
| E | element() | 是Queue接口裡的方法,傳回head(隊頭),處的元素,但不移除此元素,如果隊列empty,則抛出異常 |
| E | peek() | 是Queue接口裡的方法,傳回head(隊頭),處的元素,但不移除此元素,如果隊列empty,則傳回null |
| 移除 | ||
| E | remove() | 是Queue接口裡的方法,(注意,Collection裡的remove(E e )方法,是有參的),擷取并移除此隊列的head,如果隊列empty,則抛出異常NoSuchElementException |
| E | poll() | 是Queue接口裡的方法,(注意,Collection裡的remove(E e )方法,是有參的),擷取并移除此隊列的head,如果隊列empty,則傳回null |
說明:
offer 方法可插入一個元素，否則傳回 false。這與 Collection.add 方法不同，該方法隻能通過抛出未經檢查的異常使添加元素失敗。
remove() 和 poll() 方法可移除和傳回隊列的頭。到底從隊列中移除哪個元素是隊列排序政策的功能，而該政策在各種實作中是不同的。remove() 和 poll() 方法僅在隊列為空時其行為有所不同：remove() 方法抛出一個異常，而 poll() 方法則傳回 null。
element() 和 peek() 傳回，但不移除，隊列的頭。
Queue 實作通常不允許插入 null 元素，盡管某些實作（如 LinkedList）并不禁止插入 null。即使在允許 null 的實作中，也不應該将 null 插入到 Queue 中，因為 null 也用作 poll 方法的一個特殊傳回值，表明隊列不包含元素。
值得注意的是LinkedList類實作了Queue接口，是以我們可以把LinkedList當成Queue來用。
private void testDeque() {
Deque<String> tmpDeque = new LinkedList<>();
tmpDeque.offer("Hello");
tmpDeque.offer("World");
tmpDeque.offer("你好!");
Log.d(TAG, "tmpDeque.size():" + tmpDeque.size());
String str = null;
while ((str = tmpDeque.poll()) != null) {
Log.d(TAG, "str : " + str);
}
Log.d(TAG, "tmpDeque.size():" + tmpDeque.size());
}
D/DequeActivity: tmpDeque.size():3
D/DequeActivity: str : Hello
D/DequeActivity: str : World
D/DequeActivity: str : 你好!
D/DequeActivity: tmpDeque.size():0
6 . Deque
public interface Deque<E> extends Queue<E> {
//....
}
Deque 接口繼承了Queue接口,是以支援Queue 的所有操作,間接也支援Collection的是以操作
類節構:
Deque是一個線性 collection，支援在兩端插入和移除元素。
名稱 deque 是“double ended queue（雙端隊列）”的縮寫，通常讀為“deck”。
大多數 Deque 實作對于它們能夠包含的元素數沒有固定限制，但此接口既支援有容量限制的雙端隊列，也支援沒有固定大小限制的雙端隊列。
此接口定義在雙端隊列兩端通路元素的方法。提供插入、移除和檢查元素的方法。因為此接口繼承了隊列接口Queue，是以其每種方法也存在兩種形式：一種形式在操作失敗時抛出異常，另一種形式傳回一個特殊值（null 或 false，具體取決于操作）。
- 将Deque 用作單純的隊列(FIFO,尾進頭出,先進先出)
在将雙端隊列用作隊列時，将得到 FIFO（先進先出）行為。将元素添加到雙端隊列的末尾，從雙端隊列的開頭移除元素。從 Queue 接口繼承的方法完全等效于 Deque 方法，如下表所示：
| Queue的方法 | 等效Deque的方法 | 描述 |
|---|---|---|
| add(E e) | addLast(E e) | 添加至tail,失敗,則抛異常 |
| offer() | offerLast() | 添加至tail,失敗,則傳回false |
| remove() | removeFirst() | 移除head,失敗,則抛異常 |
| poll() | pollFirst() | 移除head,失敗,傳回null |
| element() | getFirst() | 檢查head,不移除,失敗,則抛異常 |
| peek() | peekFirst() | 檢查head,不移除,失敗,則傳回null |
- 将Deque 用作棧(LIFO,頭進頭出,後進先出,比如activity的棧)
在将雙端隊列用作 LIFO（後進先出）堆棧。應優先使用此接口而不是遺留 Stack 類。在将雙端隊列用作堆棧時，元素被推入雙端隊列的開頭并從雙端隊列開頭彈出。堆棧方法完全等效于 Deque 方法，如下表所示：
| 堆棧方法 | 等效Deque的方法 | 描述 |
|---|---|---|
| push(e) | addFirst(e) | 添加至頭部,失敗,則抛異常 |
| offerFirst(e) | 添加至頭部,失敗,則傳回false | |
| pop() | removeFirst() | 移除頭部,失敗,則抛異 |
| pollFirst() | 移除頭部,失敗,則傳回false | |
| peek() | getFirst() | 檢查頭部,失敗,則抛異常 |
| peekFirst() | 檢查頭部,失敗,則傳回null |