//-------------------------------------------------------------
// StackClient.java: a stack example to illustrate some Java
//
// Andy Collins - acollins@cs.washington.edu
//-------------------------------------------------------------
import java.io.*;

//-------------------------------------------------------------
// class Stack: a standard implementation of a stack, uses
//              inheritance polymorphism and a linked-list
//-------------------------------------------------------------
class Stack
{
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Constructor: set up the linked list
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public Stack ()
   {
      head = null;
   }

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Push: push an element at the front of the list
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public void Push (Object elem)
   {
      Link newLink = new Link ();
      newLink.data = elem;        // pointer assignment == sharing

      newLink.next = head;
      head = newLink;
   }

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Pop: remove and return the element from the front of the 
   //      list.  If the list is empty then throw an exception
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public Object Pop () throws EmptyStack
   {
      if (this.Size () == 0)       // 'this.' is optional
         throw new EmptyStack ();

      Object retval = head.data;
      head = head.next;

      return retval;
   }

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // IsEmpty: return true iff the stack has no elements in it
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public boolean IsEmpty ()
   {
      return (Size () == 0);
   }

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Size: return the number of items in the stack.  
   //       Recursive implementation
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public int Size ()
   {
      return SizeHelper (head);
   }

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // SizeHelper: the actual recursive implementation of Size
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   private int SizeHelper (Link head)
   {
      if (head == null)
         return 0;
      else
         return 1 + SizeHelper (head.next);
   }

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // private data:
   //   head    reference to the first Link in the stack,
   //           or null for an empty stack.
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   private Link head;
}

//-------------------------------------------------------------
// class EmptyStack: the execption thrown by Push.  No
//                   special data
//-------------------------------------------------------------
class EmptyStack extends Exception
{
}

//-------------------------------------------------------------
// class Link: a single link out of the linked-list.  Used
//             internally by Stack as a struct
//-------------------------------------------------------------
class Link
{
   public Object data;
   public Link next;
}

//-------------------------------------------------------------
// class StackClient: a client program using the stack
//-------------------------------------------------------------
public class StackClient
{
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // main: entry point into program
   //
   // USAGE: java StackClient [<num>]
   //    Push the numbers 0 ... <num> onto the stack, then
   //    pop and print them.  <num> defaults to 10 if not 
   //    specified
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public static void main (String[] args)
   {
      // Argument parsing
      int num = 10;
      if (args.length > 0)
         {
         try
            {
            num = Integer.parseInt (args[0]);
            }
         catch (NumberFormatException e)
            {
            // num could not have been updated, no need to do
            // anything here
            }
         }

      // Create a stack
      Stack stack = new Stack ();

      // Push the numbers
      for (int i = 0; i <= num; ++i)
         stack.Push (new Integer (i));     // need to wrap int in Integer

      // Pop and print the numbers
      try
         {
         System.out.println ("Stack contents:");
         while (!stack.IsEmpty ())
            System.out.println ("   " + stack.Pop ());
         }
      catch (EmptyStack e)
         {
         System.out.println ("Exception: bailing out");
         }
   }
}