/**
 *  file :  Stack.java
 *  desc :  Implements the class Stack
 */


public class Stack
{
  /**
   *  post :  constructs an empty stack
   */
  public Stack()
  {
    max = 10;
    elems = new Object [max];
    top = 0;
  }

  /**
   *  post :  returns true <==> stack is empty
   */
  public boolean isEmpty()
  {
    return (top == 0);
  }

  /**
   *   pre :  isEmpty() == false
   *  post :  removes and returns element at the top
   */
  public Object pop()
  {
    return elems[--top];
  }

  /**
   *  post :  put 'elem' at the top
   */
  public void push( Object elem )
  {
    checkSize();
    elems[top++] = elem;
  }

  public String toString ()
  {
      String result = "[ ";
      for (int i = 0; i < top; i++) {
        result += elems[i] + " ";
      }
      result += "]";
      return result;
  }

  // private fields
  private int max;     	     // Current capacity of stack
  private int top;           // Current number of stack elements.
  private Object[] elems;    // Data in stack (elems[t-1] is top).

  /**
   *  post :  if the stack was full, the capacity is expanded
   *          (doubled)
   */
  private void checkSize()
  {
    if (top == max)
    {
      // double the capacity
      int newmax = max << 2;
      Object[] newelems = new Object [newmax];

      // copy the data
      int i;
      for( i = 0; i < max; i++ )
	newelems[i] = elems[i];

      // point to the new data
      max = newmax;
      elems = newelems;
    }
  }
}