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; 
} 
}