源码学习：Java 本地队列 - java.util.Deque

1、接口定义

支持在头尾两端插入和移除元素的线性集合（双端队列：Double Ended Queue，Deque，读音：英[dek]｜美[dɛk] ）。大多数 Deque 实现对于它们可能包含的元素数量没有固定的限制，不过这个接口对容量设限以及没有固定容量限制的那些 Deque 实现都支持。

该接口定义了访问 Deque 两端元素的方法，方法被提供用于插入、提取和检索操作。这些操作方法都以两种形式存在：一种在操作失败时抛出异常，另一种是返回一个特殊值（根据操作的不同，可以是 null 或 false）。后一种形式的插入操作是专门为使用容量设限的 Deque 实现而设计的；在大多数实现中，插入操作不会失败。

这个接口继承了 Queue 接口。当使用 Deque 作为 Queue 队列时，会产生 FIFO （先进先出）行为：元素被添加到 Deque 的尾部，然后从头部移除。从 Queue 接口继承的方法精确地等同于 Deque 方法，如下表所示：

Deque 也可用作 LIFO（后进先出） Stack 堆栈。应该优先使用这个接口，而不是历史遗留的 java.util.Stack 类。当一个 Deque 被用作堆栈时，元素从该 Deque 的头部被压入和弹出。Stack 方法与 Deque 方法完全等价，如下表所示：

请注意，当 Deque 被用作 Queue 队列或 Stack 堆栈时，peek() 方法同样有效；在这两种情况下，元素都是从 Deque 的头部提取的。

这个接口还提供了两个方法来移除内部元素，removeFirstOccurrence() 和 removeLastOccurrence()。

与 java.util.List 接口不同，该接口不支持对元素的索引访问。

虽然 Deque 实现并不严格要求禁止插入 null 元素，但强烈建议这样做。任何允许 null 元素的 Deque 实现的使用者都强烈建议不要利用插入 null 元素的能力。这是因为 null 会被各种方法用作特殊的返回值，以表明 Deque 为空。

Deque 实现通常不定义 equals() 和 hashCode() 的基于元素版本的方法，而是从类 Object 继承基于标识版本的方法。

java.util.Deque 继承于 java.util.Queue 接口，接口继承关系如下图所示：

2、方法声明

1）void addFirst(E e);

• 在不违反容量限制的情况下立即将指定的元素插入到该 Deque 的头部中，当使用容量设限的 Deque 时，通常最好使用 offerFirst() 方法；
• 如果此时由于容量限制（没有可用空间）而不能添加元素，则抛出 java.lang.IllegalStateException；
• 如果指定元素的类阻止将其添加到此队列中，则抛出 java.lang.ClassCastException；
• 如果指定的元素为 null 且该队列不允许 null 元素，则抛出 java.lang.NullPointerException；
• 如果此元素的某些属性阻止将其添加到此队列中，则抛出 java.lang.IllegalArgumentException。

2）void addLast(E e);

• 在不违反容量限制的情况下立即将指定的元素插入到该 Deque 的尾部中，当使用容量设限的 Deque 时，通常最好使用 offerLast() 方法；
• 如果此时由于容量限制（没有可用空间）而不能添加元素，则抛出 java.lang.IllegalStateException；
• 如果指定元素的类阻止将其添加到此队列中，则抛出 java.lang.ClassCastException；
• 如果指定的元素为 null 且该队列不允许 null 元素，则抛出 java.lang.NullPointerException；
• 如果此元素的某些属性阻止将其添加到此队列中，则抛出 java.lang.IllegalArgumentException。

3）boolean offerFirst(E e);

• 将指定的元素插入到 Deque 的头部，除非它违反容量限制，成功时返回 true，否则返回 false。当使用容量设限的队列时，这个方法通常比 addFirst() 更适合使用，因为在不能添加元素时，addFirst() 方法只能抛出异常；
• 如果指定元素的类阻止将其添加到此队列中，则抛出 java.lang.ClassCastException；
• 如果指定的元素为 null 且该队列不允许 null 元素，则抛出 java.lang.NullPointerException；
• 如果此元素的某些属性阻止将其添加到此队列中，则抛出 java.lang.IllegalArgumentException。

4）boolean offerLast(E e);

