package com.qiusongde;

import java.util.Iterator;

import java.util.NoSuchElementException;

import edu.princeton.cs.algs4.StdIn;

import edu.princeton.cs.algs4.StdOut;

public class Stack<Item> implements Iterable<Item> {

    private Node first;

    private int n;

    private class Node {

        Item item;

        Node next;

    }

    public Stack() {

        first = null;

        n = 0;

    }

    public void push(Item item) {

        Node oldfirst = first;

        first = new Node();

        first.item = item;

        first.next = oldfirst;

        n++;

    }

    public Item pop() {

        if(isEmpty())

            throw new NoSuchElementException("Stack is empty");

        Item item = first.item;

        first = first.next;

        n--;

        return item;

    }

    //1.3.7

    public Item peek() {

        if(isEmpty())

            throw new NoSuchElementException("Stack is empty");

        return first.item;

    }

    public boolean isEmpty() {

        return first == null;

    }

    public int size() {

        return n;

    }

    @Override

    public Iterator<Item> iterator() {

        return new StackIterator();

    }

    private class StackIterator implements Iterator<Item> {

        private Node current = first;

        @Override

        public boolean hasNext() {

            return current != null;

        }

        @Override

        public Item next() {

            if(!hasNext())

                throw new NoSuchElementException("Stack is empty");

            Item item = current.item;

            current = current.next;

            return item;

        }

        @Override

        public void remove() {

            throw new UnsupportedOperationException("Stack don't support remove");

        }

    }

    public static void main(String[] args) {

        Stack<String> stack = new Stack<String>();

        StdOut.println("Initialized size:" + stack.size());

        while (!StdIn.isEmpty()) {

            String item = StdIn.readString();

            if (!item.equals("-")) {

                stack.push(item);

                StdOut.println("push success:" + item + " size:" + stack.size());

                StdOut.print("Left on stack: ");

                for (String s : stack) {

                    StdOut.print(s + " ");

                }

                StdOut.println();

            } else {

                if(stack.isEmpty())

                    StdOut.println("pop error, stack empty");

                else {

                    StdOut.println("pop success:" + stack.pop() + " size:" + stack.size());

                    StdOut.print("Left on stack: ");

                    for (String s : stack) {

                        StdOut.print(s + " ");

                    }

                    StdOut.println();

                }

            }

        }

    }

}