1 files changed, 97 insertions, 0 deletions
diff --git a/Algorithms/Part-I/2-Randomized_Queues_Deques/RandomizedQueue.java b/Algorithms/Part-I/2-Randomized_Queues_Deques/RandomizedQueue.java
new file mode 100644
index 0000000..19d9295
--- /dev/null
+++ b/Algorithms/Part-I/2-Randomized_Queues_Deques/RandomizedQueue.java
@@ -0,0 +1,97 @@
+/* vim: set expandtab tabstop=4 shiftwidth=4 : */
+
+import java.util.Iterator;
+
+public class RandomizedQueue<Item> implements Iterable<Item>
+{
+    private int n;
+    private Item[] items;
+
+    // construct an empty randomized queue
+    public RandomizedQueue()
+    {
+        n = 0;
+        items = (Item[]) new Object[1];
+    }
+
+    // is the queue empty?
+    public boolean isEmpty() { return n == 0; }
+
+    // return the number of items on the queue
+    public int size() { return n; }
+
+    // add the item
+    public void enqueue(Item item)
+    {
+        if (item == null) throw new java.lang.NullPointerException();
+        if (n == items.length)
+        {
+            Item[] copy = (Item[]) new Object[n*2];
+            for (int i = 0; i < n; i++)
+                copy[i] = items[i];
+            items = copy;
+        }
+        items[n++] = item;
+    }
+
+    // delete and return a random item
+    public Item dequeue()
+    {
+        if (n == 0) throw new java.util.NoSuchElementException();
+        int r = StdRandom.uniform(n);
+        Item item = items[r];
+        items[r] = items[--n];
+        items[n] = null;
+        if (n > 0 && n == items.length/4)
+        {
+            Item[] copy = (Item[]) new Object[items.length/2];
+            for (int i = 0; i < n; i++)
+                copy[i] = items[i];
+            items = copy;
+        }
+        return item;
+    }
+
+    // return (but do not delete) a random item
+    public Item sample()
+    {
+        if (n == 0) throw new java.util.NoSuchElementException();
+        return items[StdRandom.uniform(n)];
+    }
+
+    // return an independent iterator over items in random order
+    public Iterator<Item> iterator() { return new RandomizedQueueIterator(); }
+
+    private class RandomizedQueueIterator implements Iterator<Item>
+    {
+        // must be random !!!!
+        private int idx;
+        private int[] random;
+
+        public RandomizedQueueIterator()
+        {
+            idx = 0;
+            random = new int[n];
+            for (int i = 0; i < n; i++)
+                random[i] = i;
+            for (int i = 0; i < n; i++)
+            {
+                int r = StdRandom.uniform(i + 1);
+                int tmp = random[i];
+                random[i] = random[r];
+                random[r] = tmp;
+            }
+        }
+
+        public boolean hasNext()
+        { return idx < n; }
+        public void remove()
+        { throw new java.lang.UnsupportedOperationException(); }
+        public Item next()
+        {
+            if (idx >= n) throw new java.util.NoSuchElementException();
+            Item item = items[random[idx++]];
+            return item;
+        }
+    }
+}