2

循環配列を使用してこの両端キューを実装するのに多くの問題があります。特に、remove メソッドは、何を試しても間違った要素を削除しているようです。誰でも助けることができますか？

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 < 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;
    }
    /**
     * 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 >= 8){
            if(size() < capacity/4){
                capacity /= 2;
            }
        }
        int[] B = new int[capacity];
        for(int i = 1; i < 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 >= 8){
            if(size() < capacity/4){
                capacity /= 2;
            }
        }
        int[] B = new int[capacity];
        for(int i = front; i<size()-1; i++){
            B[i] = A[i];
        }
        A = B;
        rear--;
        return A[rear];
    }
}  // end class
4

4 に答える 4

4

コードsize() == capacity は真になることはありません。これが展開されない理由です。それを作るsize() == capacity - 1。

見落としやすいのでお譲りします

于 2011-03-04T12:33:12.467 に答える
1

指定されたコードによると、frontの値は常に値ゼロを保持します。

  1. removeFirst（）では、 front++を実行する必要があります。
  2. insertLast（）では、rear++を2回実行しています。if/elseの外でrear++を削除できます。
  3. removeFirst （）は、常に2番目の要素を返します。これは、そのメソッドのforループが最初の要素を失うためです。

注：上記のいずれも、循環キューにはなりません。アドバイス：読んで再実装:)

于 2011-02-21T19:42:42.130 に答える
-1

少し前に作成した C の実装があります。Java への移植が容易であるか、少なくとも Java での実装方法についてのヒントが得られると思います。

ありがとう、セルジオ。

typedef struct { void *要素; /データ。*/ size_t sz; /* キューの容量。*/ size_t nelems; /* キュー内の要素数。*/ size_t 最初; /* キューの最初の要素を指します。*/} nx_queue_t;

nx_queue_t *nx_queue_create (size_t サイズ) { nx_queue_t *q;

if ( (q = malloc (sizeof(nx_queue_t))) == NULL )
    return (NULL);

q->sz = size;
q->nelems = 0;
q->first=0;

if ( (q->elems = malloc (sizeof(void*)*size)) == NULL ) {
    free (q);
    return (NULL);
}

return (q);

}

size_t nx_queue_capacity (nx_queue_t *q) { return (q->sz); }

size_t nx_queue_size (nx_queue_t *q) { return (q->nelems); }

int nx_queue_empty (nx_queue_t *q) { return (! q->nelems); }

int nx_queue_full (nx_queue_t *q) { return (q->nelems == q->sz); }

int nx_queue_enqueue (nx_queue_t *q, void *elem) { size_t i;

if (nx_queue_full (q))
    return (-1);

i = (q->first + q->nelems) % q->sz;
q->elems[i] = elem;
q->nelems++;

}

void *nx_queue_dequeue (nx_queue_t *q) { void *elem ;

if (nx_queue_empty (q))
    return (NULL);

elem = q->elems[q->first];
q->first = (q->first + 1) % q->sz;
q->nelems--;

return (elem);

}

于 2011-02-21T19:50:25.130 に答える