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}