Advertisement
zinch

Randomized Queue

Feb 20th, 2014
363
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.91 KB | None | 0 0
  1. import java.util.Arrays;
  2. import java.util.Iterator;
  3. import java.util.NoSuchElementException;
  4. import java.util.Random;
  5.  
  6. public class RandomizedQueue<Item> implements Iterable<Item> {
  7.  
  8.     private Item[] data;
  9.     private int size;
  10.  
  11.     public RandomizedQueue() {
  12.         data = (Item[]) new Object[10];
  13.     }
  14.  
  15.     public void enque(Item item) {
  16.         if (size == data.length) {
  17.             ensureCapacity(size * 2);
  18.         }
  19.  
  20.         data[size++] = item;
  21.     }
  22.  
  23.     public Item deque() {
  24.  
  25.         Random random = new Random();
  26.  
  27.         int index = random.nextInt(size);
  28.  
  29.         Item item = data[index];
  30.         data[index] = data[size - 1];
  31.         data[size - 1] = null;
  32.  
  33.         --size;
  34.  
  35.         if (size <= data.length / 4) {
  36.             ensureCapacity(data.length / 2);
  37.         }
  38.  
  39.         return item;
  40.     }
  41.  
  42.     public int size() {
  43.         return size;
  44.     }
  45.  
  46.     public boolean isEmpty() {
  47.         return size == 0;
  48.     }
  49.  
  50.     @Override
  51.     public Iterator<Item> iterator() {
  52.  
  53.         return new Iterator<Item>() {
  54.  
  55.             Item[] localData = Arrays.copyOf(data, RandomizedQueue.this.size);
  56.             int size = localData.length;
  57.  
  58.             @Override
  59.             public boolean hasNext() {
  60.                 return size > 0;
  61.             }
  62.  
  63.             @Override
  64.             public Item next() {
  65.                 if (!hasNext()) {
  66.                     throw new NoSuchElementException();
  67.                 }
  68.  
  69.                 Random random = new Random();
  70.  
  71.                 int index = random.nextInt(size);
  72.  
  73.                 Item item = localData[index];
  74.                 localData[index] = localData[size - 1];
  75.                 localData[size - 1] = null;
  76.  
  77.                 --size;
  78.  
  79.                 return item;
  80.             }
  81.  
  82.             @Override
  83.             public void remove() {
  84.  
  85.             }
  86.         };
  87.     }
  88.  
  89.     private void ensureCapacity(int length) {
  90.  
  91.         Item[] items = Arrays.copyOf(data, length);
  92.         data = items;
  93.     }
  94.  
  95.  
  96.     public static void main(String[] args) {
  97.         RandomizedQueue<Integer> rQueue = new RandomizedQueue<Integer>();
  98.  
  99.         System.out.println("length = " + ((Object[]) rQueue.data).length);
  100.  
  101.         for (int i = 0; i < 11; i++) {
  102.             rQueue.enque(i);
  103.         }
  104.  
  105.         System.out.println("length = " + ((Object[]) rQueue.data).length);
  106.  
  107.         while (!rQueue.isEmpty()) {
  108.             System.out.print(" " + rQueue.deque());
  109.         }
  110.         System.out.println();
  111.  
  112.         System.out.println("length = " + ((Object[]) rQueue.data).length);
  113.  
  114.         RandomizedQueue<String> stringRandomizedQueue = new RandomizedQueue<String>();
  115.  
  116.         for (int i = 65; i < 91; i++) {
  117.             stringRandomizedQueue.enque(String.valueOf((char) i));
  118.         }
  119.  
  120.         for(String str : stringRandomizedQueue) {
  121.             System.out.print(" " + str);
  122.         }
  123.  
  124.         System.out.println();
  125.     }
  126. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement