Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Estructuras de Datos/Guías prácticas/Secuencias/Solución al ejercicio 7 de secuencias

De Wikilibros, la colección de libros de texto de contenido libre.
Ir a la navegación Ir a la búsqueda

Una vez ordenados los desastres, en principio haría falta un recorrido hacia atrás desde cada uno de los elementos para determinar cual cumple con la condición que estamos buscando. Como un primer criterio necesario de esa búsqueda es que el tiempo sea el mayor, deberíamos tener acceso primero al último elemento. Si éste fuere inferior al actual, podríamos descartarlo de la búsqueda actual; es más, podemos descartarlo de todas las búsquedas, ya que contamos con un elemento de mayor valor y tiempo posterior; sólo hará falta conservar el elemento superior al actual, y los superiores a él que fueran guardados al procesar elementos anteriores. Para realizar este procedimiento se puede usar una pila, y haciendo sólo un recorrido secuencial, para el recorrido total en el peor de los casos entrarán y saldrán cada uno de los elementos en la pila, una sola vez.

 public class Desastre implements Comparable{

   private Date fecha;
   private int victimas;
   private Date fechaUltimoConMasVictimas;

   public static void completar(Vector desastres)
   {
     QuickSort.quickSort(desastres);
     Stack anteriores=new Stack();
     anteriores.push(desastres.elementAt(0));
     for (int i=1;i<desastres.size();i++)
     {
       while(!anteriores.isEmpty())
       {
         if (((Desastre)(anteriores.top())).getVictimas()>((Desastre)(desastres.elementAt(i))).getVictimas())
         {
           ((Desastre)(desastres.elementAt(i))).setFechaUltimoConMasVictimas(((Desastre)(anteriores.top())).getFecha());
           break;
         }
         else anteriores.pop();
       }
       anteriores.push(desastres.elementAt(i));
     }
   }

   /* (non-Javadoc)
    * @see java.lang.Comparable#compareTo(java.lang.Object)
    */
   public int compareTo(Object arg0) {
     if (arg0 instanceof Desastre)
       return this.fecha.compareTo(((Desastre)arg0).getFecha());
     else return 0; //excepcion?
   }