001package algs13;
002import stdlib.*;
003import java.util.Iterator;
004import java.util.NoSuchElementException;
005/* ***********************************************************************
006 *  Compilation:  javac ResizingSlowStack.java
007 *  Execution:    java ResizingSlowStack < 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 ResizingSlowStack < tobe.txt
016 *  to be not that or be (2 left on stack)
017 *
018 *************************************************************************/
019
020public class XResizingArraySlowStack<T> implements Iterable<T> {
021        private T[] a;         // array of items
022        private int N = 0;    // number of elements on stack
023
024        // create an empty stack
025        @SuppressWarnings("unchecked")
026        public XResizingArraySlowStack() {
027                a = (T[]) new Object[N];
028        }
029
030        public boolean isEmpty() { return N == 0; }
031        public int size()        { return N;      }
032
033        // resize the underlying array holding the elements
034        private void resize(int capacity) {
035                @SuppressWarnings("unchecked")
036                T[] temp = (T[]) new Object[capacity];
037                for (int i = 0; i < N; i++)
038                        temp[i] = a[i];
039                a = temp;
040        }
041
042        // push a new item onto the stack
043        public void push(T item) {
044                if (N == a.length) resize(N+1);
045                a[N] = item;
046                N++;
047        }
048
049        // delete and return the item most recently added
050        public T pop() {
051                if (isEmpty()) { throw new Error("Stack underflow error"); }
052                N--;
053                T item = a[N];
054                a[N] = null;  // to avoid loitering
055                resize(N); // shrink size of array if necessary
056                return item;
057        }
058
059
060        public Iterator<T> iterator()  { return new LIFOIterator();  }
061
062        // an iterator, doesn't implement remove() since it's optional
063        private class LIFOIterator implements Iterator<T> {
064                private int i = N;
065                public boolean hasNext()  { return i > 0;                               }
066                public void remove()      { throw new UnsupportedOperationException();  }
067
068                public T next() {
069                        if (!hasNext()) throw new NoSuchElementException();
070                        return a[--i];
071                }
072        }
073
074
075
076        /* *********************************************************************
077         * Test routine.
078         **********************************************************************/
079        public static void main(String[] args) {
080                Trace.drawStepsOfMethod ("resize");
081                Trace.run ();
082                StdIn.fromString ("to be or not to - be - - that - - - is");
083
084                XResizingArraySlowStack<String> s = new XResizingArraySlowStack<>();
085                while (!StdIn.isEmpty()) {
086                        String item = StdIn.readString();
087                        if (!item.equals("-")) s.push(item);
088                        else if (!s.isEmpty()) StdOut.print(s.pop() + " ");
089                }
090                StdOut.println("(" + s.size() + " left on stack)");
091        }
092}