Soluzione 8.7

Il metodo main di questa classe e` in pratica identico a quello dell'esercizio precedente. I metodi sortStack sono sostanzialmente una realizzazione di selectionSort ottenuta usando solo pile come strutture di memorizzazione dei dati. Ci sono due cicli annidati: per ogni iterazione del ciclo esterno, il ciclo interno scorre tutti gli elementi della pila non ancora ordinati e tra questi identifica quello massimo, per poi scriverlo nella pila.
import java.util.Scanner;
import java.util.StringTokenizer;

public class StackSorter
{   public static void main(String[] args)
    {   //controllo parametro passato sulla riga di comando: se vale "a" uso la
        //soluzione che impiega 2 pile temporanee, se vale "b" uso la soluzione
        //che impiega 1 pila temporanea
        if (args.length != 1 || (!args[0].equals("a") && !args[0].equals("b")))
        {   System.out.println("Uso: $java StackSorter < arg >");
            System.out.println("Se arg = \"a\" si usa soluzione a (2 pile)");
            System.out.println("Se arg = \"b\" si usa soluzione b (1 pila)");
            System.exit(1);
        }

        //Creo una pila e vi inserisco numeri interi letti da standard input 
        Scanner in = new Scanner(System.in);
        Stack stack = new ArrayStack();
        while (in.hasNextLine())
        {   StringTokenizer stok = new StringTokenizer(in.nextLine());
            while (stok.hasMoreTokens())
                stack.push(new Double(Double.parseDouble(stok.nextToken())));
        }

        //effettuo l'ordinamento della pila
        if (args[0].equals("a"))    sortStack_a(stack);
        else                        sortStack_b(stack);

        System.out.println("*** Pila con elementi ordinati ***");
        while (!stack.isEmpty())
            System.out.println(stack.pop());
    }

    /*
        Soluzione a: si usano due pile temporanee temp1 e temp2. L'algoritmo
        proposto realizza in sostanza un ordinamento per selezione, in cui le
        le uniche strutture di memorizzazione sono pile
    */
    public static void sortStack_a(Stack s)
    {   Stack temp1 = new ArrayStack();
        while (!s.isEmpty())
            temp1.push(s.pop());   //temp1 contiene una copia dei dati di s
        while (!temp1.isEmpty())
        {   Stack temp2 = new ArrayStack();//creo un'altra pila temporanea vuota
            Comparable max = (Comparable) temp1.pop(); //travaso temp1 in temp2 
            while (!temp1.isEmpty()) //e mentre travaso trovo l'elemento massimo
            {   Comparable c = (Comparable) temp1.pop();
                if (c.compareTo(max) < 0)
                    temp2.push(c);
                else
                {   temp2.push(max);
                    max = c;
                }
            }
            /* alla fine di questo ciclo while interno
               - max e` l'elemento massimo di temp1 (cioe` di s)
               - temp1 e` stata svuotata e travasata in temp2
               - temp2 contiene tutti gli elementi di temp1 (cioe` di s),
                 tranne l'elemento massimo max
            */
            s.push(max);   //scrivo l'elemento massimo nella pila originaria s
            temp1 = temp2; //ora temp1 punta alla pila che contiene tutti gli
        }                 //elementi di s tranne quello massimo: a questo punto
    }                     //posso iterare il ciclo while esterno.

    /*
        Soluzione b: invece di temp2 usiamo s come pila temporanea. Dobbiamo
        sapere quanti sono gli elementi di s che costituiscono la parte di 
        memorizzazione temporanea, per distinguerli dalla parte ordinata
    */
    public static void sortStack_b(Stack s)
    {   Stack temp = new ArrayStack();
        int toOrder = 0; //in ogni momento toOrder e` il numero di elementi in
                         //temp, ovvero il numero di elementi ancora da ordinare
        while (!s.isEmpty())
        {   temp.push(s.pop());
            toOrder++;
        }
        while (toOrder > 0)
        {   Comparable max = (Comparable) temp.pop();
            toOrder--;
            for (int i = 0; i < toOrder; i++) //estraggo tutti gli elem. di temp
            {   Comparable c = (Comparable) temp.pop();
                if (c.compareTo(max) < 0)
                    s.push(c);
                else
                {   s.push(max);
                    max = c;
                }
            }
            for (int i = 0; i < toOrder; i++)
                temp.push(s.pop());
            s.push(max);
        }
    }  
}