//
// COMP102
// Example 10: Stacks
//            
//
// Paul E. Dunne 11/11/99
//
public class Stack
  {
  //******************************************************
  // Stack Fields                                        *
  //******************************************************
  private Object Top;         
  private Stack Rest;         
  private int CellCount;         // The number of list cells in this instance.
  //******************************************************
  // Stack Constructor                                   *
  //******************************************************
  public Stack()
    {
    Top  = null;
    Rest = null;      
    CellCount=0; // Initiates the empty Stack
    }
  private Stack( Object Item, Stack rest_of )
     {
     Top = Item;
     Rest = rest_of;
     }
     
  //******************************************************
  // Stack Instance Methods                              *
  //******************************************************
  //
  //  Test if this instance is the Empty list.
  //
  public boolean IsEmptyStack()
    {
    return (CellCount==0);       // `Safer' than testing for null reference.
    };
  //
  //************************************************************
  //  Add a new Cell as the first cell in this Stack           *
  //************************************************************
  //
  public void Push ( Object Datum )
    {
     if (IsEmptyStack())
       {
       Top =Datum;
       Rest = null;
       }
     else
       {
       Rest = new Stack (Top,Rest);
       Top = Datum;
       };
     this.CellCount++;
    }
  //
  //************************************************************************
  //  Remove the Cell at the start of this Stack                           *
  //  i.e. if the current Stack is [Top]::[Rest], the `new' one is [Rest]. *
  //************************************************************************
  //
  public void Pop()
    {
    if (CellCount<=1)                    // There is an argument for raising
      {                                  // an exception if CellCount=0
                                         // however, we adopt the convention
                                         // that RemoveHead() applied to
                                         // the empty list leaves the empty list.
      Top = null; 
      Rest=null;

      CellCount=0;
      }
    else
      {
      Top = Rest.Top;
      CellCount--;                      // and this list has one fewer cell.
      if (CellCount==1)
        Rest=null;                      // If there's only a single cell then its Link field
                                        // must point to the empty list (i.e. null reference)
      else
        Rest = Rest.Rest;               // Otherwise we can update Tail without any problem.
      };
    }
  //
  //**********************************************************************
  //  Obtain the Object in the Datum field of the ListCell at            *
  //  the start of this Linked List.                                     *
  //  This method will not change the current instantiation of this List.*
  //**********************************************************************
  //
  public Object Peek()
    {
    if (!(CellCount==0))                // If there's anything to return
      return this.Top;                // then return it.
    else
      return null;                      // otherwise return a null reference.
    }
  public String toString()
    {
    String res = new String();
    Stack temporary = new Stack();
    temporary.Top = this.Top; 
    temporary.Rest = this.Rest; 
    temporary.CellCount=this.CellCount;
    while (!temporary.IsEmptyStack())
      {
      res = res+(temporary.Peek()).toString()+"\n";
      temporary.Pop();
      };
    return res;
    }     
  }