001package algs13; 002import stdlib.*; 003 004public class XResizingArrayQueueofStrings { 005 private String[] q; // queue elements 006 private int N; // number of elements on queue 007 private int first; // index of first element of queue 008 private int last; // index of next available slot 009 // Invariant (after the constructor): 010 // a[(first + 0) % q.length]..a[(first + N-1) % q.length] are non null 011 // a[(first + N) % q.length]..a[(first + a.length-1) % q.length] are null 012 public XResizingArrayQueueofStrings() { 013 this.q = new String[2]; 014 this.N = 0; 015 this.first = 0; 016 this.last = 0; 017 } 018 019 public boolean isEmpty() { return N == 0; } 020 public int size() { return N; } 021 022 private void resize(int capacity) { 023 if (capacity <= N) throw new IllegalArgumentException (); 024 String[] temp = new String[capacity]; 025 for (int i = 0; i < N; i++) { 026 temp[i] = q[(first + i) % q.length]; 027 } 028 q = temp; 029 first = 0; 030 last = N; 031 } 032 033 public void enqueue(String item) { 034 if (N == q.length) resize(2*q.length); // double size of array if necessary 035 q[last] = item; 036 last = (last + 1) % q.length; 037 N++; 038 } 039 040 // remove the least recently added item 041 public String dequeue() { 042 if (isEmpty()) throw new Error("Queue underflow"); 043 String item = q[first]; 044 q[first] = null; // to avoid loitering 045 N--; 046 first = (first + 1) % q.length; 047 if (N > 0 && N == q.length/4) resize(q.length/2); // shrink size of array if necessary 048 return item; 049 } 050 051 public String toString () { 052 if (isEmpty()) return "[]"; 053 StringBuilder sb = new StringBuilder ("["); 054 sb.append (q[first % q.length]); 055 int i = 1; 056 while (i < N) { 057 sb.append (" "); 058 sb.append (q[(first + i) % q.length]); 059 i++; 060 } 061 sb.append ("]"); 062 return sb.toString (); 063 } 064 private void check (String expected) { 065 if (N<0 || N>q.length) throw new Error (); 066 if (N==0 && q.length!=2) throw new Error ("Expected length 2, got " + q.length); 067 if (N!=0 && N<q.length/4) throw new Error (); 068 if (((first + N) % q.length) != last) throw new Error (); 069 for (int i=0; i<N; i++) { 070 if (q[(first + i) % q.length] == null) throw new Error (); 071 } 072 for (int i=N; i<q.length; i++) { 073 if (q[(first + i) % q.length] != null) throw new Error (); 074 } 075 if (expected != null) { 076 if (!expected.equals(this.toString ())) throw new Error ("Expected \"" + expected + "\", got \"" + this + "\""); 077 } 078 StdOut.println (this); 079 } 080 private void check (String iExpected, String iActual, String expected) { 081 if (!iExpected.equals (iActual)) throw new Error ("Expected \"" + iExpected + "\", got \"" + iActual + "\""); 082 check (expected); 083 } 084 public static void mainX (String args[]) { 085 String k; 086 var d1 = new XResizingArrayQueueofStrings (); 087 d1.enqueue ("11"); d1.check ("[11]"); 088 d1.enqueue ("12"); d1.check ("[11 12]"); 089 k = d1.dequeue(); d1.check ("11", k, "[12]"); 090 k = d1.dequeue(); d1.check ("12", k, "[]"); 091 092 d1 = new XResizingArrayQueueofStrings (); 093 for (int i = 10; i < 20; i++) 094 d1.enqueue (Integer.toString(i)); 095 d1.check ("[10 11 12 13 14 15 16 17 18 19]"); 096 097 for (int i = 10; i < 20; i++) { 098 d1.dequeue (); d1.check (null); 099 } 100 try { d1.dequeue (); throw new Error ("Expected exception"); } catch (Error e) {} 101 } 102 103 // A test client 104 public static void main (String[] args) { 105 StdIn.fromString ("to be or not to - be - - that - - - is"); 106 107 var q = new XResizingArrayQueueofStrings(); 108 while (!StdIn.isEmpty()) { 109 String item = StdIn.readString(); 110 if (!item.equals("-")) q.enqueue(item); 111 else StdOut.print(q.dequeue() + " "); 112 } 113 StdOut.println("(" + q.size() + " left on queue)"); 114 } 115}