SHARE
TWEET

ResizableQueue

a guest Jul 5th, 2014 188 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Iterator;
  2.  
  3. class Queue<T> implements Iterable<T> {
  4.  
  5.   private class QueueIterator implements Iterator<T> {
  6.  
  7.     private int curr = head;
  8.  
  9.     public boolean hasNext() {
  10.       return curr != tail;
  11.     }
  12.     public void remove() {
  13.       throw new UnsupportedOperationException();
  14.     }
  15.     public T next() {
  16.       return data[curr++];
  17.     }
  18.   }
  19.   private T[] data;
  20.   private int head, tail;
  21.   public Iterator<T> iterator() {
  22.     return new QueueIterator();
  23.   }
  24.  
  25.  
  26.   public Queue() {
  27.     data = (T[]) new Object[2];
  28.     head = 0;
  29.     tail = 0;
  30.   }
  31.  
  32.   public int size() {
  33.     return tail - head;
  34.   }
  35.  
  36.   public boolean isEmpty() {
  37.     return size() == 0;
  38.   }
  39.  
  40.   private void realign() {
  41.     java.util.Arrays.sort(data, new java.util.Comparator<Object>() {
  42.       public int compare(Object o1, Object o2) {
  43.         if (o1 == null) return 1;
  44.         else if(o2 == null) return -1;
  45.         else return 0;
  46.       }
  47.     });
  48.     tail -= head;
  49.     head = 0;
  50.   }
  51.  
  52.   private void resize() {
  53.     if (tail == data.length && size() != data.length) {
  54.       realign();
  55.     }
  56.     if (data.length == size()) {
  57.       int newLength = data.length * 2;
  58.       T[] newData = (T[]) new Object[newLength];
  59.       System.arraycopy(data, 0, newData, 0, data.length);
  60.       data = newData;
  61.     } else if (size() == data.length / 4 && size() != 0) {
  62.       int newLength = data.length / 2;
  63.       T[] newData = (T[]) new Object[newLength];
  64.       System.arraycopy(data, 0, newData, 0, data.length);
  65.       data = newData;
  66.     }
  67.   }
  68.  
  69.   public void enqueue(T item) {
  70.     if (item == null) { throw new NullPointerException(); }
  71.     resize();
  72.     data[tail] = item;
  73.     tail++;
  74.     return;
  75.   }
  76.  
  77.   public T dequeue() {
  78.     if (isEmpty()) { throw new java.util.NoSuchElementException(); }
  79.     T res = data[head];
  80.     data[head] = null;
  81.     head++;  
  82.     if (head == tail) {
  83.       head = tail = 0;
  84.     }
  85.     return res;
  86.   }
  87. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top