随机队列

随机队列：考虑删除数据项时采用是否重复抽样的规则，方法dequeue()移除并返回一个随机项（不重置抽样），方法sample()返回一个随机项而不从队列中移除它（重置抽样）

//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by Fernflower decompiler)
//

import java.util.Iterator;
import java.util.NoSuchElementException;

//随机队列：考虑删除数据项时采用其他规则，方法dequeue()移除并返回一个随机项（不重置抽样），方法sample()返回一个随机项而不从队列中移除它（重置抽样）

public class RandomQueue<Item> implements Iterable<Item> {
   
    private static final int INIT_CAPACITY = 2;
	//这里的数组a.length()与N是未必等大的，a.length()表示数组大小长度，N表示数据项长度，在数组“有空余”的情况下，N < a.length();
    private Item[] a = (Object[])(new Object[2]);
    private int N = 0;

    public RandomQueue() {
   
    }

    public boolean isEmpty() {
   
        return this.N == 0;
    }

    public int size() {
   
        return this.N;
    }

    private void resize(int var1) {
   
        Object[] var2 = (Object[])(new Object[var1]);

        for(int var3 = 0; var3 < this.N; ++var3) {
   
            var2[var3] = this.a[var3];
        }

        this.a = var2;
    }

    public void enqueue(Item var1) {
   
        if (this.N == this.a.length) {
   
			//容量不够时，数组长度加倍：
            this.resize(2 * this.a.length);
        }

        this.a[this.N++] = var1;
    }

    public Item sample() {
   
		//返回一个随机项而不从队列中移除它（重置抽样）
        if (this.isEmpty()) {
   
            throw new RuntimeException("Randomized queue underflow");
        } else {
   
            int var1 = StdRandom.uniform(this.N);
            return this.a[var1];
        }
    }

    public Item dequeue() {
   
		//移除并返回一个随机项（不重置抽样）
        if (this.isEmpty()) {
   
            throw new RuntimeException("Randomized queue underflow");
        } else {
     //此时N>=1;
            int var1 = StdRandom.uniform(this.N);
            Object var2 = this.a[var1];
			//由于是随机队列，这里不重新拷贝复制数据到新数组中，而是将最后一位数据项补充到移除的数据项的位置上。
            this.a[var1] = this.a[this.N - 1];
            this.a[this.N - 1] = null;
            --this.N;
			//数组空余量过大的时候，调整数组空余量
            if (this.N > 0 && this.N == this.a.length / 4) {
   
                this.resize(this.a.length / 2);
            }

            return var2;
        }
    }

    public Iterator<Item> iterator() {
   
        return new RandomQueue.RandomIterator();
    }

    private class RandomIterator implements Iterator<Item> {
   
        private RandomQueue<Item> copy = new RandomQueue();

        public RandomIterator() {
   
            for(int var2 = 0; var2 < RandomQueue.this.N; ++var2) {
   
                this.copy.enqueue(RandomQueue.this.a[var2]);
            }

        }

        public boolean hasNext() {
   
            return !this.copy.isEmpty();
        }

        public void remove() {
   
            throw new UnsupportedOperationException();
        }

        public Item next() {
   
            if (!this.hasNext()) {
   
                throw new NoSuchElementException();
            } else {
   
                return this.copy.dequeue();
            }
        }
    }
}