001// Exercise 4.3.36 002package algs13; 003import stdlib.*; 004import java.util.Iterator; 005public class MyRandomQueue<T> implements Iterable<T> { 006 007 /** Create an empty random queue. */ 008 public MyRandomQueue () {} 009 010 /** Is it empty? */ 011 public boolean isEmpty () { 012 return true; 013 } 014 015 /** Return the number of elements. */ 016 public int size () { 017 return 0; 018 } 019 020 /** Add an item. */ 021 public void enqueue (T item) {} 022 023 /** Return (but do not remove) a random item. */ 024 public T sample () { 025 return null; 026 } 027 028 /** Remove and return a random item. */ 029 public T dequeue () { 030 return null; 031 } 032 033 /** Return an iterator over the items in random order. */ 034 public Iterator<T> iterator () { 035 return new QueueIterator (); 036 } 037 038 // an iterator, doesn't implement remove() since it's optional 039 private class QueueIterator implements Iterator<T> { 040 public boolean hasNext () { return false; } 041 public T next () { return null; } 042 public void remove () {} 043 } 044 045 // Test code from https://blog.itu.dk/BADS-F2011/2011/02/10/programming-exercise-3-randomqueue/ 046 public static void main (String args[]) { 047 int NUMROLLS = 10000; 048 // Build a queue containing the Integers 1,2,...,6: 049 MyRandomQueue<Integer> q1 = new MyRandomQueue<> (); 050 for (int i = 1; i < 7; ++i) 051 q1.enqueue (i); // autoboxing! cool! 052 053 // Print 30 die rolls to standard output 054 StdOut.print ("Some die rolls: "); 055 for (int i = 1; i < 30; ++i) 056 StdOut.print (q1.sample () + " "); 057 StdOut.println (); 058 059 // Let's be more serious: do they really behave like die rolls? 060 int[] rolls = new int[NUMROLLS]; 061 for (int i = 0; i < NUMROLLS; ++i) 062 rolls[i] = q1.sample (); // autounboxing! Also cool! 063 StdOut.format ("Mean (should be around 3.5): %5.4f\n", StdStats.mean (rolls)); 064 StdOut.format ("Standard deviation (should be around 1.7): %5.4f\n", StdStats.stddev (rolls)); 065 066 // Let's look at the iterator. First, we make a queue of colours: 067 MyRandomQueue<String> q2 = new MyRandomQueue<> (); 068 q2.enqueue ("red"); 069 q2.enqueue ("blue"); 070 q2.enqueue ("green"); 071 q2.enqueue ("yellow"); //q2.print (); 072 q2.dequeue (); //q2.print (); 073 q2.dequeue (); //q2.print (); 074 q2.enqueue ("purple"); //q2.print (); 075 q2.enqueue ("orange"); //q2.print (); 076 077 Iterator<String> it1 = q2.iterator (); 078 Iterator<String> it2 = q2.iterator (); 079 080 StdOut.print ("Two colours from first shuffle: "); 081 StdOut.print (it1.next () + " "); 082 StdOut.print (it1.next () + " "); 083 084 StdOut.print ("\nEntire second shuffle: "); 085 while (it2.hasNext ()) 086 StdOut.print (it2.next () + " "); 087 088 StdOut.print ("\nRemaining two colours from first shuffle: "); 089 StdOut.print (it1.next () + " "); 090 StdOut.println (it1.next ()); 091 092 Stopwatch s = new Stopwatch (); 093 int[][] irolls = new int[6][NUMROLLS]; 094 for (int i = 0; i < NUMROLLS; ++i) { 095 Iterator<Integer> it3 = q1.iterator (); 096 for (int j = 0; j < 6; j++) 097 irolls[j][i] = it3.next (); 098 } 099 StdOut.format ("Elapsed time: %5.4f\n", s.elapsedTime ()); 100 for (int j = 0; j < 6; j++) { 101 StdOut.format ("Mean (should be around 3.5): %5.4f\n", StdStats.mean (irolls[j])); 102 StdOut.format ("Standard deviation (should be around 1.7): %5.4f\n", StdStats.stddev (irolls[j])); 103 } 104 } 105 106}