• 将指定的元素插入到 Deque 的尾部，除非它违反容量限制，成功时返回 true，否则返回 false。当使用容量设限的队列时，这个方法通常比 addLast() 更适合使用，因为在不能添加元素时，addLast() 方法只能抛出异常；
• 如果指定元素的类阻止将其添加到此队列中，则抛出 java.lang.ClassCastException；
• 如果指定的元素为 null 且该队列不允许 null 元素，则抛出 java.lang.NullPointerException；
• 如果此元素的某些属性阻止将其添加到此队列中，则抛出 java.lang.IllegalArgumentException。

5）E removeFirst();

• 检索并移除该 Deque 的第一个元素（头部元素）。此方法与 pollFirst() 的不同之处在于：当该 Deque 为空时，则抛出异常；
• 如果该 Deque 为空，则抛出 java.util.NoSuchElementException。

6）E removeLast();

• 检索并移除该 Deque 的最后一个元素（尾部元素）。此方法与 pollLast() 的不同之处在于：当该 Deque 为空时，则抛出异常；
• 如果该 Deque 为空，则抛出 java.util.NoSuchElementException。

7）E pollFirst();

• 检索并移除该 Deque 的第一个元素（头部元素），如果该 Deque 为空，则返回 null。

8）E pollLast();

• 检索并移除该 Deque 的最后一个元素（尾部元素），如果该 Deque 为空，则返回 null。

9）E getFirst();

• 检索（但并不移除）该 Deque 的第一个元素（头部元素）。此方法与 peekFirst() 的不同之处在于：当该 Deque 为空时，则抛出异常；
• 如果该 Deque 为空，则抛出 java.util.NoSuchElementException。

10）E getLast();

• 检索（但并不移除）该 Deque 的最后一个元素（尾部元素）。此方法与 peekLast() 的不同之处在于：当该 Deque 为空时，则抛出异常；
• 如果该 Deque 为空，则抛出 java.util.NoSuchElementException。

11）E peekFirst();

• 检索（但并不移除）该 Deque 的第一个元素（头部元素），如果该 Deque 为空，则返回 null。

12）E peekLast();

• 检索（但并不移除）该 Deque 的最后一个元素（尾部元素），如果该 Deque 为空，则返回 null。

13）boolean removeFirstOccurrence(Object o);

• 从 Deque 中移除指定元素的第一个匹配项。如果该 Deque 中不包含该元素，则它不会有所改变。更正式地说，即移除第一个满足 (o==null ? e==null : o.equals(e)) 表达式的元素 e（如果存在这样的元素的话）。如果该 Deque 包含指定的元素则移除它并返回 true；
• 如果指定元素的类型与 Deque 不兼容，则抛出 java.lang.ClassCastException（可选）；
• 如果指定的元素是 null，而这个 Deque 是不允许 null 元素的，则抛出 java.lang.NullPointerException（可选）。

注：“可选”指具体的 Deque 实现可根据自己的实现目的而选择合适的策略，或返回此异常，或返回成功。

14）boolean removeLastOccurrence(Object o);

• 从 Deque 中移除指定元素的最后一个匹配项。如果该 Deque 中不包含该元素，则它不会有所改变。更正式地说，即移除最后一个满足 (o==null ? e==null : o.equals(e)) 表达式的元素 e（如果存在这样的元素的话）。如果该 Deque 包含指定的元素则移除它并返回 true；
• 如果指定元素的类型与 Deque 不兼容，则抛出 java.lang.ClassCastException（可选）；
• 如果指定的元素是 null，而这个 Deque 是不允许 null 元素的，则抛出 java.lang.NullPointerException（可选）。

— 以下为 Queue 队列方法 —

15）boolean add(E e);

• 如果可以在不违反容量限制的情况下立即将指定的元素插入到该 Deque 所表示的 Queue 队列中（换句话说，插入到该 Deque 的尾部），则在插入成功时返回 true（如 Collection.add() 所指定的），当使用容量设限的 Deque 时，通常最好使用 offer() 方法。此方法与 addLast() 方法等效；
• 如果此时由于容量限制（没有可用空间）而不能添加元素，则抛出 java.lang.IllegalStateException；
• 如果指定元素的类阻止将其添加到此队列中，则抛出 java.lang.ClassCastException；
• 如果指定的元素为 null 且该队列不允许 null 元素，则抛出 java.lang.NullPointerException；
• 如果此元素的某些属性阻止将其添加到此队列中，则抛出 java.lang.IllegalArgumentException。

16）boolean offer(E e);

