Deque双向队列之ArrayDeque

 1  /**
 2    * The array in which the elements of the deque are stored.
 3    * The capacity of the deque is the length of this array, which is
 4    * always a power of two. The array is never allowed to become
 5    * full, except transiently within an addX method where it is
 6    * resized (see doubleCapacity) immediately upon becoming full,
 7    * thus avoiding head and tail wrapping around to equal each
 8    * other.  We also guarantee that all array cells not holding
 9    * deque elements are always null.
10    */
11   transient Object[] elements; // non-private to simplify nested class access
12
13   /**
14    * The index of the element at the head of the deque (which is the
15    * element that would be removed by remove() or pop()); or an
16    * arbitrary number equal to tail if the deque is empty.
17    */
18   transient int head;
19
20   /**
21    * The index at which the next element would be added to the tail
22    * of the deque (via addLast(E), add(E), or push(E)).
23    */
24   transient int tail;
25
26   /**
27    * The minimum capacity that we'll use for a newly created deque.
28    * Must be a power of 2.
29    */
30   private static final int MIN_INITIAL_CAPACITY = 8;

 1  /**
 2   * Constructs an empty array deque with an initial capacity
 3   * sufficient to hold 16 elements.
 4   */
 5  public ArrayDeque() {
 6      elements = new Object[16];
 7  }
 8
 9  /**
10   * Constructs an empty array deque with an initial capacity
11   * sufficient to hold the specified number of elements.
12   *
13   * @param numElements  lower bound on initial capacity of the deque
14   */
15  public ArrayDeque(int numElements) {
16      allocateElements(numElements);
17  }
18  /**
19     * Constructs a deque containing the elements of the specified
20     * collection, in the order they are returned by the collection's
21     * iterator.  (The first element returned by the collection's
22     * iterator becomes the first element, or <i>front</i> of the
23     * deque.)
24     *
25     * @param c the collection whose elements are to be placed into the deque
26     * @throws NullPointerException if the specified collection is null
27     */
28    public ArrayDeque(Collection<? extends E> c) {
29        allocateElements(c.size());
30        addAll(c);
31    }

 1  /**
 2   * Inserts the specified element at the end of this deque.
 3   *
 4   * <p>This method is equivalent to {@link #add}.
 5   *
 6   * @param e the element to add
 7   * @throws NullPointerException if the specified element is null
 8   */
 9  public void addLast(E e) {
10      if (e == null)
11          throw new NullPointerException();
12      elements[tail] = e;
13      if ( (tail = (tail + 1) & (elements.length - 1)) == head)
14          doubleCapacity();
15  }
16  /**
17   * Inserts the specified element at the end of this deque.
18   *
19   * @param e the element to add
20   * @return {@code true} (as specified by {@link Deque#offerLast})
21   * @throws NullPointerException if the specified element is null
22   */
23  public boolean offerLast(E e) {
24      addLast(e);
25      return true;
26  }
27  /**
28   * Inserts the specified element at the end of this deque.
29   *
30   * <p>This method is equivalent to {@link #addLast}.
31   *
32   * @param e the element to add
33   * @return {@code true} (as specified by {@link Collection#add})
34   * @throws NullPointerException if the specified element is null
35   */
36  public boolean add(E e) {
37      addLast(e);
38      return true;
39  }  

1      if ( (tail = (tail + 1) & (elements.length - 1)) == head)

 1  /**
 2   * Doubles the capacity of this deque.  Call only when full, i.e.,
 3   * when head and tail have wrapped around to become equal.
 4   */
 5  private void doubleCapacity() {
 6      assert head == tail;
 7      int p = head;
 8      int n = elements.length;
 9      int r = n - p; // number of elements to the right of p
10      int newCapacity = n << 1;
11      if (newCapacity < 0)
12          throw new IllegalStateException("Sorry, deque too big");
13      Object[] a = new Object[newCapacity];
14      System.arraycopy(elements, p, a, 0, r);
15      System.arraycopy(elements, 0, a, r, p);
16      elements = a;
17      head = 0;
18      tail = n;
19  }

 1  public E pollFirst() {
 2      int h = head;
 3      @SuppressWarnings("unchecked")
 4      E result = (E) elements[h];
 5      // Element is null if deque empty
 6      if (result == null)
 7          return null;
 8      elements[h] = null;     // Must null out slot
 9      head = (h + 1) & (elements.length - 1);
10      return result;
11  }

1  /**
2   * @throws NoSuchElementException {@inheritDoc}
3   */
4  public E removeFirst() {
5      E x = pollFirst();
6      if (x == null)
7          throw new NoSuchElementException();
8      return x;
9  }

 1  /**
 2   * Returns an array containing all of the elements in this deque
 3   * in proper sequence (from first to last element).
 4   *
 5   * <p>The returned array will be "safe" in that no references to it are
 6   * maintained by this deque.  (In other words, this method must allocate
 7   * a new array).  The caller is thus free to modify the returned array.
 8   *
 9   * <p>This method acts as bridge between array-based and collection-based
10   * APIs.
11   *
12   * @return an array containing all of the elements in this deque
13   */
14  public Object[] toArray() {
15      return copyElements(new Object[size()]);
16  }