// StackArray class


/**
 * Array-based implementation of the stack.
 *
 * @author Mark Allen Weiss
 * @author Albert J. Wong
 *
 * Modified by Albert J. Wong October 2003
 *   - Fixed style
 *   - Threw exceptions on underflow
 *   - Weiss has one memory leak in this. The leak is left in.
 *     Finding and fixing it is left as an exercise to the students.
 *   - Created generic interface for stack and queue
 */
public class StackArray implements Stack {
	/**
	 * Construct the stack.
	 */
	public StackArray() {
		this( DEFAULT_CAPACITY );
	}


	/**
	 * Construct the stack.
	 *
	 * @param capacity the capacity.
	 */
	public StackArray( int capacity ) {
		data = new Object[ capacity ];
		topOfStack = -1;
	}


	/**
	 * Test if the stack is logically empty.
	 *
	 * @return true if empty, false otherwise.
	 */
	public boolean isEmpty() {
		return topOfStack == -1;
	}


	/**
	 * Test if the stack is logically full.
	 *
	 * @return true if full, false otherwise.
	 */
	public boolean isFull() {
		return topOfStack == data.length - 1;
	}


	/**
	 * Make the stack logically empty.
	 */
	public void makeEmpty() {
		topOfStack = -1;
	}


	/**
	 * Get the most recently inserted item in the stack.
	 * Does not alter the stack.
	 *
	 * @return the most recently inserted item in the stack.
	 * @exception UnderflowException	Thrown if stack is empty.
	 */
	public Object top() {
		if( isEmpty() ) {
			throw new UnderflowException();
		}

		return data[ topOfStack ];
	}


	/**
	 * Remove the most recently inserted item from the stack.
	 *
	 * @exception UnderflowException	Thrown if stack is empty.
	 */
	public void pop() {
		if( isEmpty() ) {
			throw new UnderflowException();
		}

		data[ topOfStack-- ] = null;
	} 


	/**
	 * Insert a new item into the stack, if not already full.
	 *
	 * @param x the item to insert.
	 * @exception OverflowException		Thrown if queue is full.
	 */
	public void push( Object x ) {
		if( isFull() ) {
			throw new OverflowException();
		}
		
	    	data[ ++topOfStack ] = x;
	}


	/// The array that holds the items in the stack 
	private Object []	data;

	/// The index of the last element inserted onto the stack
	private int		topOfStack;

	/// Default capacity
	static final int	DEFAULT_CAPACITY = 10;



	/**
	 * Main function for a simple unit test of the stack.
	 */
	public static void main( String [ ] args )
	{
		StackArray s = new StackArray( 12 );

		try {
			for( int i = 0; i < 10; i++ ) {
				s.push( new Integer( i ) );
			}
		} catch( OverflowException oe ) { 
			System.out.println( "Unexpected overflow" ); 
		}

		while( !s.isEmpty() ) {
			System.out.println( s.top() );
			s.pop();
		}
	}        
}