001// Exercise 1.3.14 (Solution published at http://algs4.cs.princeton.edu/) 002package algs13; 003import stdlib.*; 004import java.util.Iterator; 005import java.util.NoSuchElementException; 006/* *********************************************************************** 007 * Compilation: javac ResizingArrayQueue.java 008 * Execution: java ResizingArrayQueue < input.txt 009 * Data files: http://algs4.cs.princeton.edu/13stacks/tobe.txt 010 * 011 * Queue implementation with a resizing array. 012 * 013 * % java ResizingArrayQueue < tobe.txt 014 * to be or not to be (2 left on queue) 015 * 016 *************************************************************************/ 017 018public class ResizingArrayQueue<T> implements Iterable<T> { 019 private T[] q; // queue elements 020 private int N; // number of elements on queue 021 private int first; // index of first element of queue 022 private int last; // index of next available slot 023 024 // cast needed since no generic array creation in Java 025 @SuppressWarnings("unchecked") 026 public ResizingArrayQueue() { 027 this.q = (T[]) new Object[2]; 028 this.N = 0; 029 this.first = 0; 030 this.last = 0; 031 } 032 033 public boolean isEmpty() { return N == 0; } 034 public int size() { return N; } 035 036 @SuppressWarnings("unchecked") 037 private void resize(int capacity) { 038 if (capacity <= N) throw new IllegalArgumentException (); 039 T[] temp = (T[]) new Object[capacity]; 040 for (int i = 0; i < N; i++) temp[i] = q[(first + i) % q.length]; 041 q = temp; 042 first = 0; 043 last = N; 044 } 045 046 public void enqueue(T item) { 047 if (N == q.length) resize(2*q.length); // double size of array if necessary 048 q[last] = item; // add item 049 last = (last + 1) % q.length; 050 N++; 051 } 052 053 // remove the least recently added item 054 public T dequeue() { 055 if (isEmpty()) throw new Error("Queue underflow"); 056 T item = q[first]; 057 q[first] = null; // to avoid loitering 058 N--; 059 first = (first + 1) % q.length; 060 if (N > 0 && N == q.length/4) resize(q.length/2); // shrink size of array if necessary 061 return item; 062 } 063 064 public Iterator<T> iterator() { return new ArrayIterator(); } 065 private class ArrayIterator implements Iterator<T> { 066 private int i = 0; 067 public boolean hasNext() { return i < N; } 068 public void remove() { throw new UnsupportedOperationException(); } 069 070 public T next() { 071 if (!hasNext()) throw new NoSuchElementException(); 072 T item = q[(first + i) % q.length]; 073 i++; 074 return item; 075 } 076 } 077 078 public String toString () { 079 if (isEmpty()) return "[]"; 080 StringBuilder sb = new StringBuilder ("["); 081 Iterator<T> i = iterator(); 082 sb.append (i.next ()); 083 while (i.hasNext ()) { 084 sb.append (" "); 085 sb.append (i.next ()); 086 } 087 sb.append ("]"); 088 return sb.toString (); 089 } 090 private void check (String expected) { 091 if (N<0 || N>q.length) throw new Error (); 092 if (N==0 && q.length!=2) throw new Error ("Expected length 2, got " + q.length); 093 if (N!=0 && N<q.length/4) throw new Error (); 094 if (((first + N) % q.length) != last) throw new Error (); 095 for (int i=0; i<N; i++) { 096 if (q[(first + i) % q.length] == null) throw new Error (); 097 } 098 for (int i=N; i<q.length; i++) { 099 if (q[(first + i) % q.length] != null) throw new Error (); 100 } 101 if (expected != null) { 102 if (!expected.equals(this.toString ())) throw new Error ("Expected \"" + expected + "\", got \"" + this + "\""); 103 } 104 StdOut.println (this); 105 } 106 private void check (T iExpected, T iActual, String expected) { 107 if (!iExpected.equals (iActual)) throw new Error ("Expected \"" + iExpected + "\", got \"" + iActual + "\""); 108 check (expected); 109 } 110 public static void mainx (String args[]) { 111 ResizingArrayQueue<Integer> d1; 112 Integer k; 113 d1 = new ResizingArrayQueue<> (); 114 d1.enqueue (11); d1.check ("[11]"); 115 d1.enqueue (12); d1.check ("[11 12]"); 116 k = d1.dequeue(); d1.check (11, k, "[12]"); 117 k = d1.dequeue(); d1.check (12, k, "[]"); 118 119 d1 = new ResizingArrayQueue<> (); 120 for (int i = 10; i < 20; i++) 121 d1.enqueue (i); 122 d1.check ("[10 11 12 13 14 15 16 17 18 19]"); 123 124 for (int i = 0; i < 10; i++) { 125 d1.dequeue (); d1.check (null); 126 } 127 try { d1.dequeue (); throw new Error ("Expected exception"); } catch (Error e) {} 128 } 129 130 // A test client 131 public static void main (String[] args) { 132 StdIn.fromString ("to be or not to - be - - that - - - is"); 133 134 ResizingArrayQueue<String> q = new ResizingArrayQueue<>(); 135 while (!StdIn.isEmpty()) { 136 String item = StdIn.readString(); 137 if (!item.equals("-")) q.enqueue(item); 138 else StdOut.print(q.dequeue() + " "); 139 } 140 StdOut.println("(" + q.size() + " left on queue)"); 141 } 142}