¿Cómo invertir una cola?

Llegó alguien vía google buscando como invertir una cola. Ese es uno de esos algoritmos simples pero ingeniosos que dan en la clase de programación avanzada.

Se usan la cola y una pila. Se van desencolando los elementos de la cola y se colocan en la pila. Después se desapilan y se encolan en la cola. Como la pila es un buffer LIFO (el primero en entrar es el último en salir) el orden se invierte. Requiere 2n operaciones y emplea 2n espacio (resulta de orden lineal). Hasta ahí el algoritmo de clase, simple y elegante.

En caso de querer optimizar se podría hacer “magia” y convertir la pila (ya llena) en cola, si la implementación permite reusar los nodos; eso es, agregar una referencia al fondo de la pila; requiriendo entonces solamente n+1 operaciones.

También se podría implementar la cola como doblemente ligada y eso solamente necesitaría una operación, cambiar el “signo” de la dirección de la cola; es muy eficiente en tiempo, pero muy ineficiente en espacio, porque incrementa (puede llegar casi a duplicar, dependiendo de qué se está guardando) el tamaño de cada nodo.

Pues eso; de una operación tan aparentemente simple como invertir una cola se puede hablar mucho, es de esas cosas bonitas de la computación. Se puede pasar de largo, leer una fórmula de recetario y usarla toda la vida; pero lo interesante es buscar formas nuevas de hacer cada cosa, según la necesidad.

addendum: invertir una pila es aún más simple; no hace falta volcar la pila en una cola y de vuelta en la pila, es suficiente con volcarla en otra pila, y ya queda en orden inverso.