Princeton Algorithm Part 1 Week

今天做RandomizedQueue， 我用了一个环状结构的list实现了。 我也用纯array做了一遍，只是在很大的数据量下速度跟不上。还未提交。

Today's assignment is RandomizedQueue. The following code is based on a loop , named by me, data structure. I also did another one based on object array only, which was too expensive. This solution has not yet been submitted.

import java.util.Iterator;

import edu.princeton.cs.algs4.StdRandom;

public class RandomizedQueue<Item> implements Iterable<Item> {
    private Node looper = new Node();
    private int  size   = 0;

    public RandomizedQueue() {
        looper.next = looper;
    }

    private class Node {
        Item item;
        Node next;
    }

    public boolean isEmpty() {
        return looper.next == looper;
    }

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

    public void enqueue(Item item) {
        if (item == null)
            throw new java.lang.IllegalArgumentException();
        Node node = new Node();
        node.next = looper.next;
        looper.next = node;
        node.item = item;
        size++;
    }

    public Item dequeue() {
        if (size == 0)
            throw new java.util.NoSuchElementException();
        Node node = looper;
        for (int i = 0; i < StdRandom.uniform(size); i++) {
            node = node.next;
        }
        Item result = node.next.item;
        node.next = node.next.next;
        size--;
        return result;
    }

    public Item sample() {
        if (size == 0)
            throw new java.util.NoSuchElementException();
        Node node = looper;
        for (int i = 0; i < StdRandom.uniform(size); i++) {
            node = node.next;
        }
        return node.next.item;
    }

    @Override
    public Iterator<Item> iterator() {
        // TODO Auto-generated method stub
        return new RandIterator();
    }

    private class RandIterator implements Iterator<Item> {
        Object[] arr   = new Object[size];
        int      count = 0;

        public RandIterator() {
            Node node = looper;
            for (int i = 0; i < size; i++) {
                arr[i] = node.next.item;
                node = node.next;
            }
            StdRandom.shuffle(arr);
        }

        @Override
        public boolean hasNext() {
            return count != size;
        }

        @Override
        public Item next() {
            return (Item) arr[count++];
        }
    }

    public static void main(String[] args) {
    }
}