// Show code for an Iterable Stack class:

import java.util.*;
public abstract class Stack implements Iterable<String> {
// Note: we can't use int for the stack contents!!

    abstract boolean isEmpty1 ();
    abstract String top1();
    abstract Stack pop1();
//*****************  add this abstract declaration
    public abstract Iterator<String> iterator(); 
    // ensures this method is defined for all concrete subclasses
	    
    // The basic creators are empty and push.

    // Returns an empty stack.

    public static Stack empty () {
        return new EmptyStack();
    }

    // Returns a stack representing n pushed onto s.

    public static Stack push (Stack s, String n) {
        return new PushStack (s, n);
    }

    // Other public methods.

    // Returns true iff the given stack is empty.

    public static boolean isEmpty (Stack s) {
        return s.isEmpty1();
    }

    // Returns the top element of the given stack, which must be nonempty.

    public static String top (Stack s) {
        return s.top1();
    }

    // Returns the pop of the given stack, which must be nonempty.

    public static Stack pop (Stack s) {
        return s.pop1();
    }

//**************** Create an inner class which is an abstract stack iterator 
//                 class nested within the abstract stack class
    protected abstract class StackIter implements Iterator<String> {
	   abstract public boolean hasNext ();
	   abstract public String next ();
	   abstract public void remove();
	   // Stack is an immutable ADT so remove is not permitted
	   protected static final String msgRemove = 
	    "Remove operation unsupported";
	   protected static final String msgNext = 
	    "Next operation on empty stack is illegal";
	    }
	
} // end of Stack abstract class

// The class of objects created by empty().
   class EmptyStack extends Stack {
    
    // Initializes this empty stack.

    EmptyStack () { }

    boolean isEmpty1 () { return true; }

    String top1 () {
        throw new IllegalArgumentException (msgTop);
    }

    Stack pop1 () {
        throw new IllegalArgumentException (msgPop);
    }

    private static final String msgTop
        = "Can't take the top of an empty stack.";

    private static final String msgPop
        = "Can't pop an empty stack.";

    //***********************
    public Iterator<String> iterator() {return new EmptyIter();}

    // Here is the first concrete Iterator
    private class EmptyIter extends StackIter {
	EmptyIter() {}
    	public boolean hasNext () {return false;}
    	public String next () {
	        throw new NoSuchElementException (msgNext);
    	}
    	public void remove () {
    		throw new UnsupportedOperationException (msgRemove);
    	}
    } // end of EmptyIter    
  } // end of Empty
	

//  The class of objects created by push(s,t).
    class PushStack extends Stack {
       private String top;  // the top of this Stack (t)
       private Stack other;   // the pop of this Stack (s)

    /////*****NOTE THAT THE INSTANCE VARIABLES ABOVE MUST NOT BE CHANGED!!
	    

    private Stack s;                 // the pop of this Stack
    private String n;                   // the top of this Stack

    // Initializes this stack with top n and pop s.

    PushStack (Stack s, String n) {
        this.s = s;
        this.n = n;
    }

    boolean isEmpty1 () { return false; }

    String top1 () {
        return n;
    }

    Stack pop1 () {
        return s;
    }

    public Iterator<String> iterator() {return new PushIter ();}
	    
    private class PushIter extends StackIter {

    private Stack moreStack; 
    private boolean starting = true;

       // the first call to next() is a special case because 
       // even if nextStack is empty there is a "next" element.

       PushIter () {
	   moreStack = other;
	   }

       public boolean hasNext () {
          return  starting || !Stack.isEmpty (moreStack); }

       public String next () {
	  String s;
	  if (starting) {
	    s = top;  // get the next element
	    starting = false;
	    }
	  else if (!Stack.isEmpty(moreStack)) {
	    s = Stack.top(moreStack);
	    moreStack = Stack.pop(moreStack);
	    }
	  else throw new NoSuchElementException(msgNext);
	  return s;
	  }

     public void remove () {
	throw new UnsupportedOperationException (msgRemove);
   	}	    	
    } //end of PushIter
  } //end of Push