diff options
4 files changed, 168 insertions, 25 deletions
diff --git a/Algorithms/Part-I/2-Randomized_Queues_Deques/Deque.java b/Algorithms/Part-I/2-Randomized_Queues_Deques/Deque.java index e8a17de..d27629f 100644 --- a/Algorithms/Part-I/2-Randomized_Queues_Deques/Deque.java +++ b/Algorithms/Part-I/2-Randomized_Queues_Deques/Deque.java @@ -10,9 +10,9 @@ public class Deque<Item> implements Iterable<Item> private class Node { - Item item; - Node next; - Node prev; + private Item item; + private Node next; + private Node prev; } // construct an empty deque @@ -24,16 +24,10 @@ public class Deque<Item> implements Iterable<Item> } // is the deque empty? - public boolean isEmpty() - { - return (head == null); - } + public boolean isEmpty() { return n == 0; } // return the number of items on the deque - public int size() - { - return n; - } + public int size() { return n; } // insert the item at the front public void addFirst(Item item) @@ -43,8 +37,11 @@ public class Deque<Item> implements Iterable<Item> node.item = item; node.next = head; node.prev = null; + if (head == null) + tail = node; + else + head.prev = node; head = node; - if (tail == null) tail = head; n++; } @@ -57,14 +54,10 @@ public class Deque<Item> implements Iterable<Item> node.next = null; node.prev = tail; if (tail == null) - { - head = tail = node; - } + head = node; else - { tail.next = node; - tail = tail.next; - } + tail = node; n++; } @@ -73,9 +66,18 @@ public class Deque<Item> implements Iterable<Item> { if (head == null) throw new java.util.NoSuchElementException(); Item item = head.item; - if (tail == head) tail = tail.next; - head = head.next; - head.prev = null; + if (head == tail) // head.next == null + { + head = null; + tail = null; + } + else + { + Node prevHead = head; + head = head.next; + head.prev = null; + prevHead.next = null; + } n--; return item; } @@ -85,14 +87,17 @@ public class Deque<Item> implements Iterable<Item> { if (tail == null) throw new java.util.NoSuchElementException(); Item item = tail.item; - if (head == tail) + if (head == tail) // tail.prev == null { - head = tail = null; + head = null; + tail = null; } else { + Node prevTail = tail; tail = tail.prev; tail.next = null; + prevTail.prev = null; } n--; return item; @@ -105,8 +110,10 @@ public class Deque<Item> implements Iterable<Item> { private Node current = head; - public boolean hasNext() { return current != null; } - public void remove() { throw new java.lang.UnsupportedOperationException(); } + public boolean hasNext() + { return current != null; } + public void remove() + { throw new java.lang.UnsupportedOperationException(); } public Item next() { if (current == null) throw new java.util.NoSuchElementException(); 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; + } + } +} diff --git a/Algorithms/Part-I/2-Randomized_Queues_Deques/Subset.java b/Algorithms/Part-I/2-Randomized_Queues_Deques/Subset.java new file mode 100644 index 0000000..61a8502 --- /dev/null +++ b/Algorithms/Part-I/2-Randomized_Queues_Deques/Subset.java @@ -0,0 +1,18 @@ +/* vim: set expandtab tabstop=4 shiftwidth=4 : */ + +public class Subset +{ + public static void main(String[] args) + { + int k = Integer.parseInt(args[0]); + if (k == 0) return; + RandomizedQueue<String> q = new RandomizedQueue<String>(); + while (!StdIn.isEmpty()) + { + q.enqueue(StdIn.readString()); + } + for (int i = 0; i < k; i++) + System.out.println(q.dequeue()); + System.out.println(); + } +} diff --git a/Algorithms/Part-I/2-Randomized_Queues_Deques/run.sh b/Algorithms/Part-I/2-Randomized_Queues_Deques/run.sh new file mode 100755 index 0000000..6adde6d --- /dev/null +++ b/Algorithms/Part-I/2-Randomized_Queues_Deques/run.sh @@ -0,0 +1,21 @@ +#! /bin/bash + +export "CLASSPATH=$CLASSPATH:.:$HOME/algs4/algs4.jar:$HOME/algs4/stdlib.jar" + +CLASSES="Deque RandomizedQueue Subset" + +rm *.class *.zip 2>/dev/null + +for kls in $CLASSES; do + ~/algs4/bin/checkstyle ${kls}.java + javac ${kls}.java +done +~/algs4/bin/findbugs *.class + +echo "RUN..." +echo A B C D E F G H I | java Subset 3 +echo A B C D E F G H I | java Subset 3 +echo A B C D E F G H I | java Subset 3 +echo AA BB BB BB BB BB CC CC | java Subset 8 + +zip queues.zip Deque.java RandomizedQueue.java Subset.java |