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

你的初始化是精絕，我們也有開始：

front = rear = 0; 

Befor添加項目到Q，我們修改rear爲

rear = (rear + 1) % N; 

的%允許我們保持隊列的循環屬性。你也一定想知道，如果我們在添加任何項目之前修改尾部，那麼0索引是empty，那麼我們必須在這裏妥協一個數組項目留空，以便具有檢查isEmpty()和isFull()函數的正確實現：

這就是說，對於isEmpty()正確的代碼是：

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

你也應該有一個功能isFull()，如：

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

另外，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; 
} 
}