import java.util.Iterator; import java.util.NoSuchElementException; import stdlib.StdOut; import stdlib.StdRandom; // A data type to represent a random queue, implemented using a resizing array as the underlying // data structure. public class ResizingArrayRandomQueue implements Iterable { ... // Constructs an empty random queue. public ResizingArrayRandomQueue() { ... } // Returns true if this queue is empty, and false otherwise. public boolean isEmpty() { ... } // Returns the number of items in this queue. public int size() { ... } // Adds item to the end of this queue. public void enqueue(Item item) { ... } // Returns a random item from this queue. public Item sample() { ... } // Removes and returns a random item from this queue. public Item dequeue() { ... } // Returns an independent iterator to iterate over the items in this queue in random order. public Iterator iterator() { ... } // Returns a string representation of this queue. public String toString() { StringBuilder sb = new StringBuilder(); for (Item item : this) { sb.append(item); sb.append(", "); } return n > 0 ? "[" + sb.substring(0, sb.length() - 2) + "]" : "[]"; } // An iterator, doesn't implement remove() since it's optional. private class RandomQueueIterator implements Iterator { ... // Constructs an iterator. public RandomQueueIterator() { ... } // Returns true if there are more items to iterate, and false otherwise. public boolean hasNext() { ... } // Returns the next item. public Item next() { ... } // Unsupported method. public void remove() { throw new UnsupportedOperationException("remove() is not supported"); } } // Resizes the underlying array. private void resize(int max) { Item[] temp = (Item[]) new Object[max]; for (int i = 0; i i++) { if (q[i] != null) { temp[i] = q[i]; } } q = temp; } // Unit tests the data type. [DO NOT EDIT] public static void main(String[] args) { ResizingArrayRandomQueue q = new ResizingArrayRandomQueue(); int sum = 0; for (int i = 0; i i++) { int r = StdRandom.uniform(10000); q.enqueue(r); sum += r; } int iterSumQ = 0; for (int x : q) { iterSumQ += x; } int dequeSumQ = 0; while (q.size() > 0) { dequeSumQ += q.dequeue(); } StdOut.println("sum = " + sum); StdOut.println("iterSumQ = " + iterSumQ); StdOut.println("dequeSumQ = " + dequeSumQ); StdOut.println("iterSumQ + dequeSumQ == 2 * sum? " + (iterSumQ + dequeSumQ == 2 * sum)); } } 

Problem 3. (Random Queue) A random queue is similar to a stack or queue, except that the item removed is chosen uniformly at random from items in the data structure. Create a generic, iterable data type called ResizingArrayRandomQueue that uses a resizing array to implement the following random queue API: E ResizingArrayRandomQueue ResizingArrayRandomQueue () boolean isEmpty() int size void enqueue (Item item) Item sample) Item dequeue () Iterator iterator() String toString() constructs an empty random queue returns true if this queue is empty, and false otherwise returns the number of items in this queue adds item to the end of this queue returns a random item from this queue removes and returns a random item from this queue returns an independent iterator to iterate over the items in this queue in random order returns a string representation of this queue The order of two or more iterators on the same randomized queue must be mutually independent, ie, each iterator must maintain its own random order. Corner Cases The enqueue () method should throw a NullPointerException("item is null") if item is null. The sample() and dequeue () methods should throw a NoSuchElementException("Random queue is empty") the random queue is empty. The next() method in the random queue iterator shoud throw a NoSuchElementException("Iterator is empty") if there are no more items to iterate. Performance Requirements The constructor and methods in ResizingArrayRandomQueue should run in time T(n) ~ 1. The constructor in RandomQueue Iterator should run in time T(n) ~n. The methods in RandomQueue Iterator should run in time T(n) ~ 1. >_*/workspace/project2 $ java ResizingArrayRandom Queue sum = 5081434 iterSum Q = 5081434 de que Sum Q = 5081434 iterSum Q + de que Sum Q == 2 * sum? true Problem 3. (Random Queue) Hints: Use a resizing array to implement the API Instance variables Array to store the items of queue, Item [] q Size of the queue, int n ResizingArrayRandomQueue () Initialize instance variables appropriately create a with an initial capacity of 2 boolean isEmpty() Return whether the queue is empty or not int size() Return the size of the queue void enqueue (Item item) If q is at full capacity, resize it to twice its current capacity Insert the given item in at index n. Increment n by one q Item sample) Return q[r], where r is a random integer from the interval [0, n) Item dequeue () Save q[r] in item, where r is a random integer from the interval [0, n) Set q[r] to q[n - 1] and q[n - 1] to null If q is at quarter capacity, resize it to half its current capacity Decrement n by one Return item Iterator iterator) Return an object of type RandomQueueIterator ResizingArrayRandomQueue :: RandomQueueIterator) Instance variables Array to store the items of q, Item [] items Index of the current item in items, int current RandomQueueIterator) Create items with capacity n Copy the n items from q into items Shuffle items Initialize current appropriately boolean hasNext() Return whether the iterator has more items to iterate or not Item next() Return the item in items at index current and advance current by one 1 2 3 Gimport java.util.Iterator; import java.util. No SuchElementException; | import stdlib.Stdout; import stdlib.StdRandom; 4 5 6 7 8 // A data type to represent a random queue, implemented using a resizing array as the underlying // data structure. public class ResizingArrayRandomQueue implements Iterable { 9 10 11 12 // Constructs an empty random queue. public ResizingArrayRandomQueue () { 13 14 15 } 16 17 // Returns true if this queue is empty, and false otherwise. public boolean isEmpty() { 18 19 20 A } 21 22 // Returns the number of items in this queue. public int size() { 23 o 24 ... 25 } 26 27 // Adds item to the end of this queue. public void enqueue (Item item) { 28 29 30 A } 31 32 // Returns a random item from this queue. public Item sample() { 33 34 35 } 36 37 // Removes and returns a random item from this queue. public Item de queue() { 38 D 39 40 } 41 42 // Returns an independent iterator to iterate over the items in this queue in random order. public Iterator iterator() { 43 of 42 43 of 44 // Returns an independent iterator to iterate over the items in this queue in random order. public Iterator iterator() { 45 } 46 47 48 of 49 50 o // Returns a string representation of this queue. public String toString() { StringBuilder sb = new StringBuilder(); for (Item item : this) { sb.append(item); sb.append(", "); } return n > 0 ? "[" + sb.substring(0, sb.length() - 2) + "]" : "[]"; 51 52 53 54 55 56 57 // An iterator, doesn't implement remove() since it's optional. private class RandomQueueIterator implements Iterator { 58 59 60 61 // Constructs an iterator. public RandomQueueIterator() { 62 63 64 A } 65 66 // Returns true if there are more items to iterate, and false otherwise. public boolean hasNext() { 67 68 69 A } 70 71 72 of 73 // Returns the next item. public Item next() { 74 } . 75 76 77 of // Unsupported method. public void remove() { throw new UnsupportedoperationException("remove() is not supported"); } 78 79 80 } 81 81 82 83 84 85 D-D 86 // Resizes the underlying array. private void resize(int max) { Item[] temp = (Item[]) new Object[max]; for (int i 0; i q = new ResizingArrayRandomQueue (); int sum = 0; for (int i = 0; i 0) { deque SumQ += q.dequeue(); } Stdout.println("sum + sum); Stdout.println("iter SumQ iterSumq); Stdout.println("deque SumQ + deque Sumo); Stdout.println("iterSumQ + deque SumQ == 2 * sum? " + (iterSumQ + deque SumQ == 2 * sum)); } 104 105 A 106 107 108 109 110 111 112 113 114 115 }