⚡ Implementaciones de Listas, Pilas y Colas

[GabrielEValenzuela]

🔀 Control de Acceso Circular

Escenario

El sistema biométrico de acceso al refugio está basado en una lista circular. Cada visitante es registrado en una lista simplemente enlazada circular, sin cabecera. El sistema sólo puede mantener un único iterador.

Desafío

Queremos simular una cola (FIFO) de acceso al refugio. Evaluá estas dos opciones:

• a) El iterador apunta al primer nodo (visitante en la entrada).
• b) El iterador apunta al último nodo (visitante más reciente).

Explicá cuál opción permite realizar enqueue y dequeue en tiempo constante O(1), y justificá tu elección.

---

🔥 Protocolo de Eliminación (Josephus)

Escenario

Durante una simulación de combate, se propuso el protocolo de eliminación Josephus:

• Hay N soldados en un círculo.
• Se pasa una granada de entrenamiento.
• Luego de M pases, el soldado con la granada es eliminado.
• El siguiente retoma el ciclo hasta que solo queda un ganador.

Tareas

1. Implementá una función que reciba N y M y devuelva el orden de eliminación y el ganador.
2. Analizá la complejidad temporal.
3. Si M = 1, analizá el impacto en rendimiento para N > 100000.

Hint: Idealmente deberías usar una lista circular. Eliminar nodos con eficiencia es clave.

---

📦 Transferencias entre Módulos Limitados

Escenario

Alice, una ingeniera, dispone de 3 módulos de almacenamiento:

• A: capacidad 100 (lleno).
• B: capacidad 5 (vacío).
• C: capacidad 3 (vacío).

La única operación permitida es transfer(S, T), que transfiere elementos de una pila S a T hasta que S esté vacía o T llena.

Desafío

Diseñá una secuencia de transfer() para que al final la pila B contenga exactamente 4 elementos.

Pensá en el orden de transferencias entre A, B y C. Podes usar papel o una simulación simple.

---

♻️ Cola usando Pilas

Escenario

El sistema de eventos del refugio sufrió una falla. La cola nativa dejó de funcionar. La solución temporal propuesta fue emular una cola usando dos pilas.

Desafío

Implementá una clase QueueViaStacks que soporte enqueue, dequeue y front usando sólo dos stacks.

• Justificá cómo se mantiene el orden FIFO.
• Bonus: agregá comandos de consola para probarlo.

---

🧱 4. Visibilidad en la Torre de Vigilancia

Basado en pilas y recorrido en reversa

Desde una torre en el Refugio 33 se observan soldados alineados de izquierda a derecha. Se conoce la altura de cada uno.

Consigna:

Dado un vector de alturas de soldados, devolvé un vector respuesta[i] que indique cuántos soldados puede ver el soldado i hacia su derecha, considerando:

• El soldado i puede ver al j si i < j y todos los soldados entre i y j son más bajos que ambos.

Input:  [10,6,8,5,11,9]
Output: [3,1,2,1,1,0]

Input:  [5,1,2,3,10]
Output: [4,1,1,1,0]

Tip: Este ejercicio se puede resolver en O(n) usando una pila.

Modalidad de entrega

Comentario en esta issue

[BaltasarMottura]

Transferencias entre Módulos Limitados:

void transfer(Stack pilaOrigen, Stack pilaDestino){
      
      Nodo* aux = new Nodo<T>(pilaOrigen.czo);
      
      for(int i=0, i<pilaDestino.size(), i++){
          pilaDestino.add(aux);
          pilaOrigen.pop();
          aux=aux->next;
      }
      if(pilaDestino.getNombre()=="B"){
          for(int i=0, i<pilaDestino.size()-1, i++){
          pilaDestino.add(aux);
          pilaOrigen.pop();
          aux=aux->next;
      }
      }
          
}

[giraudoignacio]

🔥 Protocolo de Eliminación (Josephus)

Lista Josephus(int N, int M) {
    Lista ordenEliminacion;
    Nodo* actual = obtenerLista(N);

    while ((actual != nullptr) && (actual->siguiente != actual)) {
        for (int i = 1; i < M; i++) {
            actual = actual->siguiente;
        }

        Nodo* eliminado = actual->siguiente;
        ordenEliminacion.push(eliminado->soldado);
        actual->siguiente = eliminado->siguiente;
        delete eliminado;
        actual = actual->siguiente;
    }

    ordenEliminacion.push(actual->id); 
    delete actual;

    return ordenEliminacion;
}