import java.io.PrintStream;
import java.io.UnsupportedEncodingException;
import java.util.Random;
import java.util.Scanner;

public class Pila {

    private Pila liga;
    private int dato;

    public static Scanner teclado = new Scanner(System.in);
    public static PrintStream out;
    public static String FLECHA = "\u2500\u25BA";
   
    private Pila() {}

    public static Pila create() {
        return null;
    }
   
    public static int peek(Pila nodo) {
        return nodo.dato;
    }
   
    public static boolean empty(Pila nodo) {
        return nodo == null;
    }

    public static Pila push(Pila cabecera, int dato) {
        Pila nodo = new Pila();
        nodo.liga = cabecera;
        nodo.dato = dato;
        return nodo;
    }

    public static Pila remove(Pila nodo, int dato) {
        if (!empty(nodo)) {
            if (peek(nodo) == dato)
                return pop(nodo);
            nodo.liga = remove(nodo.liga, dato);
        }
        return nodo;
    }

    public static void list(Pila nodo) {
        if (!empty(nodo)) {
            list(nodo.liga);
            out.println(peek(nodo));
        }
    }

    public static boolean sort(Pila nodo) {
        int dato;
        boolean cambio = false;
        if (!empty(nodo) && !empty(nodo.liga)) {
            if (peek(nodo) < peek(nodo.liga)) {
                dato = peek(nodo);
                nodo.dato = peek(nodo.liga);
                nodo.liga.dato = dato;
                cambio = true;
            }
            cambio = cambio || sort(nodo.liga);
            if (cambio)
                sort(nodo);
        }
        return cambio;
    }

    public static Pila reverse(Pila nodo, Pila inversa) {
        if (!empty(nodo))
            inversa = reverse(nodo.liga, push(inversa, peek(nodo)));
        return inversa;
    }

    public static void print(Pila nodo) {
        if (!empty(nodo)) {
            out.print(peek(nodo) + " " + FLECHA + " ");
            print(nodo.liga);
        } else
            out.println("null\n");
    }

    public static int size(Pila nodo) {
        return empty(nodo) ? 0 : 1 + size(nodo.liga);
    }

    public static Pila insert_first(Pila nodo, int dato) {
        if (empty(nodo))
            return push(Pila.create(), dato);
        nodo.liga = insert_first(nodo.liga, dato);
        return nodo;
    }

    public static Pila remove_first(Pila nodo) {
        if (!empty(nodo)) {
            if (empty(nodo.liga))
                return pop(nodo);
            nodo.liga = remove_first(nodo.liga);
        }
        return nodo;
    }

    public static boolean contains(Pila nodo, int dato) {
        return !empty(nodo) && (peek(nodo) == dato || contains(nodo.liga, dato));
    }

    public static Pila pop(Pila nodo) {
        return !empty(nodo) ? nodo.liga : Pila.create();
    }

    public static int leer_entero(String mensaje) {
        int entero;
        out.print("Ingrese " + mensaje + ": ");
        entero = Integer.parseInt(teclado.nextLine());
        out.println();
        return entero;
    }

    public static void main(String[] args) throws UnsupportedEncodingException {
        Pila cabecera = Pila.create();
        int dato;
        String input;
        char opcion;
        Random random = new Random();
        if(System.getProperties().get("os.name").equals("Linux") || System.console()==null)
            out = new PrintStream(System.out);
        else {
            out = new PrintStream(System.out, true, "CP850");
            FLECHA = "\u2500\20";
        }
        do {
            out.println("\n\n\n\n\n\n\n\n");
            out.print("OPERACIONES B\u00C1SICAS DE PILAS\n"
                    + "a) Insertar un n\u00FAmero al final\n"
                    + "b) Quitar el \u00FAltimo n\u00FAmero\n"
                    + "c) Listar n\u00FAmeros\n"
                    + "d) Tama\u00F1o de la pila\n"
                    + "e) Vaciar pila\n"
                    + "OPERACIONES COMPLEMENTARIAS\n"
                    + "f) Insertar n\u00FAmeros aleatorios\n"
                    + "g) Insertar un n\u00FAmero al principio\n"
                    + "h) Consular si contiene un n\u00FAmero\n"
                    + "i) Quitar un n\u00FAmero a buscar\n"
                    + "j) Quitar el primer n\u00FAmero\n"
                    + "k) Ordenar pila\n"
                    + "l) Ivertir pila\n"
                    + "m) Salir\n\n"
                    + "Seleccione una opci\u00F3n: ");
            do {
                input = teclado.nextLine().toLowerCase();
            } while (input == null || input.length() != 1 || input.charAt(0) < 'a' || input.charAt(0) > 'm');
            opcion = input.charAt(0);
            if (opcion != 'm') {
                out.println();
                if (Pila.empty(cabecera) && opcion != 'a' && opcion != 'd' && opcion != 'f' && opcion != 'g')
                    out.println("La pila est\u00E1 vac\u00EDa.\n");
                else {
                    if (opcion != 'c' && opcion != 'd' && opcion != 'h') {
                        out.println("Pila original:");
                        Pila.print(cabecera);
                    }
                    switch (opcion) {
                    case 'a': /* Insertar un numero al final */
                        dato = leer_entero("el n\u00FAmero a insertar");
                        cabecera = Pila.push(cabecera, dato);
                        break;
                    case 'b': /* Quitar el ultimo numero */
                        cabecera = Pila.pop(cabecera);
                        break;
                    case 'c': /* Listar numeros */
                        Pila.list(cabecera);
                        out.println();
                        break;
                    case 'd': /* Tamano de la pila */
                        out.println("Tama\u00F1o de la pila: " + Pila.size(cabecera) + ".\n");
                        break;
                    case 'e': /* Vaciar pila */
                        while (!Pila.empty(cabecera))
                            cabecera = Pila.pop(cabecera);
                        break;
                    case 'f': /* Insertar numeros aleatorios */
                        dato = leer_entero("la cantidad de n\u00FAmeros aleatorios a insertar");
                        for (; dato > 0; dato--)
                            cabecera = Pila.push(cabecera, random.nextInt(1000));
                        break;
                    case 'g': /* Insertar un numero al principio */
                        dato = leer_entero("el n\u00FAmero a insertar");
                        cabecera = Pila.insert_first(cabecera, dato);
                        break;
                    case 'h': /* Consular si existe un numero */
                        dato = leer_entero("el n\u00FAmero a consultar");
                        out.println("El n\u00FAmero " + dato + " "
                            + (Pila.contains(cabecera, dato) ? "s\u00ED" : "no")
                            + " est\u00E1 en la pila.\n");
                        break;
                    case 'i': /* Quitar un numero a buscar */
                        dato = leer_entero("el n\u00FAmero a remove");
                        cabecera = Pila.remove(cabecera, dato);
                        break;
                    case 'j': /* Quitar el primer numero */
                        cabecera = Pila.remove_first(cabecera);
                        break;
                    case 'k': /* Ordenar pila */
                        Pila.sort(cabecera);
                        break;
                    case 'l': /* Ivertir pila */
                        cabecera = Pila.reverse(cabecera, Pila.create());
                        break;
                    }
                    if (opcion != 'c' && opcion != 'd' && opcion != 'h') {
                        out.println("Pila actualizada:");
                        Pila.print(cabecera);
                    }
                }
                out.print("Presione <ENTER> tecla para continuar . . . ");
                teclado.nextLine();
            }
        } while (opcion != 'm');
    }

}