← Volver a los ejercicios

Ejercicios sobre las implementaciones: rotar la cola

Una operación nueva para la cola sobre nodos, la que guarda cabeza, ultimo y n: rotar() pasa el frente al final sin reservar ni liberar nodos, solo cambiando punteros. La cola de prueba es ⟨8, 3, 6, 1⟩, del frente al final.

1. Tres rotaciones

// exige !vacia()
void rotar() {
  assert(!vacia());
  if (cabeza != ultimo) {
    Nodo *primero = cabeza;
    cabeza = cabeza->siguiente;
    primero->siguiente = NULL;
    ultimo->siguiente = primero;
    ultimo = primero;
  }
}

Después de llamar tres veces a rotar(), ¿cómo queda la cola del frente al final?

2. La lista que hace falta debajo

¿Con cuál de estas cadenas queda rotar en Θ(1) sin gastar memoria de más?

3. El orden de las asignaciones

Tres cuerpos para el if, sobre una cola de dos elementos o más. ¿Cuál pierde la cadena?

4. Sin el if

Se quita el if (cabeza != ultimo) de la versión 1 y se llama rotar() sobre la cola ⟨5⟩. ¿Cómo queda?

5. Lo que cuesta

En las tres rotaciones del punto 1, ¿cuántas escrituras de puntero se hacen en total? Cuentan las asignaciones a cabeza, a ultimo y a los campos siguiente.