- import edu.princeton.cs.algs4.*;
- import java.util.Iterator;// 注意别忘记
- public class RandomQueue<Item> implements Iterable<Item>
- {
- private Item [] a;
- int N;
- public RandomQueue()
- {
- a = (Item[]) new Object[1];
- }
- public boolean isEmpty()
- {
- return N == 0;
- }
- public void enqueue(Item item)
- {
- if(N == a.length)
- {
- resizing(a.length * 2);
- }
- a[N++] = item;
- }
- public void resizing(int size)
- {
- Item [] p = (Item[]) new Object[size];
- for(int i = 0; i <N; i++)
- {
- p[i] = a[i];
- }
- a = p;
- }
- public Item dequeue()// 随机删除一项并拿最后一项来补删除的那项
- {
- if(this.isEmpty())
- {
- return null;
- }
- if(N == a.length / 4)
- {
- resizing(a.length / 2);
- }
- int index = StdRandom.uniform(N);//p30 页, integer between 0 and N-1
- Item x = a[index];
- a[index] = a[--N];
- a[N] = null;
- return x;
- }
- public Item sample()
- {
- int index = StdRandom.uniform(N);
- return a[index];
- }
- public Iterator<Item> iterator()
- {
- return new RandomQueueIterator();
- }
- public class RandomQueueIterator implements Iterator<Item>
- {
- private Item[] temp;
- private int index;
- public RandomQueueIterator()
- {
- temp = (Item[]) new Object[N];
- for(int i = 0; i <N; i++)
- {
- temp[i] = a[i];
- }
- StdRandom.shuffle(temp);//p30,randomly shuffle the array a[]
- index = 0;
- }
- public boolean hasNext()
- {
- return index < N;
- }
- public Item next()
- {
- return temp[index++];
- }
- public void remove()
- {
- }
- }
- public static void main(String[] args)
- {
- RandomQueue<Integer> queue = new RandomQueue<Integer>();
- for(int i = 1; i <= 52; i++)
- {
- queue.enqueue(i);
- }
- for(Integer integer : queue)
- {
- StdOut.print(integer + "\t");
- }
- StdOut.print("\n");
- }
- }
来源: http://www.bubuko.com/infodetail-2612760.html