Solução do STPAR - Street Parade (SPOJ) - Execução Comentada

Principal.java

import java.util.ArrayList;
import java.util.Scanner;

/** 
 * Maratona de Programação - Laboratório II
 * Problema Street Parade 
 * Bruno Armanelli & Davi Santos @ PUC Minas
 */

class Caminhao {
    private int valor;
    private Caminhao anterior;
    
    public void setAnterior(Caminhao anterior) {
        this.anterior = anterior;
    }
    
    public Caminhao getAnterior() {
        return anterior;
    }
    
    public void setValor(int valor) {
        this.valor = valor;
    }
    
    public int getValor() {
        return valor;
    }
}

class Pilha {
    Caminhao topo = null;

    public Pilha() {
    }

    public void empilha(int valor) throws Exception {
        Caminhao novo = new Caminhao();
        novo.setValor(valor);
        novo.setAnterior(topo);
        topo = novo;
    }
    
    public int desempilha() throws Exception {
        if(topo == null) {
            throw new Exception("Erro: Pilha vazia");
        }
        
        int valor = topo.getValor();
        topo = topo.getAnterior();
        return valor;
    }
    
    public boolean vazia() {
        if(topo == null) {
           return true;
        }
        return false;
    }
    
}

class Principal {
	
	// Remover as linhas de println para SPOJ
	private static String resolve (int car []) throws Exception {
		Pilha desfile = new Pilha();
		int temp, proxDesfile;
		proxDesfile = 1; // Primeiro do desfile
		
		String resultado = "no\n";
		System.out.println("\n\n"); // Remover
		
		// Percorre vetor e compara alementos com o proximo a ser desfilado
		for(int i = 0; i < car.length; i++) {
		    // Compara item do vetor com proximo do desfile
		    if(car[i] != proxDesfile) {
		        System.out.println(car[i] + " é diferente de " + proxDesfile);
		        
		        // Desempilha, verifica, e repete ou se não, reempilha
		        for(int j = car.length - proxDesfile; j > 0; j--) {
    		        if(!desfile.vazia()) {
    		            temp = desfile.desempilha();
    		            System.out.println("<< desempilhou: " + temp);
    		            
    		            if(temp != proxDesfile) {
    		                System.out.println(temp + " é diferente de " + proxDesfile);
    		                desfile.empilha(temp);
    		                System.out.println(">> empilhou de volta: " + temp);
    		                break;
    		            } else {
    		                proxDesfile++;
    		                System.out.println(temp + " passou no desfile");
    		            }
    		        } else {
    		            break;
    		        }
		        }
		       
		        desfile.empilha(car[i]);
		        System.out.println(">> empilha: " + car[i]);
		    } else {
		        // Empilha do vetor se não compativel
		        System.out.println(car[i] + " eh igual a " + proxDesfile);
		        proxDesfile++;
		        System.out.println(car[i] + " passou no desfile");
		        System.out.println("o proximo do desfile eh " + proxDesfile);
		    }
		}
	
    	// Se houver elementos no fim, desempilha e verifica
		if(proxDesfile <= car.length) {
		    System.out.println("\n-- VERIFICACAO DO RESTANTE NA PILHA -- \n");
		    System.out.println("faltam " + (car.length - proxDesfile + 1) + " na fila");
		    
		    for(int i = 0; i <= (car.length - proxDesfile); i++) {
		        temp = desfile.desempilha();
		        System.out.println("<< desempilhou " + temp);
		        
		        if(temp != proxDesfile) {
		            System.out.println("xxx " + temp + " nao eh igual a " + proxDesfile + " xxx");
		            return resultado;
		        } else {
		            System.out.println(temp + " eh igual a " + proxDesfile);
		            proxDesfile++;
		            System.out.println("o proximo do desfile eh " + proxDesfile);
		        }
		    }
		}
		
		resultado = "yes\n";		
				
		return resultado; 
	}

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		
		String resultado;
        
        String parametros[];    
        
        Scanner input = new Scanner (System.in);
        String line;
                
        boolean EndOfInput = true;      
                       
        int n;
        
        while(EndOfInput)
        {    
            line = input.nextLine();
            
            n = Integer.parseInt(line);
            
            if (n == 0) {
            	EndOfInput = false;
            }
            else {
            	
            	line = input.nextLine();

                parametros = line.split(" ");
            	
            	int car [] = new int [n];
                
                for (int i = 0; i < n; i++) 
                	car[i] = Integer.parseInt(parametros[i]);
                
                resultado = resolve (car);
                
                System.out.printf(resultado);
            	
            }
        }     
	}
}