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.
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.
Lo que quedó
rotar mueve un nodo de un extremo al otro con cuatro
escrituras de puntero: Θ(1) en tiempo y Θ(1) en espacio aparte, sin
reservar ni liberar memoria. Escrita con el contrato,
encolar(frente()) seguido de desencolar(),
también es Θ(1), pero reserva un nodo y libera otro en cada llamada. Con
punteros, el orden de las asignaciones decide: un enlace se lee antes de cortarlo, y el caso
de un solo elemento, donde cabeza y ultimo son el
mismo nodo, se revisa aparte.