/**
  * Class ArrayDeque to implement the Deque interface using a circular array
  *

  * @author Jack Han
  */

public class ArrayDeque<E> implements Deque<E> {
 

  protected <E> array[];  // circular array
  private int front, end;    // pointers to the front and end
  private int size;

  private int capacity;

 // initialize an empty deque

 public ArrayDeque(int capacity) { 
    array = new E[capacity];  // create an array

    front = 1;                         // pointers initialized

    end = 0;

    size = 0;                           // number of elements

    this.capacity = capacity - 1;   // length of the array minus 1
  }
 

// Returns the number of nodes

 public int size() {  
    return size;
  }
 

 // Test if empty

 public boolean isEmpty() {   
    return size == 0;
  }

// Returns the first element

 public E getFirst() throws EmptyDequeException { 
    if (isEmpty())
      throw new EmptyDequeException("Deque is empty.");
    return array[(front-1)%capacity];
  }
 

 // Returns the last element

public E getLast() throws EmptyDequeException { 
    if (isEmpty())
      throw new EmptyDequeException("Deque is empty.");
    return array[(end+1)%capacity];
  }

 // Adds a new element at the front

 public void addFirst(E o) throws FullDequeException { 
    if (size == capacity)

        throw new FullDequeException("Deque is full.");
    array[front] = o;

    front = (front+1)%capacity; 

    size++;
  }
 

 // Adds a new node at the tail

 public void addLast(E o) {  

    if (size == capacity)

        throw new FullDequeException("Deque is full.");
    array[end] = o;

    end = (end-1)%capacity; 

    size++;
  }

 // Removes the first node

 public E removeFirst() throws EmptyDequeException {
    if (isEmpty())
      throw new EmptyDequeException("Deque is empty.");
    front = (front-1)%capacity;
    size--;
    return array[front];
  }

 // Removes the last node

 public E removeLast() throws EmptyDequeException {
    if (isEmpty())
      throw new EmptyDequeException("Deque is empty.");
    end = (end+1)%capacity;
    size--;
    return array[end];
  }
}