RandomizedQueue.java

package xyz.gummary;

import edu.princeton.cs.algs4.StdRandom;

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

/**
 * Created by admin on 2016/11/10.
 */
public class RandomizedQueue<Item> implements Iterable<Item> {

    private static final int InitSize = 10;
    private Item[] items;
    private int queueSize = 0;


    public RandomizedQueue() // construct an empty randomized queue
    {
        items = (Item[]) new Object[InitSize];
    }

    public boolean isEmpty() {
        return queueSize == 0;
    }

    public int size() {
        return queueSize;
    }

    public void enqueue(Item item) {

        if(item == null) {
            throw new NullPointerException();
        }

        if (queueSize == items.length) resize(queueSize * 2);

        items[queueSize++] = item;
    }

    public Item dequeue() {

        if(isEmpty()) throw new NoSuchElementException();

        int r = StdRandom.uniform(queueSize);
        Item temp = items[r];
        items[r] = items[queueSize - 1];
        items[queueSize - 1] = null;
        queueSize--;
        if (queueSize > 0 && queueSize < items.length / 4) {
            resize(items.length / 2);
        }
        return temp;
    }

    public Item sample() {
        if(isEmpty()) throw new NoSuchElementException();
        return items[StdRandom.uniform(queueSize)];
    }

    private void resize(int max) {
        Item[] temp = (Item[])new Object[max];
        for (int i = 0; i < queueSize; i++) {
            temp[i] = items[i];
        }
        items = temp;
    }

    @Override
    public Iterator<Item> iterator() {
        return new RandomQueueIterator();
    }

    private class RandomQueueIterator implements Iterator<Item> {

        Item[] a;
        int N;

        public RandomQueueIterator() {
            a = (Item[])new Object[queueSize];
            N = queueSize;
        }

        @Override
        public boolean hasNext() {
            return N != 0;
        }

        @Override
        public Item next() {

            if (!hasNext()) throw new NoSuchElementException();

            int r = StdRandom.uniform(queueSize);
            Item temp = a[r];
            a[r] = a[N - 1];
            a[N - 1] = null;
            N--;
            return temp;
        }

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