0

配列がいっぱいになると拡張する循環配列を利用して 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)
4

1 に答える 1

0
public void insertLast(int e) {

     if(size() == capacity - 1) {
         capacity= capacity*2;
    }

    int[] B = new int[capacity];

    for(int i = 0; i < size(); i++) {
        B[i] = A[i];
    }

    A = B;

    A[rear] = e;
    rear = (rear + 1) % capacity;

}

これが私のinsertLast()です。これがうまくいくと思います。cse2011で頑張ってください.. !!

于 2013-06-28T22:54:16.827 に答える