Doubling Stack of
Strings using Java
import java.util.Iterator; import java.util.NoSuchElementException; public class DoublingStackOfStrings implements Iterable<String> { private String[] a; private int N; public DoublingStackOfStrings() { a = new String[2]; N = 0; } // is the stack empty? public boolean isEmpty() { return (N == 0); } // resize the underlying array holding the elements private void resize(int capacity) { String[] temp = new String[capacity]; for (int i = 0; i < N; i++) { temp[i] = a[i]; } a = temp; } // push a new item onto the stack public void push(String item) { if (N == a.length) resize(2*a.length); a[N++] = item; } // delete and return the item most recently added public String pop() { if (isEmpty()) { throw new RuntimeException("Stack underflow error"); } String item = a[--N]; a[N] = null; // to avoid loitering if (N > 0 && N == a.length/4) resize(a.length/2); return item; } public Iterator<String> iterator() { return new ReverseArrayIterator(); } // an iterator, doesn't implement remove() since it's optional private class ReverseArrayIterator implements Iterator<String> { private int i = N; public boolean hasNext() { return i > 0; } public void remove() { throw new UnsupportedOperationException(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); return a[--i]; } } // test client public static void main(String[] args) { DoublingStackOfStrings s = new DoublingStackOfStrings(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) s.push(item); else if (s.isEmpty()) StdOut.println("BAD INPUT"); else StdOut.print(s.pop()); } } }