← Volver a los ejercicios

Lo que cobra cada operación

Tres programas con el mismo contrato de cola y perfiles de uso distintos. Las cuatro implementaciones en juego son el arreglo circular, la cola sobre la lista de arreglo, la cola sobre la lista enlazada simple y la cola sobre la lista con puntero al último.

1. El máximo se conoce y la memoria está contada

Un controlador recibe mediciones y nunca puede tener más de 256 pendientes: el protocolo lo garantiza. Corre en un dispositivo con poca memoria, así que lo que importa es cuántos bytes ocupa cada medición guardada.

2. Sin saber cuántos van a llegar

Un servidor encola las peticiones que llegan y las atiende en orden. En una hora tranquila pasan cientos; en un pico pueden ser cientos de miles, y nadie sabe de antemano cuál es el máximo.

3. La propuesta de la enlazada simple

Para el servidor del punto anterior alguien propone la cola sobre la lista enlazada simple, con este argumento: desencolar es Θ(1), porque el frente es la cabeza y sacarla es mover un puntero. ¿Sirve?

4. La cuenta de la que sí sirve

Encolando n = 40 veces y desencolando los 40 sobre la lista con puntero al último, ¿cuántos elementos se tocan en total? Tocar un elemento es correrlo en el arreglo o visitar su nodo en un recorrido.