import java.util.Iterator;
public class LStack<T> implements IStack<T>
{
    private Link<T> top;  
    public LStack()
    {
        top = null;
    }
    public void push(T newItem)
    {
        top = new Link<T>(newItem, top); 
    }
    public T peek()
    {
        if(isEmpty())
        {
            throw new EmptyStackException();
        }
        return top.getDatum();
    }
    //return the evictee
    //remove its link from the top.
    public T pop()
    {
        if(isEmpty())
        {
            throw new EmptyStackException();
        }
        T out = top.getDatum();
        top = top.getNext();
        return out;
    }
    public boolean isEmpty()
    {
        return top == null;
    }
    public int size()
    {
        int count = 0;
        for(Link<T> nav = top; nav != null; nav = nav.getNext())
        {
            count++;
        }
        return count;

    }
    public void clear()
    {
        top = null;
    }
    @Override
    public String toString()
    {
        StringBuffer sb = new StringBuffer("[");
        for(Link<T> nav = top; nav != null; nav = nav.getNext())
        {
            sb.append(String.format("%s, ", nav.getDatum()));
        }
        sb.delete(sb.length() - 2, sb.length());
        sb.append("]");
        return sb.toString();
    }
    public Iterator<T> iterator()
    {
        return new Navigator();
    }
    /*****************Alien*********************/
    class Navigator implements Iterator<T>
    {
        Link<T> nav;
        public Navigator()
        {
            nav = top;
        }
        public void remove()
        {
            throw new UnsupportedOperationException();
        }
        public boolean hasNext()
        {
            return nav != null;
        }
        public T next()
        {
            T out = nav.getDatum();
            nav = nav.getNext();
            return out;
        }
    }

    public static void main(String[] args)
    {
        IStack<String> s = new LStack<>();
        System.out.println(s.size() == 0);
        s.push("C");
        s.push("B");
        s.push("A");
        System.out.println(s);
        System.out.println(s.size() == 3);
        for(String q:s)
        {
            System.out.println(q);
        }
        
        s.pop();
        System.out.println(s);
        System.out.println(s.size() == 2);
        s.clear();
        for(int k = 0; k <25000; k++)
        {
            s.push("" + k);
        }
        System.out.println(s.size() == 25000);
        /*for(String q:s)
        {
            System.out.println(q);
        }*/
        for(int k = 0; k <25000; k++)
        {
            s.pop();
        }
        System.out.println(s.isEmpty());


    }
}
class Link<T>
{
    private final T datum;
    private Link<T> next;
    public Link(T datum, Link<T> next)
    {
        this.datum = datum;
        this.next = next;
    }
    public T getDatum()
    {
        return datum;
    }
    public Link<T> getNext()
    {
        return next;
    }
}