diff --git a/user/super/com/google/gwt/emul/java/util/ArrayDeque.java b/user/super/com/google/gwt/emul/java/util/ArrayDeque.java
new file mode 100644
index 0000000..619b7e8
--- /dev/null
+++ b/user/super/com/google/gwt/emul/java/util/ArrayDeque.java
@@ -0,0 +1,487 @@
+/*
+ * Copyright 2016 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package java.util;
+
+import static javaemul.internal.InternalPreconditions.checkCriticalElement;
+import static javaemul.internal.InternalPreconditions.checkCriticalNotNull;
+import static javaemul.internal.InternalPreconditions.checkElement;
+import static javaemul.internal.InternalPreconditions.checkState;
+
+import javaemul.internal.ArrayHelper;
+
+/**
+ * A {@link Deque} based on circular buffer that is implemented with an array and head/tail
+ * pointers. Array deques have no capacity restrictions; they grow as necessary to support usage.
+ * Null elements are prohibited. This class is likely to be faster than {@link Stack}
+ * when used as a stack, and faster than {@link LinkedList} when used as a queue.
+ * <a href="https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html">ArrayDeque</a>
+ *
+ * @param <E> the element type.
+ */
+public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable {
+
+  private final class IteratorImpl implements Iterator<E> {
+    /**
+     * Index of element to be returned by subsequent call to next.
+     */
+    private int currentIndex = head;
+
+    /**
+     * Tail recorded at construction (also in remove), to stop
+     * iterator and also to check for comodification.
+     */
+    private int fence = tail;
+
+    /**
+     * Index of element returned by most recent call to next.
+     * Reset to -1 if element is deleted by a call to remove.
+     */
+    private int lastIndex = -1;
+
+    @Override
+    public boolean hasNext() {
+      return currentIndex != fence;
+    }
+
+    @Override
+    public E next() {
+      checkCriticalElement(hasNext());
+
+      E e = array[currentIndex];
+      // OpenJDK ArrayDeque doesn't catch all possible comodifications,
+      // but does catch the ones that corrupt traversal
+      checkConcurrentModification(fence == tail && e != null);
+      lastIndex = currentIndex;
+      currentIndex = (currentIndex + 1) & (array.length - 1);
+      return e;
+    }
+
+    @Override
+    public void remove() {
+      checkState(lastIndex >= 0);
+      checkConcurrentModification(head <= lastIndex && lastIndex < tail);
+
+      if (removeAtIndex(lastIndex) < 0) {
+        // if left-shifted, undo increment in next()
+        currentIndex = (currentIndex - 1) & (array.length - 1);
+        fence = tail;
+      }
+      lastIndex = -1;
+    }
+  }
+
+  private final class DescendingIteratorImpl implements Iterator<E> {
+    private int currentIndex = tail;
+    private int fence = head;
+    private int lastIndex = -1;
+
+    @Override
+    public boolean hasNext() {
+      return currentIndex != fence;
+    }
+
+    @Override
+    public E next() {
+      checkCriticalElement(hasNext());
+
+      currentIndex = (currentIndex - 1) & (array.length - 1);
+      E e = array[currentIndex];
+      checkConcurrentModification(fence == head && e != null);
+      lastIndex = currentIndex;
+      return e;
+    }
+
+    @Override
+    public void remove() {
+      checkState(lastIndex >= 0);
+      checkConcurrentModification(head <= lastIndex && lastIndex < tail);
+
+      if (removeAtIndex(lastIndex) > 0) {
+        // if right-shifted, undo decrement in next()
+        currentIndex = (currentIndex + 1) & (array.length - 1);
+        fence = head;
+      }
+      lastIndex = -1;
+    }
+  }
+
+  /**
+   * 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;
+
+  private static void checkConcurrentModification(boolean expression) {
+    if (!expression) {
+      throw new ConcurrentModificationException();
+    }
+  }
+
+  /**
+   * Returns best power-of-two array length to hold the given number of elements.
+   *
+   * @param numElements the number of elements to hold
+   */
+  @SuppressWarnings("unchecked")
+  private static int nextArrayLength(int numElements) {
+    return nextPowerOfTwo(Math.max(MIN_INITIAL_CAPACITY, numElements));
+  }
+
+  /**
+   * Returns a number that is greater than {@code num} and is a power of two.
+   * If passed {@code num} is not positive integer or next power of two overflows then
+   * returned value is non-positive.
+   * E.g., if num == 32, returns 64. if num == 31, returns 32.
+   *
+   * @param num positive integer.
+   */
+  private static int nextPowerOfTwo(int num) {
+    return Integer.highestOneBit(num) << 1;
+  }
+
+  /**
+   * This field holds a JavaScript array.
+   */
+  @SuppressWarnings("unchecked")
+  private E[] array = (E[]) new Object[MIN_INITIAL_CAPACITY];
+
+  /**
+   * 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.
+   */
+  private 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)).
+   */
+  private int tail;
+
+  public ArrayDeque() {
+  }
+
+  public ArrayDeque(Collection<? extends E> c) {
+    this(c.size());
+    addAll(c);
+  }
+
+  public ArrayDeque(int numElements) {
+    ArrayHelper.setLength(array, nextArrayLength(numElements));
+  }
+
+  @Override
+  public boolean add(E e) {
+    addLast(e);
+    return true;
+  }
+
+  @Override
+  public void addFirst(E e) {
+    checkCriticalNotNull(e);
+
+    head = (head - 1) & (array.length - 1);
+    array[head] = e;
+    ensureCapacity();
+  }
+
+  @Override
+  public void addLast(E e) {
+    checkCriticalNotNull(e);
+
+    array[tail] = e;
+    tail = (tail + 1) & (array.length - 1);
+    ensureCapacity();
+  }
+
+  @SuppressWarnings("unchecked")
+  @Override
+  public void clear() {
+    if (head == tail) {
+      return;
+    }
+
+    array = (E[]) new Object[MIN_INITIAL_CAPACITY];
+    head = 0;
+    tail = 0;
+  }
+
+  public Object clone() {
+    return new ArrayDeque<>(this);
+  }
+
+  @Override
+  public boolean contains(Object o) {
+    return contains(iterator(), o);
+  }
+
+  @Override
+  public Iterator<E> descendingIterator() {
+    return new DescendingIteratorImpl();
+  }
+
+  @Override
+  public E element() {
+    return getFirst();
+  }
+
+  @Override
+  public E getFirst() {
+    E e = peekFirstElement();
+    checkElement(e != null);
+    return e;
+  }
+
+  @Override
+  public E getLast() {
+    E e = peekLastElement();
+    checkElement(e != null);
+    return e;
+  }
+
+  @Override
+  public boolean isEmpty() {
+    return head == tail;
+  }
+
+  @Override
+  public Iterator<E> iterator() {
+    return new IteratorImpl();
+  }
+
+  @Override
+  public boolean offer(E e) {
+    return offerLast(e);
+  }
+
+  @Override
+  public boolean offerFirst(E e) {
+    addFirst(e);
+    return true;
+  }
+
+  @Override
+  public boolean offerLast(E e) {
+    addLast(e);
+    return true;
+  }
+
+  @Override
+  public E peek() {
+    return peekFirst();
+  }
+
+  @Override
+  public E peekFirst() {
+    return peekFirstElement();
+  }
+
+  @Override
+  public E peekLast() {
+    return peekLastElement();
+  }
+
+  @Override
+  public E poll() {
+    return pollFirst();
+  }
+
+  @Override
+  public E pollFirst() {
+    E e = peekFirstElement();
+    if (e == null) {
+      return null;
+    }
+    array[head] = null;
+    head = (head + 1) & (array.length - 1);
+    return e;
+  }
+
+  @Override
+  public E pollLast() {
+    E e = peekLastElement();
+    if (e == null) {
+      return null;
+    }
+    tail = (tail - 1) & (array.length - 1);
+    array[tail] = null;
+    return e;
+  }
+
+  @Override
+  public E pop() {
+    return removeFirst();
+  }
+
+  @Override
+  public void push(E e) {
+    addFirst(e);
+  }
+
+  @Override
+  public E remove() {
+    return removeFirst();
+  }
+
+  @Override
+  public boolean remove(Object o) {
+    return removeFirstOccurrence(o);
+  }
+
+  @Override
+  public E removeFirst() {
+    E e = pollFirst();
+    checkElement(e != null);
+    return e;
+  }
+
+  @Override
+  public boolean removeFirstOccurrence(Object o) {
+    return remove(iterator(), o);
+  }
+
+  @Override
+  public E removeLast() {
+    E e = pollLast();
+    checkElement(e != null);
+    return e;
+  }
+
+  @Override
+  public boolean removeLastOccurrence(Object o) {
+    return remove(descendingIterator(), o);
+  }
+
+  @Override
+  public int size() {
+    return (tail - head) & (array.length - 1);
+  }
+
+  @Override
+  public Spliterator<E> spliterator() {
+    return Spliterators.spliterator(this, Spliterator.NONNULL | Spliterator.ORDERED);
+  }
+
+  @SuppressWarnings("unchecked")
+  @Override
+  public <T> T[] toArray(T[] out) {
+    int size = size();
+    if (out.length < size) {
+      out = ArrayHelper.createFrom(out, size);
+    }
+    Object[] dest = out;
+    final int mask = size - 1;
+    for (int i = head, dstIdx = 0; dstIdx < size; i = (i + 1) & mask, ++dstIdx) {
+      dest[dstIdx] = array[i];
+    }
+    if (out.length > size) {
+      out[size] = null;
+    }
+    return out;
+  }
+
+  private boolean contains(Iterator<E> it, Object o) {
+    if (o == null) {
+      return false;
+    }
+
+    while (it.hasNext()) {
+      if (o.equals(it.next())) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  private boolean remove(Iterator<E> it, Object o) {
+    if (contains(it, o)) {
+      it.remove();
+      return true;
+    }
+    return false;
+  }
+
+  private E peekFirstElement() {
+    return array[head];
+  }
+
+  private E peekLastElement() {
+    return array[(tail - 1) & (array.length - 1)];
+  }
+
+  /**
+   * Increase the capacity of this deque when full, i.e.,
+   * when head and tail have wrapped around to become equal.
+   */
+  private void ensureCapacity() {
+    if (head != tail) {
+      return;
+    }
+
+    int numElements = array.length;
+    int newLength = nextArrayLength(numElements);
+    if (head != 0) {
+      E[] newArray = ArrayHelper.createFrom(array, newLength);
+      array = toArray(newArray);
+    } else {
+      ArrayHelper.setLength(array, newLength);
+    }
+    head = 0;
+    tail = numElements;
+  }
+
+  /**
+   * Removes the element at the specified position in the elements array,
+   * adjusting head and tail as necessary. This results in motion of
+   * elements backwards or forwards in the array.
+   *
+   * @return -1 if elements moved backwards (left-shifted); 1 if forwards (right-shifted).
+   */
+  private int removeAtIndex(int i) {
+    final int mask = array.length - 1;
+    int headDistance = (i - head) & mask;
+    int tailDistance = (tail - i) & mask;
+    if (headDistance >= tailDistance) {
+      shiftLeftAtIndex(i);
+      return -1;
+    } else {
+      shiftRightAtIndex(i);
+      return 1;
+    }
+  }
+
+  private void shiftLeftAtIndex(int i) {
+    final int mask = array.length - 1;
+    tail = (tail - 1) & mask;
+    while (i != tail) {
+      int nextOffset = (i + 1) & mask;
+      array[i] = array[nextOffset];
+      i = nextOffset;
+    }
+    array[tail] = null;
+  }
+
+  private void shiftRightAtIndex(int i) {
+    final int mask = array.length - 1;
+    while (i != head) {
+      int prevOffset = (i - 1) & mask;
+      array[i] = array[prevOffset];
+      i = prevOffset;
+    }
+    array[head] = null;
+    head = (head + 1) & mask;
+  }
+}
diff --git a/user/test/com/google/gwt/emultest/CollectionsSuite.java b/user/test/com/google/gwt/emultest/CollectionsSuite.java
index 6ab5bfa..6d69a38 100644
--- a/user/test/com/google/gwt/emultest/CollectionsSuite.java
+++ b/user/test/com/google/gwt/emultest/CollectionsSuite.java
@@ -15,6 +15,7 @@
  */
 package com.google.gwt.emultest;
 
+import com.google.gwt.emultest.java.util.ArrayDequeTest;
 import com.google.gwt.emultest.java.util.ArrayListTest;
 import com.google.gwt.emultest.java.util.ArraysTest;
 import com.google.gwt.emultest.java.util.BitSetTest;
@@ -48,6 +49,7 @@
     GWTTestSuite suite = new GWTTestSuite("Tests for emulation of Java Collections");
 
     // $JUnit-BEGIN$
+    suite.addTestSuite(ArrayDequeTest.class);
     suite.addTestSuite(ArrayListTest.class);
     suite.addTestSuite(ArraysTest.class);
     suite.addTestSuite(BitSetTest.class);
diff --git a/user/test/com/google/gwt/emultest/java/util/ArrayDequeTest.java b/user/test/com/google/gwt/emultest/java/util/ArrayDequeTest.java
new file mode 100644
index 0000000..9915e2a
--- /dev/null
+++ b/user/test/com/google/gwt/emultest/java/util/ArrayDequeTest.java
@@ -0,0 +1,856 @@
+/*
+ * Copyright 2016 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.emultest.java.util;
+
+import static java.util.Arrays.asList;
+
+import com.google.gwt.core.client.JavaScriptException;
+
+import org.apache.commons.collections.TestCollection;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.ConcurrentModificationException;
+import java.util.Deque;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * Tests ArrayDeque class.
+ */
+public class ArrayDequeTest extends TestCollection {
+
+  public void testAdd() throws Exception {
+    Object o1 = new Object();
+    Object o2 = new Object();
+    Object o3 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    assertTrue(deque.add(o1));
+    checkDequeSizeAndContent(deque, o1);
+    assertTrue(deque.add(o2));
+    checkDequeSizeAndContent(deque, o1, o2);
+    assertTrue(deque.add(o3));
+    checkDequeSizeAndContent(deque, o1, o2, o3);
+
+    try {
+      deque.add(null);
+      fail();
+    } catch (NullPointerException expected) { }
+  }
+
+  public void testAddAll() throws Exception {
+    Object o1 = new Object();
+    Object o2 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    assertTrue(deque.addAll(asList(o1, o2)));
+    checkDequeSizeAndContent(deque, o1, o2);
+
+    try {
+      deque = new ArrayDeque<>();
+      deque.addAll(asList(o1, null, o2));
+      fail();
+    } catch (NullPointerException expected) { }
+  }
+
+  public void testAddFirst() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+    Object o3 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    deque.addFirst(o1);
+    checkDequeSizeAndContent(deque, o1);
+    deque.addFirst(o2);
+    checkDequeSizeAndContent(deque, o2, o1);
+    deque.addFirst(o3);
+    checkDequeSizeAndContent(deque, o3, o2, o1);
+
+    try {
+      deque.addFirst(null);
+      fail();
+    } catch (NullPointerException expected) { }
+  }
+
+  public void testAddLast() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+    Object o3 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    deque.addLast(o1);
+    checkDequeSizeAndContent(deque, o1);
+    deque.addLast(o2);
+    checkDequeSizeAndContent(deque, o1, o2);
+    deque.addLast(o3);
+    checkDequeSizeAndContent(deque, o1, o2, o3);
+
+    try {
+      deque.addLast(null);
+      fail();
+    } catch (NullPointerException expected) { }
+  }
+
+  public void testConstructorFromCollection() {
+    assertEquals(0, new ArrayDeque<>(new ArrayList<>()).size());
+    try {
+      new ArrayDeque<>(null);
+      fail();
+    } catch (NullPointerException expected) {
+      // expected
+    } catch (JavaScriptException expected) {
+      // expected
+    }
+
+    try {
+      new ArrayDeque<>(asList(new Object(), null, new Object()));
+      fail();
+    } catch (NullPointerException expected) { }
+
+    Collection<Object> collection = new ArrayList<>(asList(getFullNonNullElements()));
+    checkDequeSizeAndContent(new ArrayDeque<>(collection), getFullNonNullElements());
+  }
+
+  public void testContains() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+    Object o3 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    assertFalse(deque.contains(o3));
+    assertFalse(deque.contains(null));
+    assertTrue(deque.add(o1));
+    assertTrue(deque.add(o2));
+    assertTrue(deque.add(o1));
+    assertTrue(deque.add(o3));
+    assertTrue(deque.contains(o1));
+    assertTrue(deque.contains(o2));
+    assertTrue(deque.contains(o3));
+    assertFalse(deque.contains(null));
+
+    deque.clear();
+    assertTrue(deque.isEmpty());
+    assertFalse(deque.contains(o1));
+    assertFalse(deque.contains(o2));
+    assertFalse(deque.contains(o3));
+  }
+
+  public void testDescendingIterator() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+    Object o3 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    Iterator<Object> it = deque.descendingIterator();
+    assertFalse(it.hasNext());
+    try {
+      it.next();
+      fail();
+    } catch (NoSuchElementException expected) { }
+
+    deque.add(o1);
+    deque.add(o2);
+    deque.add(o3);
+    it = deque.descendingIterator();
+    assertTrue(it.hasNext());
+    assertEquals(o3, it.next());
+    assertTrue(it.hasNext());
+    assertEquals(o2, it.next());
+    assertTrue(it.hasNext());
+    assertEquals(o1, it.next());
+    assertFalse(it.hasNext());
+    try {
+      it.next();
+      fail();
+    } catch (NoSuchElementException expected) { }
+    checkDequeSizeAndContent(deque, o1, o2, o3);
+
+    deque = new ArrayDeque<>();
+    deque.add(o1);
+    deque.add(o2);
+    deque.add(o3);
+    it = deque.descendingIterator();
+    assertTrue(it.hasNext());
+    assertEquals(o3, it.next());
+    it.remove();
+    assertEquals(2, deque.size());
+    assertTrue(it.hasNext());
+    assertEquals(o2, it.next());
+    assertTrue(it.hasNext());
+    assertEquals(o1, it.next());
+    it.remove();
+    checkDequeSizeAndContent(deque, o2);
+  }
+
+  public void testElement() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    try {
+      deque.element();
+      fail();
+    } catch (NoSuchElementException expected) { }
+
+    deque.add(o1);
+    assertEquals(o1, deque.element());
+    checkDequeSizeAndContent(deque, o1);
+
+    deque.add(o2);
+    assertEquals(o1, deque.element());
+    checkDequeSizeAndContent(deque, o1, o2);
+
+    deque.clear();
+    assertTrue(deque.isEmpty());
+    try {
+      deque.element();
+      fail();
+    } catch (NoSuchElementException expected) { }
+  }
+
+  public void testFailFastIterator() {
+    ArrayDeque<Object> deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+    Iterator<Object> it = deque.iterator();
+    it.next();
+    deque.removeFirst();
+    try {
+      it.next();
+    } catch (ConcurrentModificationException e) {
+      fail();
+    }
+    deque.removeLast();
+    try {
+      it.next();
+      fail();
+    } catch (ConcurrentModificationException expected) { }
+
+    deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+    it = deque.iterator();
+    it.next();
+    deque.clear();
+    try {
+      it.next();
+      fail();
+    } catch (ConcurrentModificationException expected) { }
+
+    deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+    it = deque.iterator();
+    it.next();
+    deque.addFirst(new Object());
+    try {
+      it.next();
+    } catch (ConcurrentModificationException e) {
+      fail();
+    }
+    deque.addLast(new Object());
+    try {
+      it.next();
+      fail();
+    } catch (ConcurrentModificationException expected) { }
+
+    deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+    it = deque.iterator();
+    it.next();
+    it.next();
+    deque.removeFirst();
+    try {
+      it.remove();
+    } catch (ConcurrentModificationException e) {
+      fail();
+    }
+
+    deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+    it = deque.iterator();
+    it.next();
+    it.next();
+    deque.removeFirst();
+    deque.removeFirst();
+    try {
+      it.remove();
+      fail();
+    } catch (ConcurrentModificationException expected) { }
+  }
+
+  public void testFailFastDescendingIterator() {
+    ArrayDeque<Object> deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+    Iterator<Object> it = deque.descendingIterator();
+    it.next();
+    deque.removeLast();
+    try {
+      it.next();
+    } catch (ConcurrentModificationException e) {
+      fail();
+    }
+    deque.removeFirst();
+    try {
+      it.next();
+      fail();
+    } catch (ConcurrentModificationException expected) { }
+
+    deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+    it = deque.descendingIterator();
+    it.next();
+    deque.clear();
+    try {
+      it.next();
+      fail();
+    } catch (ConcurrentModificationException expected) { }
+
+    deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+    it = deque.descendingIterator();
+    it.next();
+    deque.addLast(new Object());
+    try {
+      it.next();
+    } catch (ConcurrentModificationException e) {
+      fail();
+    }
+    deque.addFirst(new Object());
+    try {
+      it.next();
+      fail();
+    } catch (ConcurrentModificationException expected) { }
+
+    deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+    it = deque.descendingIterator();
+    it.next();
+    it.next();
+    deque.removeLast();
+    try {
+      it.remove();
+    } catch (ConcurrentModificationException e) {
+      fail();
+    }
+
+    deque = new ArrayDeque<>(asList(getFullNonNullElements()));
+    it = deque.descendingIterator();
+    it.next();
+    it.next();
+    deque.removeLast();
+    deque.removeLast();
+    try {
+      it.remove();
+      fail();
+    } catch (ConcurrentModificationException expected) { }
+  }
+
+  public void testGetFirst() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    try {
+      deque.getFirst();
+      fail();
+    } catch (NoSuchElementException expected) { }
+
+    deque.add(o1);
+    assertEquals(o1, deque.getFirst());
+    checkDequeSizeAndContent(deque, o1);
+
+    deque.add(o2);
+    assertEquals(o1, deque.getFirst());
+    checkDequeSizeAndContent(deque, o1, o2);
+
+    deque.clear();
+    assertTrue(deque.isEmpty());
+    try {
+      deque.getFirst();
+      fail();
+    } catch (NoSuchElementException expected) { }
+  }
+
+  public void testGetLast() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    try {
+      deque.getLast();
+      fail();
+    } catch (NoSuchElementException expected) { }
+
+    deque.add(o1);
+    assertEquals(o1, deque.getLast());
+    checkDequeSizeAndContent(deque, o1);
+
+    deque.add(o2);
+    assertEquals(o2, deque.getLast());
+    checkDequeSizeAndContent(deque, o1, o2);
+
+    deque.clear();
+    assertTrue(deque.isEmpty());
+    try {
+      deque.getLast();
+      fail();
+    } catch (NoSuchElementException expected) { }
+  }
+
+  public void testOffer() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+    Object o3 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    assertTrue(deque.offer(o1));
+    checkDequeSizeAndContent(deque, o1);
+    assertTrue(deque.offer(o2));
+    checkDequeSizeAndContent(deque, o1, o2);
+    assertTrue(deque.offer(o3));
+    checkDequeSizeAndContent(deque, o1, o2, o3);
+
+    try {
+      deque.offer(null);
+      fail();
+    } catch (NullPointerException expected) { }
+  }
+
+  public void testOfferFirst() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+    Object o3 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    assertTrue(deque.offerFirst(o1));
+    checkDequeSizeAndContent(deque, o1);
+    assertTrue(deque.offerFirst(o2));
+    checkDequeSizeAndContent(deque, o2, o1);
+    assertTrue(deque.offerFirst(o3));
+    checkDequeSizeAndContent(deque, o3, o2, o1);
+
+    try {
+      deque.offerFirst(null);
+      fail();
+    } catch (NullPointerException expected) { }
+  }
+
+  public void testOfferLast() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+    Object o3 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    assertTrue(deque.offerLast(o1));
+    checkDequeSizeAndContent(deque, o1);
+    assertTrue(deque.offerLast(o2));
+    checkDequeSizeAndContent(deque, o1, o2);
+    assertTrue(deque.offerLast(o3));
+    checkDequeSizeAndContent(deque, o1, o2, o3);
+
+    try {
+      deque.offerLast(null);
+      fail();
+    } catch (NullPointerException expected) { }
+  }
+
+  public void testPeek() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+    Object o3 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    assertNull(deque.peek());
+
+    deque.add(o1);
+    assertEquals(o1, deque.peek());
+    checkDequeSizeAndContent(deque, o1);
+
+    deque.add(o2);
+    assertEquals(o1, deque.peek());
+    checkDequeSizeAndContent(deque, o1, o2);
+
+    deque.addFirst(o3);
+    assertEquals(o3, deque.peek());
+    checkDequeSizeAndContent(deque, o3, o1, o2);
+
+    deque.clear();
+    assertTrue(deque.isEmpty());
+    assertNull(deque.peek());
+  }
+
+  public void testPeekFirst() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+    Object o3 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    assertNull(deque.peekFirst());
+
+    deque.add(o1);
+    assertEquals(o1, deque.peekFirst());
+    checkDequeSizeAndContent(deque, o1);
+
+    deque.add(o2);
+    assertEquals(o1, deque.peekFirst());
+    checkDequeSizeAndContent(deque, o1, o2);
+
+    deque.addFirst(o3);
+    assertEquals(o3, deque.peekFirst());
+    checkDequeSizeAndContent(deque, o3, o1, o2);
+
+    deque.clear();
+    assertTrue(deque.isEmpty());
+    assertNull(deque.peekFirst());
+  }
+
+  public void testPeekLast() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+    Object o3 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    assertNull(deque.peekLast());
+
+    deque.add(o1);
+    assertEquals(o1, deque.peekLast());
+    checkDequeSizeAndContent(deque, o1);
+
+    deque.add(o2);
+    assertEquals(o2, deque.peekLast());
+    checkDequeSizeAndContent(deque, o1, o2);
+
+    deque.addFirst(o3);
+    assertEquals(o2, deque.peekLast());
+    checkDequeSizeAndContent(deque, o3, o1, o2);
+
+    deque.clear();
+    assertTrue(deque.isEmpty());
+    assertNull(deque.peekLast());
+  }
+
+  public void testPoll() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    assertNull(deque.poll());
+
+    deque.add(o1);
+    assertEquals(o1, deque.poll());
+    assertTrue(deque.isEmpty());
+
+    deque.add(o1);
+    deque.add(o2);
+    assertEquals(o1, deque.poll());
+    checkDequeSizeAndContent(deque, o2);
+    assertEquals(o2, deque.poll());
+    assertTrue(deque.isEmpty());
+    assertNull(deque.poll());
+  }
+
+  public void testPollFirst() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    assertNull(deque.pollFirst());
+    assertTrue(deque.isEmpty());
+
+    deque.add(o1);
+    assertEquals(o1, deque.pollFirst());
+    assertTrue(deque.isEmpty());
+    assertNull(deque.pollFirst());
+
+    deque.add(o1);
+    deque.add(o2);
+    assertEquals(o1, deque.pollFirst());
+    checkDequeSizeAndContent(deque, o2);
+    assertEquals(o2, deque.pollFirst());
+    assertTrue(deque.isEmpty());
+    assertNull(deque.pollFirst());
+  }
+
+  public void testPollLast() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    assertNull(deque.pollLast());
+    assertTrue(deque.isEmpty());
+
+    deque.add(o1);
+    assertEquals(o1, deque.pollLast());
+    assertTrue(deque.isEmpty());
+    assertNull(deque.pollFirst());
+
+    deque.add(o1);
+    deque.add(o2);
+    assertEquals(o2, deque.pollLast());
+    checkDequeSizeAndContent(deque, o1);
+    assertEquals(o1, deque.pollLast());
+    assertTrue(deque.isEmpty());
+    assertNull(deque.pollLast());
+  }
+
+  public void testPop() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    try {
+      deque.pop();
+      fail();
+    } catch (NoSuchElementException expected) { }
+
+    deque.add(o1);
+    assertEquals(o1, deque.pop());
+    assertTrue(deque.isEmpty());
+
+    deque.add(o1);
+    deque.add(o2);
+    assertEquals(o1, deque.pop());
+    checkDequeSizeAndContent(deque, o2);
+    assertEquals(o2, deque.pop());
+    assertTrue(deque.isEmpty());
+    try {
+      deque.pop();
+      fail();
+    } catch (NoSuchElementException expected) { }
+  }
+
+  public void testPush() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+    Object o3 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    deque.push(o1);
+    checkDequeSizeAndContent(deque, o1);
+    deque.push(o2);
+    checkDequeSizeAndContent(deque, o2, o1);
+    deque.push(o3);
+    checkDequeSizeAndContent(deque, o3, o2, o1);
+
+    try {
+      deque.push(null);
+      fail();
+    } catch (NullPointerException expected) { }
+  }
+
+  public void testRemove() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    try {
+      deque.remove();
+      fail();
+    } catch (NoSuchElementException expected) { }
+
+    deque.add(o1);
+    assertEquals(o1, deque.remove());
+    assertTrue(deque.isEmpty());
+
+    deque.add(o1);
+    deque.add(o2);
+    assertEquals(o1, deque.remove());
+    checkDequeSizeAndContent(deque, o2);
+    assertEquals(o2, deque.removeFirst());
+    assertTrue(deque.isEmpty());
+
+    try {
+      deque.remove();
+      fail();
+    } catch (NoSuchElementException expected) { }
+  }
+
+  public void testRemoveElement() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    assertFalse(deque.remove(o1));
+
+    deque.add(o1);
+    assertTrue(deque.remove(o1));
+    assertTrue(deque.isEmpty());
+
+    deque.add(o1);
+    deque.add(o2);
+    assertTrue(deque.remove(o1));
+    checkDequeSizeAndContent(deque, o2);
+    assertTrue(deque.remove(o2));
+    assertTrue(deque.isEmpty());
+
+    assertFalse(deque.remove(null));
+  }
+
+  public void testRemoveFirst() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    try {
+      deque.removeFirst();
+      fail();
+    } catch (NoSuchElementException expected) { }
+
+    deque.add(o1);
+    assertEquals(o1, deque.removeFirst());
+    assertTrue(deque.isEmpty());
+
+    deque.add(o1);
+    deque.add(o2);
+    assertEquals(o1, deque.removeFirst());
+    checkDequeSizeAndContent(deque, o2);
+    assertEquals(o2, deque.removeFirst());
+    assertTrue(deque.isEmpty());
+
+    try {
+      deque.removeFirst();
+      fail();
+    } catch (NoSuchElementException expected) { }
+  }
+
+  public void testRemoveFirstOccurrence() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+    Object o3 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    assertFalse(deque.removeFirstOccurrence(o1));
+
+    deque.add(o1);
+    assertTrue(deque.removeFirstOccurrence(o1));
+    assertTrue(deque.isEmpty());
+
+    deque = new ArrayDeque<>();
+    deque.add(o1);
+    deque.add(o2);
+    deque.add(o3);
+    assertTrue(deque.removeFirstOccurrence(o2));
+    checkDequeSizeAndContent(deque, o1, o3);
+
+    deque = new ArrayDeque<>();
+    deque.add(o1);
+    deque.add(o2);
+    deque.add(o3);
+    deque.add(o1);
+    deque.add(o2);
+    deque.add(o3);
+    assertTrue(deque.removeFirstOccurrence(o2));
+    checkDequeSizeAndContent(deque, o1, o3, o1, o2, o3);
+    assertTrue(deque.removeFirstOccurrence(o2));
+    checkDequeSizeAndContent(deque, o1, o3, o1, o3);
+    assertTrue(deque.removeFirstOccurrence(o1));
+    checkDequeSizeAndContent(deque, o3, o1, o3);
+    assertTrue(deque.removeFirstOccurrence(o1));
+    checkDequeSizeAndContent(deque, o3, o3);
+    assertFalse(deque.removeFirstOccurrence(o1));
+
+    assertFalse(deque.removeFirstOccurrence(null));
+  }
+
+  public void testRemoveLast() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    try {
+      deque.removeLast();
+      fail();
+    } catch (NoSuchElementException expected) { }
+
+    deque.add(o1);
+    assertEquals(o1, deque.removeLast());
+    assertTrue(deque.isEmpty());
+
+    deque.add(o1);
+    deque.add(o2);
+    assertEquals(o2, deque.removeLast());
+    checkDequeSizeAndContent(deque, o1);
+    assertEquals(o1, deque.removeLast());
+    assertEquals(0, deque.size());
+
+    try {
+      deque.removeLast();
+      fail();
+    } catch (NoSuchElementException expected) { }
+  }
+
+  public void testRemoveLastOccurrence() {
+    Object o1 = new Object();
+    Object o2 = new Object();
+    Object o3 = new Object();
+
+    ArrayDeque<Object> deque = new ArrayDeque<>();
+    assertFalse(deque.removeLastOccurrence(o1));
+
+    deque.add(o1);
+    assertTrue(deque.removeLastOccurrence(o1));
+    assertTrue(deque.isEmpty());
+
+    deque = new ArrayDeque<>();
+    deque.add(o1);
+    deque.add(o2);
+    deque.add(o3);
+    assertTrue(deque.removeLastOccurrence(o2));
+    checkDequeSizeAndContent(deque, o1, o3);
+
+    deque = new ArrayDeque<>();
+    deque.add(o1);
+    deque.add(o2);
+    deque.add(o3);
+    deque.add(o1);
+    deque.add(o2);
+    deque.add(o3);
+    assertTrue(deque.removeLastOccurrence(o2));
+    checkDequeSizeAndContent(deque, o1, o2, o3, o1, o3);
+    assertTrue(deque.removeLastOccurrence(o2));
+    checkDequeSizeAndContent(deque, o1, o3, o1, o3);
+    assertTrue(deque.removeLastOccurrence(o3));
+    checkDequeSizeAndContent(deque, o1, o3, o1);
+    assertTrue(deque.removeLastOccurrence(o3));
+    checkDequeSizeAndContent(deque, o1, o1);
+    assertFalse(deque.removeLastOccurrence(o3));
+
+    assertFalse(deque.removeLastOccurrence(null));
+  }
+
+  /**
+   * Null elements are prohibited in ArrayDeque.
+   */
+  @Override
+  protected Object[] getFullElements() {
+    return getFullNonNullElements();
+  }
+
+  @Override
+  protected Collection makeConfirmedCollection() {
+    return new ArrayList<>();
+  }
+
+  @Override
+  protected Collection makeConfirmedFullCollection() {
+    return new ArrayList<>(asList(getFullElements()));
+  }
+
+  @Override
+  protected Collection makeCollection() {
+    return new ArrayDeque<>();
+  }
+
+  private void checkDequeSizeAndContent(Deque<?> deque, Object... expected) {
+    assertEquals(expected.length, deque.size());
+    int i = 0;
+    for (Object e : deque) {
+      assertEquals(expected[i++], e);
+    }
+    assertEquals(expected.length, i);
+  }
+}