基於數組的Deque implmentation

Question

我正在關注一個在線示例並學習「使用數組在Java中實現Circular Deque」。下面是我下面的在線資源：

Circular Queue Implementation

我有其中有5最終容量現在，如果數組已滿那麼我就可以有兩種方式創建的臨時陣列基於陣列雙端隊列類所有對象，然後將臨時數組的所有對象複製回「object [] arr」。我已經有一段時間了，但一直未能實現。如果有人能幫助我理解這裏的過程，我將不勝感激。我有以下類方法：

1. insertAtFront（）
2. insertAtLast（）
3. 大小（）
4. 的isEmpty（）
5. 的toString（）

這裏是我的代碼：

public class ArrayDeque { 

    private static final int INIT_CAPACITY = 5;    
    private int front;        
    private int rear;          
    private Object[] arr;       


    public ArrayDeque(){ 

     arr = new Object[ INIT_CAPACITY ]; 
     front = 0; 
     rear = 0;  
    } 


    public void insertAtFirst(Object item){ 

     if(size() >= arr.length){ 

      Object[] tmp = new Object[arr.length + INIT_CAPACITY]; 

      for(int i = 0; i < size(); ++i) 
       tmp[i] = arr[i]; 

      arr = tmp; 
     } 
     arr[front] = item; 
     ++front; 
    } 


    public void insertAtLast(Object item){ 

     if(size() >= arr.length){ 

      Object[] tmp = new Object[arr.length + INIT_CAPACITY]; 

      for(int i = 0; i < size(); ++i) 
       tmp[i] = arr[i]; 

      arr = tmp; 
     } 
     arr[rear] = item; 
     ++rear; 
    } 


    public int size(){ 

     return (rear - front);  
    } 


    public boolean isEmpty(){ 

     return (front == rear); 

    } 


    public String toString(){ 

     String s = ""; 
     for(int i = 0; i < size(); ++i) 
      s += arr[i] + "\n"; 
     return s; 
    } 
}//CLASS  

Answer 1

嘗試下面的代碼，我通過跟蹤數組填滿了多少來改變邏輯。你的主要問題是size（）函數，它提供了錯誤的指示。一些優化正在等待我看到結果中的一些空值。

public class ArrayDeque { 
    public static void main(String[] args) { 
     ArrayDeque t = new ArrayDeque(); 
     t.insertAtFirst("1"); 
     t.insertAtFirst("2"); 
     t.insertAtFirst("3"); 
     t.insertAtFirst("4"); 
     t.insertAtFirst("5"); 
     t.insertAtFirst("6"); 
     t.insertAtFirst("7"); 
     t.insertAtFirst("8"); 
     t.insertAtFirst("9"); 
     t.insertAtFirst("10"); 
     t.insertAtFirst("11"); 
     t.insertAtFirst("12"); 
     t.insertAtFirst("13"); 
     t.insertAtFirst("14"); 

     System.out.println("After first--"+t.toString()); 
     t.insertAtLast("1"); 
     t.insertAtLast("2"); 
     t.insertAtLast("3"); 
     t.insertAtLast("4"); 
     t.insertAtLast("5"); 
     t.insertAtLast("6"); 
     t.insertAtLast("7"); 
     t.insertAtLast("8"); 
     t.insertAtLast("9"); 
     t.insertAtLast("10"); 
     t.insertAtLast("11"); 
     t.insertAtLast("12"); 
     t.insertAtLast("13"); 
     t.insertAtLast("14"); 
     System.out.println("After last--"+t.toString()); 
    } 
    private static final int INIT_CAPACITY = 5;    

    private int NEW_CAPACITY; 
    private int ARRAY_SIZE; 
    private Object[] arr;       


    public TestClass(){ 

     arr = new Object[ INIT_CAPACITY ]; 

     NEW_CAPACITY = INIT_CAPACITY; 
     ARRAY_SIZE = 0; 
    } 


    public void insertAtFirst(Object item){ 

     if(ARRAY_SIZE == 0) 
     { 
      arr[0] = item; 
      ARRAY_SIZE++; 
     } 
     else if(ARRAY_SIZE+1 < arr.length) 
     { 
      Object[] tmp = new Object[NEW_CAPACITY]; 
      for(int i = 1; i < arr.length; ++i) 
       tmp[i] = (String)arr[i-1]; 

      arr = tmp; 
      arr[0] = item; 
      ARRAY_SIZE++; 
     } 
     else if(ARRAY_SIZE+1 >= arr.length) 
     { 
      NEW_CAPACITY = NEW_CAPACITY+INIT_CAPACITY; 
      Object[] tmp = new Object[NEW_CAPACITY]; 
      for(int i = 1; i < arr.length; ++i) 
       tmp[i] = (String)arr[i-1]; 

      arr = tmp; 
      arr[0] = item; 
      ARRAY_SIZE++; 
     } 
    } 


    public void insertAtLast(Object item){ 

     if(ARRAY_SIZE == 0) 
     { 
      arr[0] = item; 
      ARRAY_SIZE++; 
     } 
     else if(ARRAY_SIZE+1 < arr.length) 
     { 

      arr[ARRAY_SIZE] = item; 
      ARRAY_SIZE++; 
     } 
     else if(ARRAY_SIZE+1 >= arr.length) 
     { 
      NEW_CAPACITY = NEW_CAPACITY+INIT_CAPACITY; 
      Object[] tmp = new Object[NEW_CAPACITY]; 
      for(int i = 0; i < arr.length; ++i) 
       tmp[i] = (String)arr[i]; 

      arr = tmp; 

      arr[ARRAY_SIZE] = item; 
      ARRAY_SIZE++; 
     } 
    } 


    public int size(){ 

     return ARRAY_SIZE;  
    } 


    public boolean isEmpty(){ 

     return (ARRAY_SIZE == 0); 

    } 


    public String toString(){ 

     String s = ""; 
     for(int i = 0; i < arr.length; ++i) 
      s += arr[i] + "\t"; 
     return s; 
    } 
}