/* Beginning of Stack data structure.
        API:
        E push(E elm)   // add elememnt to stack
        E pop()         // remove element from stack

    Element in a stack are extracted in LIFO order - last in - first out.

    We cannot create an array of a parameterized type.  So we use an
    array of Objects to hold the elements.

*/

import java.util.EmptyStackException;

class Stack<E> {

	// you cannot create an array of a generic type
	private Object[] stack = null;	
	private int count = 0;

	Stack(int initialCapacity) {
		stack = new Object[initialCapacity];
	 }

	E push(E elm) {
		if (count == stack.length) {
			Object[] temp = new Object[2 * count];

			for(int i = 0; i < count; i++) {
				temp[i] = stack[i];
			}	
			stack = temp;

			System.out.println("expanded the stack");
		}

		stack[count] = elm;
		count++;

		return elm;
	}

	@SuppressWarnings("unchecked")
	E pop() {
		if (count == 0) {
			throw new EmptyStackException();
		}

		Object elm = stack[count - 1];
		stack[count - 1] = null;
		count--;
		return (E) elm;
	}

	boolean empty() {
		return (count == 0);
	}

	E peek() {
		if (count == 0) {
			throw new EmptyStackException();
		}

		return (E) stack[count - 1];
	}
	
	@Override
	public String toString() {
		String s = "";
		for (int i = 0; i < count; i++) {
			s += stack[i].toString() + " ";
		}
		return s;
	}

}