//Class that implements the stack interface

public class StackImpl implements Stack
{
    static final int DEFAULT_CAPACITY=10;

    private Object [] theArray;
    private int topOfStack;

    public StackImpl()
        {
            theArray = new Object[DEFAULT_CAPACITY];
            topOfStack=-1;
        }

    public void push(Object x)
        {
            if (topOfStack+1==theArray.length)
                doubleArray();
            topOfStack++;
            theArray[topOfStack]=x;
        }
    
    public void pop() throws Exception
        {
            if (isEmpty())
                throw new Exception("Stack pop");
            topOfStack--;
        }
    
    public Object top() throws Exception
        {
            if (isEmpty())
                throw new Exception("Stack top");
            return theArray[topOfStack];
        }
    
    public Object topAndPop() throws Exception
        {
            if (isEmpty())
                throw new Exception("Stack topAndPop");
            return theArray[topOfStack--];
        }
    
    public boolean isEmpty()
        {
            return topOfStack==-1;
        }
    
    public void makeEmpty()
        {
            topOfStack=-1;
        }
    
    private void doubleArray()
        {
            int oldArraySize = theArray.length;
            Object [] biggerArray = new Object[oldArraySize*2];

            for (int i=0; i<oldArraySize; i++)
                biggerArray[i]=theArray[i];
            theArray=biggerArray;
        }
    

}