001package algs13; 002import stdlib.*; 003import java.util.Iterator; 004import java.util.NoSuchElementException; 005/* *********************************************************************** 006 * Compilation: javac ResizingArrayStack.java 007 * Execution: java ResizingArrayStack < input.txt 008 * Data files: http://algs4.cs.princeton.edu/13stacks/tobe.txt 009 * 010 * Stack implementation with a resizing array. 011 * 012 * % more tobe.txt 013 * to be or not to - be - - that - - - is 014 * 015 * % java ResizingArrayStack < tobe.txt 016 * to be not that or be (2 left on stack) 017 * 018 *************************************************************************/ 019public class ResizingArrayStack<T> implements Iterable<T> { 020 private T[] a; // array of items 021 private int N; // number of elements on stack 022 023 // create an empty stack 024 @SuppressWarnings("unchecked") 025 public ResizingArrayStack() { 026 this.a = (T[]) new Object[2]; 027 this.N = 0; 028 } 029 030 public boolean isEmpty() { return N == 0; } 031 public int size() { return N; } 032 033 034 // resize the underlying array holding the elements 035 @SuppressWarnings("unchecked") 036 private void resize(int capacity) { 037 if (capacity <= N) throw new IllegalArgumentException (); 038 T[] temp = (T[]) new Object[capacity]; 039 for (int i = 0; i < N; i++) 040 temp[i] = a[i]; 041 a = temp; 042 } 043 044 // push a new item onto the stack 045 public void push(T item) { 046 if (N == a.length) resize(2*N); // increase array size if necessary 047 //if (N == a.length) resize((int)Math.ceil (N*1.5)); 048 a[N] = item; 049 N++; 050 } 051 052 // delete and return the item most recently added 053 public T pop() { 054 if (isEmpty()) { throw new Error("Stack underflow error"); } 055 N--; 056 T item = a[N]; 057 a[N] = null; // to avoid loitering 058 if (N > 0 && N == a.length/4) resize(a.length/2); // shrink size of array if necessary 059 return item; 060 } 061 062 /** 063 * Return string representation. 064 */ 065 public String toString() { 066 StringBuilder s = new StringBuilder(); 067 for (T item : this) 068 s.append(item + " "); 069 return s.toString(); 070 } 071 072 public Iterator<T> iterator() { return new ReverseArrayIterator(); } 073 074 // an iterator, doesn't implement remove() since it's optional 075 private class ReverseArrayIterator implements Iterator<T> { 076 private int i = N; 077 public boolean hasNext() { return i > 0; } 078 public void remove() { throw new UnsupportedOperationException(); } 079 080 public T next() { 081 if (!hasNext()) throw new NoSuchElementException(); 082 return a[--i]; 083 } 084 } 085 086 /* ********************************************************************* 087 * Test routine. 088 **********************************************************************/ 089// public static void bookMain(String[] args) { 090// StdIn.fromString ("to be or not to - be - - that - - - is"); 091// 092// ResizingArrayStack<String> s = new ResizingArrayStack<>(); 093// while (!StdIn.isEmpty()) { 094// String item = StdIn.readString(); 095// if (!item.equals("-")) s.push(item); 096// else if (!s.isEmpty()) StdOut.print(s.pop() + " "); 097// } 098// StdOut.println("(" + s.size() + " left on stack)"); 099// } 100// 101 /* ********************************************************************* 102 * Test routine. 103 **********************************************************************/ 104 public static void main(String[] args) { 105 double prevTime = 1; 106 for (int i = 0, size = 20; i<19; i += 1, size *= 2) { 107 Stopwatch s = new Stopwatch (); 108 109 for (int k = 0; k < 1; k++) { 110 ResizingArrayStack<Double> stack = new ResizingArrayStack<> (); 111 for (int j = 0; j < size; j++) { 112 stack.push (1.2); 113 } 114 } 115 116 double thisTime = s.elapsedTime (); 117 StdOut.format ("size=%d thisTime=%f ratio=%f\n", size, thisTime, thisTime/prevTime); 118 prevTime = thisTime; 119 } 120 } 121 public static void main2 (String[] args) { 122 //Trace.showObjectIdsRedundantly (true); 123 Trace.showBuiltInObjects (true); 124 //Trace.showBuiltInObjectsVerbose (true); 125 Trace.drawStepsOfMethod ("main"); 126 Trace.drawStepsOfMethod ("resize"); 127 Trace.run (); 128 129 ResizingArrayStack<Integer> s1 = new ResizingArrayStack<> (); 130 ResizingArrayStack<String> s2 = new ResizingArrayStack<> (); 131 s1.push (11); 132 s1.push (21); 133 s1.push (31); 134 135 //s2.push (41); 136 s2.push ("duck"); 137 s2.push ("goose"); 138 } 139}