使用循環數組的隊列實現：調整循環數組的大小的最佳方法是？

Question

我正在實施一個隊列使用圓形陣列，我有點卡在resize()方法實現（當數組已滿）。

在enqueue()方法裏面我檢查數組的大小是否等於它的長度，如果數組已滿，現在，我試圖調整數組的大小，而不是拋出異常。

的事情是，我有兩個問題需要注意

1. 前< =後
2. 後<前

這是複製的元素舊的的最好的方法陣列到新的，更大的？

我認爲它使用一個for循環，如：

newArray = new Array[oldArray.length*2]; 

if (front <= rear) { 
    for (int i = front; i < rear; i++) { 
     newArray[i] = oldArray[i]; 
    } 
} else { 
    for (int i = front; i < newArray.length; i++) { 
     newArray[i] = oldArray[i]; 
    } 

    for (int j = rear; j < front; j++) { 
     // i'm using the variable i, the order is maintained 
     newArray[i] = oldArray[j]; 
     i++; 
    } 
} 

然後oldArray = newArray，返回newArray它完成

調整大小我不知道爲氏使用量做到這一點，恐怕我失去了價值。

有人可以告訴我是否有更好的方法來做到這一點？

Answer 1

想想要移動的數組元素塊以及他們應該在新陣列中的位置。然後使用System.arraycopy來完成它。如果前方<後方，並且前方後方<前方兩次，則應該調用arraycopy一次。

Answer 2

對於複製具有多個元素的數組，使用System.arraycopy()，因爲它通常以本機代碼的形式實現，例如， Sun的VM使用手工編碼的彙編程序。

前>後

由於數據是連續的，它可以在新陣列中保持在相同的位置。

System.arraycopy(oldArray, front, newArray, front, front-rear); 

前< =後部

的數據是不連續的，所以這兩個塊複製到新的數組的開始。

// copy [rear to end] 
System.arraycopy(oldArray, rear, newArray, 0, oldArray.length-rear); 
// copy [0 to front] 
System.arraycopy(oldArray, 0, newArray, oldArray.length-rear, front); 
front = oldArray.length-(rear-front); 
rear = 0; 

Answer 3

如果陣列是滿的，你要麼有front == rear - 1，或rear == 0和front == length -1（或周圍的其他方法，我不知道你的命名）。在第二種情況下，您可以在一個步驟中複製整個陣列，在（更一般的）第一種情況下，您有兩個要複製的塊（0 .. front和rear .. length-1）。

Answer 4

Thx很多爲您的答案和不同的解決方案！ :)

儘管使用該系統。arraycopy（）方法是最簡單和有效的解決方案，我必須避免使用它並自己實現解決方案。

因此，如果有人要調整大小（）不System.arraycopy（）隊列執行一個圓陣，這裏是我的最終解決方案：

private void resize() { 

    E[] aux = (E[]) new Object[Q.length * 2]; // new array 

    int i = 0; // use this to control new array positions 
    int j = f; // use this to control old array positions 

    boolean rearReached = false; 

    while (!rearReached) { 

     rearReached = j % Q.length == r; // is true if we've reached the rear 

     aux[i] = Q[j % Q.length]; 

     i++; 
     j++; 

    } 

    f = 0; 
    r = Q.length - 1; 
    Q = aux; 

} 

正如你所看到的，我把優勢「循環」的東西，並使用％運算符將舊數組的位置映射到新數組。

生成的數組將在新數組的開始處具有容量的雙倍和所有元素（顯然保持原始順序）。

我測試過它，它工作正常。 Lemme知道該代碼是否有任何不便。

Regards