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}