Java-Randomized Queue Iterator导致Invalid Range异常

Question

我在 Java 中实现了随机队列。尽管入队、出队和样本操作工作正常，但迭代器导致每次在 shuffle 方法中抛出无效范围异常。

我不明白为什么 shuffle() 方法中的随机数生成受队列大小的限制。这是代码:

private int N=0;
private Item[] queue;
public RandomizedQueue(){
   queue= (Item[]) new Object[8];
}                // construct an empty randomized queue
public boolean isEmpty(){
   return N==0;
}                 // is the queue empty?
public int size(){
   return N;
}// return the number of items on the queue
private void resize(int capacity){
    Item[] copy=(Item[]) new Object[capacity];
    for(int i=0;i<N;i++){
        copy[i]=queue[i];
    }
    queue=copy;
}

private class QueueIterator implements Iterator<Item>{
    int i=0;
    public QueueIterator(){
        if(N>0){
            shuffle();
        }
    }
    @Override
    public boolean hasNext() {
        return i<N;
    }

    @Override
    public Item next() {
        Item item=queue[i];
        i++;
        return item;
    }

    @Override
    public void remove() {
        throw new java.lang.UnsupportedOperationException("remove is not supported");
    }

}

public void enqueue(Item item){
    if(item==null){
        throw new java.lang.NullPointerException("can't insert null items"); 
    }

    if(N==queue.length){
        resize(2*queue.length);
    }
    queue[N++]=item;
}           // add the item
public Item dequeue(){
    if(isEmpty()){
        throw new java.util.NoSuchElementException("queue is empty");
    }
    int i=StdRandom.uniform(0, N);
    Item item=queue[i];
    exchange(i,N-1);
    N=N-1;
    queue[N]=null;
    return item;
}                    // remove and return a random item
public Item sample(){
    if(isEmpty()){
        throw new java.util.NoSuchElementException("queue is empty");
    }
    int i=StdRandom.uniform(0,N);
    return queue[i];
}                     // return (but do not remove) a random item
public Iterator<Item> iterator(){
   return new QueueIterator();
}         // return an independent iterator over items in random order
private void exchange( int i, int j){
    Item swap=queue[i];
    queue[i]=queue[j];
    queue[j]=swap;
}

private void shuffle(){
    for(int i=0;i<N;i++){
        int j=StdRandom.uniform(0, i);
        exchange(i,j);
    }
}

Answer 1

在方法shuffle()中:

private void shuffle(){
    for(int i=0;i<N;i++){
        int j=StdRandom.uniform(0, i);
        exchange(i,j);
    }
}

在第一次迭代中，当您调用 StdRandom.uniform(0, 0) 时，它会抛出异常，因为第二个参数必须严格大于第一个。可能您应该更改 for 循环，使 i 的最小值为 1。

来自documentation :

uniform

public static int uniform(int a, int b)

Returns an integer uniformly in [a, b).

Throws:

IllegalArgumentException - if b <= a

IllegalArgumentException - if b - a >= Integer.MAX_VALUE