001package algs13; 002import stdlib.*; 003 004public class XResizingArrayStackOfStrings { 005 private String[] a; // array of items 006 private int N = 0; // number of elements on stack 007 // Invariant (after the constructor): 008 // a[0]..a[N-1] are non null 009 // a[N]..a[a.length-1] are null 010 011 // create an empty stack 012 public XResizingArrayStackOfStrings() { 013 a = new String[N]; 014 } 015 016 public boolean isEmpty() { return N == 0; } 017 public int size() { return N; } 018 019 // resize the underlying array holding the elements 020 private void resize(int capacity) { 021 String[] temp = new String[capacity]; 022 for (int i = 0; i < N; i++) 023 temp[i] = a[i]; 024 a = temp; 025 } 026 027 // push a new item onto the stack 028 public void push(String item) { 029 if (N == a.length) resize(2*a.length); 030 a[N] = item; 031 N++; 032 } 033 034 // delete and return the item most recently added 035 public String pop() { 036 if (isEmpty()) { throw new Error("Stack underflow error"); } 037 N--; 038 String item = a[N]; 039 a[N] = null; // to avoid loitering 040 if (N > 0 && N == a.length/4) resize(a.length/2); // shrink size of array if necessary 041 return item; 042 } 043 044 045 046 /* ********************************************************************* 047 * Test routine. 048 **********************************************************************/ 049 public static void main(String[] args) { 050 Trace.drawStepsOfMethod ("resize"); 051 Trace.run (); 052 StdIn.fromString ("to be or not to - be - - that - - - is"); 053 054 XResizingArrayStackOfStrings s = new XResizingArrayStackOfStrings(); 055 while (!StdIn.isEmpty()) { 056 String item = StdIn.readString(); 057 if (!item.equals("-")) s.push(item); 058 else if (!s.isEmpty()) StdOut.print(s.pop() + " "); 059 } 060 StdOut.println("(" + s.size() + " left on stack)"); 061 } 062}