Class RandomizedQueue

02Lab-Queues/RandomizedQueue.java:13–128

import java.util.NoSuchElementException;

public class RandomizedQueue<Item> implements Iterable<Item> {
    private static final int INIT_CAPACITY = 8;
    private int n;
    private Item[] v;
    private int first;
    private int last;

    // construct an empty randomized queue
    public RandomizedQueue() {
        v = (Item[]) new Object[INIT_CAPACITY];
        n = 0;
        first = 0;
        last = 0;
    }

    // is the randomized queue empty?
    public boolean isEmpty() {
        return n == 0;
    }

    // return the number of items on the randomized queue
    public int size() {
        return n;
    }

    private void resize(int capacity) {
        Item[] copy = (Item[]) new Object[capacity];
        for (int i = 0; i < n; i++)
            copy[i] = v[(first + i) % v.length];
        v = copy;
        first = 0;
        last = n;
    }

    // add the item
    public void enqueue(Item item) {
        if (item == null) throw new IllegalArgumentException();
        if (n == v.length) resize(2 * v.length);
        v[last++] = item;
        if (last == v.length) last = 0;
        n++;
    }

    // remove and return a random item
    public Item dequeue() {
        if (isEmpty()) throw new NoSuchElementException();
        int id = (first + StdRandom.uniformInt(n)) % v.length;
        Item item = v[id];
        v[id] = v[first];
        v[first++] = null;
        n--;
        if (first == v.length) first = 0;
        if (n > 0 && n == v.length / 4) resize(v.length / 2);
        return item;
    }

    // return a random item (but do not remove it)
    public Item sample() {