Java 容器源码分析之 Deque 与 ArrayDeque（1）

look_w

Queue 也是 Java 集合框架中定义的一种接口，直接继承自 Collection 接口。除了基本的 Collection 接口规定测操作外，Queue 接口还定义一组针对队列的特殊操作。通常来说，Queue 是按照先进先出(FIFO)的方式来管理其中的元素的，但是优先队列是一个例外。
Deque 接口继承自 Queue接口，但 Deque 支持同时从两端添加或移除元素，因此又被成为双端队列。鉴于此，Deque 接口的实现可以被当作 FIFO队列使用，也可以当作LIFO队列（栈）来使用。官方也是推荐使用 Deque 的实现来替代 Stack。
ArrayDeque 是 Deque 接口的一种具体实现，是依赖于可变数组来实现的。ArrayDeque 没有容量限制，可根据需求自动进行扩容。ArrayDeque不支持值为 null 的元素。
下面基于JDK 8中的实现对 ArrayDeque 加以分析。
方法概览

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

public interface Queue<E> extends Collection<E> {     //向队列中插入一个元素，并返回true     //如果队列已满，抛出IllegalStateException异常     boolean add(E e);     //向队列中插入一个元素，并返回true     //如果队列已满，返回false     boolean offer(E e);     //取出队列头部的元素，并从队列中移除     //队列为空，抛出NoSuchElementException异常     E remove();     //取出队列头部的元素，并从队列中移除     //队列为空，返回null     E poll();     //取出队列头部的元素，但并不移除     //如果队列为空，抛出NoSuchElementException异常     E element();     //取出队列头部的元素，但并不移除     //队列为空，返回null     E peek(); }

Deque 提供了双端的插入与移除操作，如下表：
  First Element (Head) Last Element (Tail) Throws exceptionSpecial valueThrows exceptionSpecial valueInsertaddFirst(e)offerFirst(e)addLast(e)offerLast(e)RemoveremoveFirst()pollFirst()removeLast()pollLast()ExaminegetFirst()peekFirst()getLast()peekLast()Deque 和 Queue 方法的的对应关系如下：
Queue MethodEquivalent Deque Methodadd(e)addLast(e)offer(e)offerLast(e)remove()removeFirst()poll()pollFirst()element()getFirst()peek()peekFirst()Deque 和 Stack 方法的对应关系如下：
Stack MethodEquivalent Deque Methodpush(e)addFirst(e)pop()removeFirst()peek()peekFirst()ArrayList 实现了 Deque 接口中的所有方法。因为 ArrayList 会根据需求自动扩充容量，因而在插入元素的时候不会抛出IllegalStateException异常。