001package algs33;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac RandomizedQueue.java
005 *  Execution:    java RandomizedQueue
006 *
007 *  Implement a randomized queue in log N time per operation in the
008 *  worst case.
009 *
010 *************************************************************************/
011
012public class XRandomizedQueue<T> {
013
014        private RedBlackBST<Integer, T> st = new RedBlackBST<>();
015
016        public XRandomizedQueue() { }
017
018        // add the item to the randomized queue
019        public void enqueue(T item) {
020                int N = st.size();
021                int r = StdRandom.uniform(N+1);
022                // r is between 0 and N, inclusive
023                // initially N == r == 0
024                //   st.get returns null if item not there
025                //   so, initially, the next line does nothing
026                st.put(N, st.get(r));
027                st.put(r, item);
028                // StdOut.format ("N=%d r=%d\n", N, r);
029        }
030
031        // delete and return a random item from the queue
032        public T dequeue() {
033                int N = st.size();
034                if (N == 0) throw new Error("Randomized queue underflow");
035                T item = st.get(N-1);
036                st.delete(N-1);
037                return item;
038        }
039
040
041        /* ***********************************************************************
042         *  Test client
043         *************************************************************************/
044        public static void main(String[] args) {
045                args = new String[] { "10000", "20" };
046                int N = Integer.parseInt(args[0]);
047                int k = Integer.parseInt(args[1]);
048                XRandomizedQueue<Integer> queue = new XRandomizedQueue<>();
049                for (int i = 0; i < N; i++)
050                        queue.enqueue(i);
051
052                for (int i = 0; i < k; i++)
053                        StdOut.println(queue.dequeue());
054        }
055}