CircularArrayQueue実装Java

Question

CircularArrayQueueを実装しようとしています。私は待ち行列が通過しなければならないJUnitテストを受けました。私は、前と後ろのポインタで何か間違っていると思います。私はデータ構造とアルゴリズムの学習にどのようにアプローチすべきですか？

import java.util.NoSuchElementException; 

public class CircularArrayQueue implements MyQueue { 
    private Integer[] array; 
    // initial size of the array 
    private int N; 
    private int front; 
    private int rear; 

    public CircularArrayQueue() { 
     this.N = 10; 
     array = new Integer[N]; 
     front = rear = 0; 
    } 

    public CircularArrayQueue(int size) { 
     this.N = size; 
     array = new Integer[N]; 
     front = rear = 0; 
    } 

    // enqueues an element at the rear of the queue 
    // if the queue is already full it is resized, doubling its size 
    @Override 
    public void enqueue(int in) { 
     if (rear == N) { 
      if (front == 0) { 
       resize(); 
       array[rear] = in; 
       rear++; 
      } else { 
       array[rear] = in; 
       rear = 0; 
      } 
     } else { 
      array[rear] = in; 
      rear++; 
     } 

    } 

    public void resize() { 
     Integer[] temp = new Integer[array.length * 2]; 

     for (int i = 0; i < array.length; i++) { 
      temp[i] = array[i]; 
     } 

     temp = array; 
    } 

    // dequeues an element 
    // if the queue is empty a NoSuchElement Exception is thrown 
    @Override 
    public int dequeue() throws NoSuchElementException { 
     if (isEmpty()) { 
      throw new NoSuchElementException("The queue is full"); 
     } 

     int headElement = array[front]; 

     if (front == N) { 
      array[front] = null; 
      front = 0; 
     } else { 
      array[front] = null; 
      front++; 
     } 

     return headElement; 
    } 

    @Override 
    public int noItems() { 
     return N - getCapacityLeft(); 
    } 

    @Override 
    public boolean isEmpty() { 
     return (getCapacityLeft() == N); 
    } 

    // return the number of indexes that are empty 
    public int getCapacityLeft() { 
     return (N - rear + front) % N; 
    } 
} 

Answer 1

あなたの初期化は絶対に大丈夫です、そして我々が開始しない：Qに項目を追加するBefor

front = rear = 0; 

%は私たちがすることができます

rear = (rear + 1) % N; 

として、我々は rearを変更キューの循環プロパティを維持します。また、 0インデックスが残っている emptyの場合は、 isEmpty()と isFull()の機能をチェックするための正しい実装を行うために、1つの配列アイテムを空白にして妥協する必要があります。

@Override 
public boolean isFull() 
{ 
    return front == ((rear + 1) % N); 
} 

：あなたはまた、のような機能 isFull()を持っている必要があり

@Override 
public boolean isEmpty() 
{ 
    return front == rear; 
} 

：isEmpty()ための正しいコードがある、と述べた

resize()のtemp = array;行もarray = temp;である必要があります。resize()を呼び出した後にNの値を更新する必要があります。

したがって、正しいコードは次のとおりです。

import java.util.NoSuchElementException; 

public class CircularArrayQueue implements MyQueue 
{ 
private Integer[] array; 
//initial size of the array 
private int N; 
private int front; 
private int rear; 
private int count = 0;//total number of items currently in queue. 
public CircularArrayQueue() 
{ 
    this.N = 10; 
    array = new Integer[N]; 
    front = rear = 0; 
} 

public CircularArrayQueue(int size) 
{ 
    this.N = size; 
    array = new Integer[N]; 
    front = rear = 0; 
} 


//enqueues an element at the rear of the queue 
// if the queue is already full it is resized, doubling its size 
@Override 
public void enqueue(int in) 
{ 
    count++; 
    if (isFull()) 
    { 
     resize(); 
     rear = (rear + 1) % N; 
     array[rear] = in; 
    } 
    else 
    { 
     rear = (rear + 1) % N; 
     array[rear] = in; 
    }    
} 

public void resize() 
{ 
    Integer[] temp = new Integer[array.length*2]; 
    N = array.length*2; 
    for(int i=0; i<array.length; i++) 
    { 
     temp[i] = array[i]; 
    } 

    array = temp; 
} 


//dequeues an element 
// if the queue is empty a NoSuchElement Exception is thrown 
@Override 
public int dequeue() throws NoSuchElementException 
{ 
    if(isEmpty()) 
    { 
     throw new Exception("The queue is empty"); 
    } 

    front = (front + 1) % N; 
    int headElement = array[front]; 
    count--; 
    return headElement; 
} 

@Override 
public int noItems() 
{ 
    return count; 
} 

@Override 
public boolean isEmpty() 
{ 
    return front == rear; 
} 

@Override 
public boolean isFull() 
{ 
    return front == ((rear + 1) % N); 
} 

//return the number of indexes that are empty 
public int getCapacityLeft() 
{ 
    return N - 1 - count; 
} 
}