//  Stack.java  (c) 2005 Kari Laitinen

//  http://www.naturalprogramming.com

//  2004-10-03  File created.
//  2005-02-24  Last modification.

//  Compile: javac Stack.java  (in MS-DOS window)
//  Run:     java  StackTester (in MS-DOS window)

//  In the java.util package there is a standard class
//  named Stack. To avoid a name conflict, the whole java.util
//  package is not imported. This program can, though,
//  be compiled also when the whole package is imported.

import java.util.Scanner ;

class Stack
{
   static final int STACK_INCREMENT_SIZE  =  4 ;

   int    number_of_items_on_stack ;
   int    current_stack_size ;
   int[]  stack_memory_space ;

   public Stack()
   {
      this( STACK_INCREMENT_SIZE ) ;
   }

   public Stack( int  requested_stack_size )
   {
      stack_memory_space  =  new  int[ requested_stack_size ] ;

      current_stack_size  =  requested_stack_size ;

      number_of_items_on_stack    =  0 ;
   }

   public void push( int item_to_the_stack )
   {
      if ( number_of_items_on_stack  >=  current_stack_size  )
      {
         //  We must increase the memory space of this stack object.

         int[]  new_stack_memory_space ;

         new_stack_memory_space  =  new  int[ current_stack_size +
                                              STACK_INCREMENT_SIZE ] ;

         current_stack_size  =  current_stack_size
                                       + STACK_INCREMENT_SIZE ;

         //  We must copy the old stack contents to the new stack
         //  memory space.

         for ( int item_index  =  0  ;
                   item_index  <  number_of_items_on_stack ;
                   item_index  ++ )
         {
            new_stack_memory_space[ item_index ]  =
                                   stack_memory_space[ item_index ] ;
         }

         //  Let's make stack_memory_space reference the reserved
         //  new memory space. The old memory space shall be freed
         //  by the garbage collector as nobody is referencing that
         //  memory area any more.

         stack_memory_space  =  new_stack_memory_space ;

         System.out.print( " STACK HAS GROWN.\n" ) ;
      }

      //  Here we push the new value to the stack.

      stack_memory_space[ number_of_items_on_stack ]  =
                                     item_to_the_stack ;
      number_of_items_on_stack  ++  ;
   }


   public int pop()
   {
      int  item_from_the_stack ;

      if  ( number_of_items_on_stack  ==  0 )
      {
         System.out.print( "\n ERROR: Attempt to pop on empty stack !\n" ) ;
         item_from_the_stack  =  -1 ;  
      }
      else
      {
         number_of_items_on_stack  -- ;
         item_from_the_stack  =
                 stack_memory_space[ number_of_items_on_stack ] ;
      }

      return  item_from_the_stack ;
   }


   public boolean stack_is_not_empty()
   {
      return  ( number_of_items_on_stack  >  0  ) ;
   }
}


class StackTester
{
   public static void main( String[] not_in_use )
   {
      Scanner keyboard = new Scanner( System.in ) ;

      int  value_to_the_stack ;
      int  value_popped_from_the_stack ;

      Stack  test_stack  =  new  Stack() ;

      System.out.print( "\n Let's test a stack. Please, type in integers."
            +  "\n I will push those numbers onto a stack, and later"
            +  "\n take them away from the stack. I will stop reading"
            +  "\n numbers when you type in a zero."
            +  "\n Please, press <Enter> after each number. \n\n" ) ;

      do
      {
         System.out.print( " Give a number:  " ) ;
         value_to_the_stack  =  keyboard.nextInt() ;

         test_stack.push( value_to_the_stack ) ;
      }  
        while  ( value_to_the_stack  !=  0  ) ;

      System.out.print( "\n The numbers popped from the stack are:\n\n ") ;

      while ( test_stack.stack_is_not_empty() )
      {
         value_popped_from_the_stack  =  test_stack.pop() ;

         System.out.print( value_popped_from_the_stack  +  "   "  ) ;
      }

      System.out.print( "\n" ) ;
   }
}


/******  Note 2004-10-03:

   STACK_INCREMENT_SIZE could not be used in the constructor

      public Stack()
      {
         this( STACK_INCREMENT_SIZE ) ;
      }

   if it was declared only "final int". It had to be declared
   "static final int".

*******/