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;

}

@SuppressWarnings("unchecked")

public void clear() {

elements = (Optional[]) Array.newInstance(Optional.class, 1);

Arrays.fill(elements, Optional.empty());

capacity = 1;

front = 0;

back = 0;

size = 0;

}

public int size () { return size; }

// --- real work begins --- //

/**

* Adds the given elem to the front of the dequeue

* If there is no room, grow the dequeue first

*/

public void addFirst(E elem) {

// TODO

}

public E getFirst() throws NoSuchElementE {

return elements[Math.floorMod(front+1,capacity)].orElseThrow(NoSuchElementE::new);

}

public E getLast() throws NoSuchElementE {

return null; // TODO

}

/*