////////////////////////////////////////////////////////////////////////
// CSE 428 SPRING 2001. 
// Code for the Exercise 5 of Midterm 2
// FILE Test.java
////////////////////////////////////////////////////////////////////////

class MyThread extends Thread{
      private Stack myStack;
      private String myName;
      
      public MyThread(Stack s, String n){ myStack = s; myName = n; }
      
      public void run(){
        try {
         sleep((long)(java.lang.Math.random()*100)); // sleep for some time
         myStack.push(myName); System.out.print("in " + myName + ", ");
         sleep((long)(java.lang.Math.random()*100)); // sleep for some time
         System.out.print("out " + myStack.pop() + ", ");
        } catch (InterruptedException e) {return;}
      }
}

class Test {
      public static void main(String[] args){   
         Stack s = new Stack();
         MyThread T1 = new MyThread(s,"A");
         MyThread T2 = new MyThread(s,"B");
         T1.start(); T2.start();
      }
}

////////////////////////////////////////////////////////////////////////
// Definition of class Stack
////////////////////////////////////////////////////////////////////////

   class Stack {
          
       private class Element {
          String info; 
          Element next;
          Element(String k, Element n) { info = k; next = n; }
       }
             
       private Element head;
    
       public Stack() { head = null; }
       
       public synchronized void pushs(String k) { 
          head = new Element(k,head); 
          notify(); // We can use notify() instead of notifyAll() 
                    // because a thread can suspend only on pop()
       }
       public void push(String k) { 
          pushs(k);
          try { // this is only to make interleaving sequences more likely
            Thread.sleep((long)(java.lang.Math.random()*1000));
          }
          catch (InterruptedException e) {
             return; 
          }
       }
       public synchronized String pops(){
          try { 
              while (head == null) wait(); 
          } catch (InterruptedException e) {
              return "pop on empty stack" ; 
          }
            String s = head.info; 
            head = head.next; 
            return s;
       }
       public String pop() { 
          String s = pops();
          try { // this is only to make interleaving sequences more likely
             Thread.sleep((long)(java.lang.Math.random()*100));
          } catch (InterruptedException e) { return "" ;} 
          return s;
       }                                 
    }