title: Implementing a deque using a circular array?
body: <p>I'm having a lot of trouble implementing this deque using a circular array; in particular, the remove methods seem to be removing the wrong elements no matter what I try.  Can anyone help?</p>
  
  <pre><code>public class ArrayDeque
  {
     public static final int INIT_CAPACITY = 8;   // initial array capacity
     protected int capacity;  // current capacity of the array
     protected int front;     // index of the front element
     protected int rear;      // index of the rear element
     protected int[] A;       // array deque
  
     public ArrayDeque( )      // constructor method
     {
        A = new int[ INIT_CAPACITY ];
        capacity = INIT_CAPACITY;
        front = rear = 0;
      }
  
     /**
       * Returns the number of items in this collection.
       * @return the number of items in this collection.
       */
      public int size( )
      {
          return rear - front;
      }
  
      /**
       * Returns true if this collection is empty.
       * @return true if this collection is empty.
       */ 
      public boolean isEmpty( )
      {
          return front == rear;
      }
      /**
       * Returns the first element of the deque
       */
      public int getFirst() throws EmptyDequeException
      {     
          if(isEmpty()){
              throw new EmptyDequeException("Deque is empty.");
          }
          return A[front % capacity];       
      }
      /**
       * Returns the last element of the deque
       */
      public int getLast( ) throws EmptyDequeException
      {  
          if(isEmpty()){
              throw new EmptyDequeException("Deque is empty.");
          }
          return A[(front + rear - 1) % capacity];   // replace this line with your code         
      }
      /**
       * Inserts e at the beginning (as the first element) of the deque
       */
      public void insertFirst( int e )
      {
          rear++;
          if(size() == capacity){
              capacity *= 2;
          }
          int[] B = new int[capacity];
          for(int i = 0; i &lt; size(); i++){
              B[i] = A[i];
          }
          A = B;
          for(int i = size(); i &gt;= front; i--){
              A[i+1] = A[i];
          }
          A[front] = e;
          front = front % capacity;
      }
      /**
       * Inserts e at the end (as the last element) of the deque
       */
      public void insertLast( int e )
      {
          if(size() == capacity){
              capacity *= 2;
              A[rear++] = e;
          }
          else{
              A[rear++] = e;
          }
          rear++;
      }
      /**
       * Removes and returns the first element of the deque
       * Shrink array by half of current size N when number of elements in the deque falls below N/4
       * minimum capacity should always be 8
       */
      public int removeFirst( ) throws EmptyDequeException
      {
          if(size() == 0){
              throw new EmptyDequeException("Deque is empty.");
          }
          if(capacity &gt;= 8){
              if(size() &lt; capacity/4){
                  capacity /= 2;
              }
          }
          int[] B = new int[capacity];
          for(int i = 1; i &lt; size(); i++){
              B[i-1] = A[i];
          }
          A = B;
          return A[front];
      }
      /**
       * Removes and returns the last element of the deque
       * Shrink array by half of current size N when number of elements in the deque falls below N/4
       * minimum capacity should always be 8
       */
      public int removeLast( ) throws EmptyDequeException
      {
          if(size() == 0){
              throw new EmptyDequeException("Deque is empty.");
          }
          if(capacity &gt;= 8){
              if(size() &lt; capacity/4){
                  capacity /= 2;
              }
          }
          int[] B = new int[capacity];
          for(int i = front; i&lt;size()-1; i++){
              B[i] = A[i];
          }
          A = B;
          rear--;
          return A[rear];
      }
  }  // end class
  </code></pre>