配列がいっぱいになると拡張する循環配列を利用して Deque を実装しようとしています。ただし、IndexOutOfBoundsException が発生しています。私の問題は、insertLast メソッドにあると思います。コードを徹底的に分析しましたが、何が間違っているのかわかりません。どんな援助でも大歓迎です。
public class CircularExtendedArrayDeque
{
public static final int INIT_CAPACITY = 4; // 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 CircularExtendedArrayDeque( ) // constructor method
{
A = new int[ INIT_CAPACITY ];
capacity = INIT_CAPACITY;
front = rear = 0;
}
/**
* Print the content of the deque
*
*/
public void printDeque( )
{
for ( int i = front; i != rear; i = (i+1) % capacity )
System.out.print( A[i] + " " );
System.out.println();
}
/**
* Print the content of the whole array
*
*/
public void printArray( )
{
for ( int i = 0; i < capacity; i++ )
System.out.print( A[i] + " " );
System.out.println();
}
// ***************************************
// DO NOT MODIFY THE CODE ABOVE THIS LINE.
// ADD YOUR CODE BELOW THIS LINE.
//
// ***************************************
/**
* Returns the number of items in this collection.
* @return the number of items in this collection.
*/
public int size()
{
// COMPLETE THIS METHOD
return (capacity - front + rear) % capacity;
}
/**
* Returns true if this collection is empty.
* @return true if this collection is empty.
*/
public boolean isEmpty()
{
// COMPLETE THIS METHOD
return front == rear;
}
/**
* Returns the first element of the deque
*
*/
public int getFirst() throws EmptyDequeException
{
// COMPLETE THIS METHOD
if(isEmpty()){
throw new EmptyDequeException("Deque is empty.");
}
return A[front % capacity];
}
/**
* Returns the last element of the deque
*
*/
public int getLast() throws EmptyDequeException
{
// COMPLETE THIS METHOD
if(isEmpty()){
throw new EmptyDequeException("Deque is empty.");
}
return A[(front + rear - 1) % capacity];
}
/**
* Inserts e at the beginning (as the first element) of the deque
*
*/
public void insertFirst( int e )
{
// COMPLETE THIS METHOD
rear++;
if(size() == capacity - 1){
capacity *= 2;
}
int[] B = new int[capacity];
for(int i = 0; i < size(); i++){
B[i] = A[i];
}
A = B;
for(int i = size(); i >= front; i--){
A[i+1] = A[i];
}
A[front] = e;
front = front % capacity;
System.out.println("Front: " + front + " & Rear:" + rear);
}
/**
* Inserts e at the end (as the last element) of the deque
*
*/
public void insertLast( int e )
{
// COMPLETE THIS METHOD
if(size() == capacity - 1){
capacity *= 2;
int[] B = new int[capacity];
for ( int i = front; i != rear; i = (i+1) % capacity )
B[i] = A[i];
/*
for(int i = 0; i < size(); i++){
B[i] = A[i];
}
*/
A = B;
A[rear++] = e;
}
else{
//System.out.println("Array Size = " + A.length);
A[rear++] = e;
}
System.out.println("Front: " + front + " & Rear:" + rear);
System.out.println("msg...size=" + size());
}
/**
* Removes and returns the first element of the deque
*
*/
public int removeFirst( ) throws EmptyDequeException
{
// COMPLETE THIS METHOD
int result = A[front];
A[front] = 0;
front = (front+1)%capacity;
if(isEmpty()){
throw new EmptyDequeException("Deque is empty.");
}
else if(capacity >= 4){
if(size() < capacity/2){
//System.out.println("msg...size = " + size());
capacity /= 2;
int[] B = new int[capacity];
int counter=0;
for(int i = front; i < front+size(); i++){
B[counter] = A[i%(capacity*2)];
counter++;
}
A = B;
front = 0;
rear = size()-1;
}
}
return result;
}
/**
* Removes and returns the last element of the deque
*
*/
public int removeLast( ) throws EmptyDequeException
{
// COMPLETE THIS METHOD
if(isEmpty()){
throw new EmptyDequeException("Deque is empty.");
}
else if(capacity >= 4){
if(size() < capacity/2){
System.out.println("Capacity shrinking...");
int[] B = new int[capacity/2];
for(int i = 0; i < capacity/2; i++){
B[i] = A[i];
}
A = B;
}
}
int temp = A[rear - 1];
A[rear] = 0;
rear = (rear - 1) % capacity;
return temp;
}
} // end class
メインクラスは次のとおりです。
public class CircularExtendedArrayMain {
public static void main(String[] args) {
CircularExtendedArrayDeque q = new CircularExtendedArrayDeque();
q.insertFirst(112);
q.insertFirst(105);
q.printDeque();
System.out.println("last element is = " + q.getLast());
System.out.println("first element is = " + q.getFirst());
q.insertLast(5501);
q.printDeque();
q.insertLast(778);
q.insertLast(37);
q.printDeque();
System.out.println("first element is = " + q.getFirst());
System.out.println("last element is = " + q.getLast());
System.out.println("remove last = " + q.removeLast());
q.printDeque();
System.out.println("remove last = " + q.removeLast());
System.out.println("remove first = " + q.removeFirst());
q.printDeque();
System.out.println("remove first = " + q.removeFirst());
System.out.println("remove first = " + q.removeFirst());
// q is now empty.
int i, k;
for( i = 1; i <= 60; i ++ )
q.insertLast(i*i);
q.printDeque(); // 60 elements in q
for( i = 1; i <= 58; i++ )
k = q.removeFirst();
q.printDeque(); // two elements are left
}
}
ここに私の出力があります：
Front: 0 & Rear:1
Front: 0 & Rear:2
105 112
last element is = 112
first element is = 105
Front: 0 & Rear:3
msg...size=3
105 112 5501
Front: 0 & Rear:4
msg...size=4
Front: 0 & Rear:5
msg...size=5
105 112 5501 778 37
first element is = 105
last element is = 37
remove last = 37
105 112 5501 778
remove last = 778
remove first = 105
112 5501
remove first = 112
remove first = 5501
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at CircularExtendedArrayDeque.insertLast(CircularExtendedArrayDeque.java:161)
at CircularExtendedArrayMain.main(CircularExtendedArrayMain.java:34)