Antes de Leer este Post
Aún y cuando este escrito menciona algunas de las características de las Colas(Queues) y Lista Enlazadas(Linked Lists) con el propósito de situar al lector en el contexto de la problemática a resolver, este post no tiene la intención de ahondar en dichas estructuras. Esto en vista de que existen infinidad de recursos en internet que pueden proporcionar al lector un profundo entendimiento acerca de estos tópicos.
Introducción a la Problemática
Las operaciones encolar y desencolar que pueden ser efectuadas en una cola siempre poseen una complejidad constante de O(1), mientras que la complejidad computacional de agregar y remover nodos en una lista enlazada puede ir de O(1) a O(n), en virtud de la posición del nodo.
Ingreso de Elementos en Lista Vacía
De esta forma, insertar o purgar un nodo al principio de una lista enlazada tiene una complejidad de O(1) debido que no se debe recorrer la estructura con el fin de llevar a cabo semejantes acciones. No obstante, el realizar un acción sobre una posición n( donde n es diferente de cero ) en una lista enlizada, conlleva el recorrer n posiciones en la lista antes de poder desempeñar tal acción. Así, se concluye que el ejecutar una tarea sobre una lista enlazada, puede arrastrar una complejidad O(n).
Ingreso de Nodos en Lista con Elementos
Entonces, si las operaciones que pueden ser realizadas tanto en una cola como en una lista enlazadas poseen complejidades computacionales diferentes ¿Cómo es posible implementar una cola mediante una lista enlazada? La respuesta a es absurdamente sencilla. Mediante una lista enlazada capaz de:
- Agregar nuevos nodos al final de la lista en tiempo constante. Esto es posible mediante un nodo auxiliar capaz de guardar una referencia al último nodo de la lista( en caso de que exista ).
- Remover el primer elemento de la lista en un tiempo O(1).
Código
Es bien sabido que las listas enlazadas se erigen a partir de un conjunto de nodos que antes de ser conectados, primero deben ser concebidos. Así, la clase Nodo tiene como objetivo el crear los eslabones que darán pie a la cola que se intenta poner en funcionamiento. Más aún, semejante clase asigna las propiedades de nodo siguiente y dato a cada objeto Nodo. Cabe destacar que Nodo no cuenta con el módulo asignarDato en virtud de que los datos hospedados en la cola no deben sufrir alteraciones.
| class Nodo: | |
| def __init__( self, dato ): | |
| self.dato = dato | |
| self.sig = None | |
| #def asignarDato( self, dato ): | |
| # self.dato = dato | |
| def asignarSig( self, sig ): | |
| self.sig = sig | |
| def obtenerSig( self ): | |
| return self.sig | |
| def obtenerDato( self ): | |
| return self.dato |
Por su parte, la clase ListaEnlazada es responsable de llamar a la clase Nodo y especificarle los datos que deben estar contenidos en los elementos de la cola y la manera en que dichos elementos deben estar enlazados. Cabe destacar que aún y cuando esta clase se compone de múltiples métodos, este post tan sólo detalla los modulos más relevantes.
| def __init__( self ): | |
| self.cabeza = None | |
| self.cola = None | |
| self.tamanio = 0 |
- cabeza: Referencia al elemento que encabeza la cola. Es decir, el nodo próximo a salir de la estructura.
- cola: Referencia al último nodo agregado a la cola. Esta referencia es vital ya que permite agregar un nodo a la estructura en tiempo O(1).
- tamanio: Tamaño de la cola.
| def encolar( self, dato ): | |
| nuevoNodo = Nodo( dato ) | |
| if not self.cabeza: | |
| nuevoNodo.asignarSig( None ) | |
| self.cabeza = nuevoNodo | |
| else: | |
| self.cola.asignarSig( nuevoNodo ) | |
| self.cola = nuevoNodo | |
| self.tamanio += 1 |
El modulo encolar realiza una llamada a la clase Nodo para crear la variable nuevoNodo y posteriormente realiza las siguientes acciones:
- Identifica si un objeto listaEnlazada se encuentra vacío o no. De encontrarse el objeto falto de contenido( es decir, si la cabeza de lista apunta a None ), el método asigna la referencia de nuevoNodo a None y apunta la cabeza de la lista a nuevoNodo. De lo contrario, de no estar la lista vacía, este modulo simplemente asigna la referencia de la cola a nuevoNodo.
- Utiliza el nodo auxiliar cola para guardar la referencia al último nodo agregado a la lista. Dicho de otra forma, la variable cola siempre preserva a la variable nuevoNodo.
- Aumenta el valor de la variable tamanio en 1.
| def desencolar( self ): | |
| if self.cabeza: | |
| self.cabeza = self.cabeza.obtenerSig() | |
| self.tamanio -= 1 |
Por último, el código perteneciente al método desencolar únicamente se encarga de revisar, por medio de la cabeza del objeto lista si existen elementos en la cola. De existir, nodos en la estructura( es decir, de apuntar la cabeza a algo diferente de None), el nodo próximo a la cabeza, será asignado a la propia cabeza.
Eliminación del Primer Elemento de la Cola.
El código completo puede ser descargado desde aquí.
Juanito Banca 