package algs13;
import stdlib.*;

public class XResizingArrayStackOfStrings {
	private String[] a;   // array of items
	private int N = 0;    // number of elements on stack
	// Invariant (after the constructor):
	//   a[0]..a[N-1] are non null
	//   a[N]..a[a.length-1] are null
	
	// create an empty stack
	public XResizingArrayStackOfStrings() {
		a = new String[N];
	}

	public boolean isEmpty() { return N == 0; }
	public int size()        { return N;      }

	// 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;
		N++;
	}

	// delete and return the item most recently added
	public String pop() {
		if (isEmpty()) { throw new Error("Stack underflow error"); }
		N--;
		String item = a[N];
		a[N] = null;  // to avoid loitering
		if (N > 0 && N == a.length/4) resize(a.length/2); // shrink size of array if necessary
		return item;
	}



	/* *********************************************************************
	 * Test routine.
	 **********************************************************************/
	public static void main(String[] args) {
		Trace.drawStepsOfMethod ("resize");
		Trace.run ();
		StdIn.fromString ("to be or not to - be - - that - - - is");

		XResizingArrayStackOfStrings s = new XResizingArrayStackOfStrings();
		while (!StdIn.isEmpty()) {
			String item = StdIn.readString();
			if (!item.equals("-")) s.push(item);
			else if (!s.isEmpty()) StdOut.print(s.pop() + " ");
		}
		StdOut.println("(" + s.size() + " left on stack)");
	}
}