DO "TODO" please import java.lang.reflect.Array; import java.util.Arrays; import java.util.Optional; class NoSuchElementE extends Exception {} public abstract class DequeueArray { protected Optional[] elements; protected int capacity, front, back, size; // // data stored in locations: // front+1, front+2, ... back-2, back-1 (all mod capacity) // // common cases: // front points to an empty location // back points to an empty location // adding to front decreases 'front' by 1 // adding to back increases 'back' by 1 // removing does the opposite // // |-------------------------| // | 4 5 6 _ _ _ _ _ _ 1 2 3 | // |-------------------------| // /\ /\ /\ // back front capacity // @SuppressWarnings("unchecked") DequeueArray(int initialCapacity) { elements = (Optional[]) Array.newInstance(Optional.class, initialCapacity); Arrays.fill(elements, Optional.empty()); capacity = initialCapacity; front = capacity - 1; back = 0; size = 0; }

public void clear() { elements = (Optional[]) Array.newInstance(Optional.class, 1); Arrays.fill(elements, Optional.empty()); capacity = 1; front = 0; back = 0; size = 0; }

class DequeueArrayPlusOne extends DequeueArray { DequeueArrayPlusOne (int initialCapacity) { super(initialCapacity); } /** * Grow the dequeue by one * A new array is created, all the elements in the old array * are copied in the first part of the new array */ @SuppressWarnings("unchecked") void grow() { // TODO } }