• 如果可以在不违反容量限制的情况下立即将指定的元素插入到该 Deque 所表示的 Queue 队列中（换句话说，插入到该 Deque 的尾部），则在插入成功时返回 true，否则返回 false，当使用容量设限的 Deque 时，这个方法通常比 add() 更适合使用，因为在因容量限制（没有可用空间）而不能添加元素时，add() 方法只能抛出异常。此方法与 offerLast() 方法等效；
• 如果指定元素的类阻止将其添加到此队列中，则抛出 java.lang.ClassCastException；
• 如果指定的元素为 null 且该队列不允许 null 元素，则抛出 java.lang.NullPointerException；
• 如果此元素的某些属性阻止将其添加到此队列中，则抛出 java.lang.IllegalArgumentException。

17）E remove();

• 检索并移除此 Deque 所表示的 Queue 队列的头部元素（换句话说，移除该 Deque 的第一个元素），此方法与 poll() 方法的不同之处在于：如果队列为空，则抛出异常。此方法与 removeFirst() 方法等效；
• 如果队列为空，则抛出 java.util.NoSuchElementException。

18）E poll();

• 检索并移除此 Deque 所表示的 Queue 队列的头部元素（换句话说，移除该 Deque 的第一个元素），如果队列为空，返回 null。此方法与 pollFirst() 方法等效。

19）E element();

• 检索（但并不移除）此 Deque 所表示的 Queue 队列的头部元素（换句话说，检索该 Deque 的第一个元素），此方法与 peek() 方法的不同之处在于：如果队列为空，则抛出异常。此方法与 getFirst() 方法等效；
• 如果队列为空，则抛出 java.util.NoSuchElementException。

20）E peek();

• 检索（但并不移除）此 Deque 所表示的 Queue 队列的头部元素（换句话说，检索该 Deque 的第一个元素），如果队列为空，返回 null。此方法与 peekFirst() 方法等效。

— 以下为 Stack 堆栈方法 —

21）void push(E e);

• 在不违反容量限制的情况下立即将一个元素压入到该 Deque 所表示的 Stack 堆栈中（换句话说，压入到该 Deque 的头部）。此方法与 addFirst() 方法等效；
• 如果此时由于容量限制（没有可用空间）而不能添加元素，则抛出 java.lang.IllegalStateException；
• 如果指定元素的类阻止将其添加到此堆栈中，则抛出 java.lang.ClassCastException；
• 如果指定的元素为 null 且该堆栈不允许 null 元素，则抛出 java.lang.NullPointerException；
• 如果此元素的某些属性阻止将其添加到此堆栈中，则抛出 java.lang.IllegalArgumentException。

22）E pop();

• 从这个 Deque 所表示的 Stack 堆栈中弹出一个元素。换句话说，移除并返回该 Deque 的第一个元素。此方法与 removeFirst() 方法等效；
• 如果堆栈为空，则抛出 java.util.NoSuchElementException。

— 以下为 Collection 集合方法 —

23）boolean remove(Object o);

• 从 Deque 中移除指定元素的第一个匹配项。如果该 Deque 中不包含该元素，则它不会有所改变。更正式地说，即移除第一个满足 (o==null ? e==null : o.equals(e)) 表达式的元素 e（如果存在这样的元素的话）。如果该 Deque 包含指定的元素则移除它并返回 true。此方法与 removeFirstOccurrence(Object o) 方法等效；
• 如果指定元素的类型与 Deque 不兼容，则抛出 java.lang.ClassCastException（可选）；
• 如果指定的元素是 null，而这个 Deque 是不允许 null 元素的，则抛出 java.lang.NullPointerException（可选）。

24）boolean contains(Object o);

• 如果 Deque 包含指定的元素时返回 true。更正式地说，当且仅当这个 Deque 至少包含一个满足 (o==null ? e==null : o.equals(e)) 表达式的元素 e 时返回 true；
• 如果指定元素的类型与 Deque 不兼容，则抛出 java.lang.ClassCastException（可选）；
• 如果指定的元素是 null，而这个 Deque 是不允许 null 元素的，则抛出 java.lang.NullPointerException（可选）。

25）public int size();

• 返回 Deque 中包含的元素的数量。

26）Iterator<E> iterator();

• 按照顺序返回 Deque 中所有元素的迭代器，元素将按从头到尾的顺序返回。

27）Iterator<E> descendingIterator();

• 以反向顺序返回该 Deque 中所有元素的迭代器，元素将按从尾到头的顺序返回。