/*************************************************************************
 *  Kompilacja:  javac Stack.java
 *  Wykonanie:    java Stack < input.txt
 *
 *  Generyczny stos zaimplementowany za pomocą listy powiązanej. Każdy element
 *  stosu jest typu Item.
 *  
 *  % more tobe.txt 
 *  to be or not to - be - - that - - - is
 *
 *  % java Stack < tobe.txt
 *  to be not that or be (elementy na stosie: 2)
 *
 *************************************************************************/

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


/**
 *  Klasa <tt>Stack</tt> reprezentuje stos LIFO generycznych elementów.
 *  Obsługuje standardowe operacje <em>push</em> i <em>pop</em>, a także metody
 *  do podglądania elementu z wierzchołka, sprawdzania, czy stos jest pusty, i przechodzenia
 *  po elementach w porządku LIFO.
 *  <p>
 *  Wszystkie operacje na stosie z wyjątkiem iterowania zajmują stały czas.
 *  <p>
 *  Dodatkową dokumentację można znaleźć w <a href="/algs4/13stacks">podrozdziale 1.3</a> książki
 *  <i>Algorytmy, wydanie czwarte</i> Roberta Sedgewicka i Kevina Wayne'a.
 */
public class Stack<Item> implements Iterable<Item> {
    private int N;          // Wielkość stosu
    private Node first;     // Wierzchołek stosu

    // Pomocnicza klasa dla listy powiązanej
    private class Node {
        private Item item;
        private Node next;
    }

   /**
     * Tworzenie pustego stosu
     */
    public Stack() {
        first = null;
        N = 0;
    }

   /**
     *Czy stos jest pusty?
     */
    public boolean isEmpty() {
        return first == null;
    }

   /**
     * Zwraca liczbę elementów na stosie
     */
    public int size() {
        return N;
    }

   /**
     * Dodaje element do stosu
     */
    public void push(Item item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }

   /**
     * Usuwa i zwraca element ostatnio dodany do stosu.
     * Zgłasza wyjątek, jeśli stos jest pusty.
     */
    public Item pop() {
        if (isEmpty()) throw new RuntimeException("Brak elementów na stosie");
        Item item = first.item;        // Zapisywanie zwracanego elementu
        first = first.next;            // Usuwanie pierwszego węzła
        N--;
        return item;                   // Zwracanie zapisanego elementu
    }


   /**
     * Zwraca element ostatnio dodany do stosu.
     * Zgłasza wyjątek, jeśli stos jest pusty.
     */
    public Item peek() {
        if (isEmpty()) throw new RuntimeException("Brak elementów na stosie");
        return first.item;
    }

   /**
     * Zwraca łańcuch reprezentujący stos.
     */
    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Item item : this)
            s.append(item + " ");
        return s.toString();
    }
       

   /**
     * Zwraca iterator stosu przechodzący po elementach w porządku LIFO.
     */
    public Iterator<Item> iterator()  { return new LIFOIterator();  }

    // Iterator (bez implementacji opcjonalej metody remove())
    private class LIFOIterator implements Iterator<Item> {
        private Node current = first;
        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

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


   /**
     * Klient testowy
     */
    public static void main(String[] args) {
        Stack<String> s = new Stack<String>();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) s.push(item);
            else if (!s.isEmpty()) StdOut.print(s.pop() + " ");
        }
        StdOut.println("(elementy na stosie: " + s.size() + ")");
    }
}

