/*************************************************************************
 *  Compilation:  javac LinkedStack.java
 *  Execution:    java LinkedStack < input.txt
 *
 *  A generic stack, implemented using a linked list. Each stack
 *  element is of type Item.
 *  
 *  % more tobe.txt 
 *  to be or not to - be - - that - - - is
 *
 *  % java LinkedStack < tobe.txt
 *  to be not that or be (2 left on stack)
 *
 *************************************************************************/

import java.util.Iterator;
import java.util.NoSuchElementException;


/** The LinkedStack class represents a last-in-first-out (LIFO) 
 * stack of  generic items. It supports the usual push and pop operations, 
 * along with methods for peeking at the top item, 
 * testing if the stack is empty, and iterating through the items in LIFO order.
 * <p>
 * This implementation uses a singly-linked list with a non-static 
 * nested class for linked-list nodes. See the Stack class
 * for a version that uses a static nested class.
 * The push, pop, peek, size, and is-empty operations all take 
 * constant time in the worst case.
 * <p>
 * For additional documentation, see algs4.cs.princeton.edu/13stacks/ or
 * Section 1.3, page 120, of "Algorithms, 4th Edition", by Robert Sedgewick 
 * and Kevin Wayne.
 *
 * @author Robert Sedgewick
 * @author Kevin Wayne
 */

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

    private int N;          // size of the stack
    private Node first;     // top of stack

    // helper linked list class
    private class Node {
        private Item item;
        private Node next;
    }

    /** Initializes an empty stack.
     */
    public LinkedStack() {
        first = null;
        N = 0;
        assert check();
    }

    /** Is this stack empty?
     * Returns true if this stack is empty; false otherwise.
     */
    public boolean isEmpty() {
        return first == null;
    }

    /** Returns the number of items in this stack.
     */
    public int size() {
        return N;
    }

    /** Adds item to this stack.
     */
    public void push(Item item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
        assert check();
    }

    /** Removes and returns the item most recently added to this stack.
     * Throws java.util.NoSuchElementException if this stack is empty.
     */
    public Item pop() {
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
        Item item = first.item;        // save item to return
        first = first.next;            // delete first node
        N--;
        assert check();
        return item;                   // return the saved item
    }


    /** Returns (but does not remove) the item most recently added 
     * to this stack.
     * Throws java.util.NoSuchElementException if the stack is empty.
     */
    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
        return first.item;
    }

    /** Returns a string representation of this stack.
     * Returns the sequence of items in the stack in LIFO order, 
     * separated by spaces.
     */
    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Item item : this)
            s.append(item + " ");
        return s.toString();
    }
       
    /** Returns an iterator that iterates through the items 
     * of this stack in LIFO order.
     */
    public Iterator<Item> iterator() { 
        return new ListIterator();  
    }

    // An iterator. 
    private class ListIterator implements Iterator<Item> {
        private Node current = first;
        public boolean hasNext() { 
            return current != null;
        }
        public void remove() { 
            // Need not implement remove() since it is optional.
            throw new UnsupportedOperationException();
        }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next; 
            return item;
        }
    }

    // check internal invariants
    private boolean check() {
        if (N == 0) {
            if (first != null) return false;
        }
        else if (N == 1) {
            if (first == null)      return false;
            if (first.next != null) return false;
        }
        else {
            if (first.next == null) return false;
        }

        // check internal consistency of instance variable N
        int numberOfNodes = 0;
        for (Node x = first; x != null; x = x.next) {
            numberOfNodes++;
        }
        if (numberOfNodes != N) return false;

        return true;
    }

    /** Unit test of this LinkedStack data type.
     * Builds a stack of strings from the strings given on standard input;
     * each item entered is pushed onto the stack,
     * unless item is "-", in which case an item is popped from the stack.
     * After input stream ends (this is signaled by typing Ctrl-z
     * if you are using Windows or Ctrl-d if you are using Unix),
     * prints the number of items left on the stack.
     */
    public static void main(String[] args) {
        LinkedStack<String> s = new LinkedStack<String>();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) s.push(item);
            else if (!s.isEmpty()) StdOut.print(s.pop() + " ");
        }
        StdOut.println("(" + s.size() + " left on stack)");
    }
}