看书上讲解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<E> 抽象类

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;

接下来,调用addlast() 或者 add()方法,加入队尾的元素的index(索引)

• 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操作,队列还支持:插入,提取和检查操作

• 类结构

collection类结构.png

Queue类结构.png

队列通常（但并非一定）以 FIFO（first in first out 先进先出）的方式排序各个元素。不过优先级队列和 LIFO（last in first out 后进先出） 队列（或堆栈）例外，优先级队列根据提供的比较器或元素的自然顺序对元素进行排序，LIFO队列按 LIFO的方式对元素进行排序。

在 FIFO 队列中，所有的新元素都插入队列的末尾，移除元素从队列头部移除。

Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。 如果要使用前端而不移出该元素，使用element()或者peek()方法。

说明:

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类结构.png

Deque是一个线性 collection，支持在两端插入和移除元素。
名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。

大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。

deque1.jpg

此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。因为此接口继承了队列接口Queue，所以其每种方法也存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。

• 将Deque 用作单纯的队列(FIFO,尾进头出,先进先出)

在将双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法，如下表所示：

deque2.jpg

• 将Deque 用作栈(LIFO,头进头出,后进先出,比如activity的栈)

在将双端队列用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法，如下表所示：

deque3.jpg