Clase 21 de 23 • Curso de Estructuras de Datos Lineales con Python
Contenido del curso
¿Cómo se construye un Queue utilizando nodos?
En el fascinante mundo de las estructuras de datos, los queues (colas) pueden construirse sobre elementos simples como listas, arrays o incluso nodos. En esta clase, exploramos cómo crear un queue basado en nodos, específicamente utilizando una lista doblemente enlazada. Este enfoque optimiza ciertas operaciones, ofreciendo una eficiencia en tiempo constante, un tema conocido como notación Big O.
¿Qué es un nodo y cómo se utiliza en un Queue?
Un nodo es una estructura que lleva un valor y referencias al siguiente y anterior nodo en la estructura. Imagina un vagón de tren; cada nodo contiene datos y se conecta con el anterior y el siguiente. La gran ventaja de usar nodos, en lugar de otras estructuras como arrays, es que agregar o eliminar nodos es una operación muy eficiente, siendo de orden constante O(1) en notación Big O.
Implementación de la clase Queue
Vamos a implementar la clase Queue utilizando nodos como base. Primero, necesitas crear la clase para representar la cola y luego implementar los métodos esenciales: enqueue (añadir elementos) y dequeue (eliminar elementos).
A continuación, vemos cómo implementar esta clase:
class Nodo: def __init__(self, data): self.data = data self.next = None self.prev = None class Queue: def __init__(self): self.head = None self.tail = None self.count = 0 def enqueue(self, data): nuevo_nodo = Nodo(data) if not self.head: self.head = nuevo_nodo self.tail = nuevo_nodo else: nuevo_nodo.prev = self.tail self.tail.next = nuevo_nodo self.tail = nuevo_nodo self.count += 1 def dequeue(self): if self.count == 0: return None current = self.head if self.count == 1: self.head = None self.tail = None else: self.head = self.head.next self.head.prev = None self.count -= 1 return current.data
Probar la implementación
Ahora que tenemos los métodos básicos implementados en nuestra clase Queue, es hora de ponerlos a prueba en un entorno interactivo de Python:
enqueue.dequeue.# Importar la clase Queue desde el módulo donde está implementada from your_module import Queue # Instanciar la cola mi_cola = Queue() # Añadir elementos mi_cola.enqueue("huevos") mi_cola.enqueue("jamón") mi_cola.enqueue("spa") # Verificar el primer elemento print(mi_cola.head.data) # Salida esperada: "huevos" # Remover elementos print(mi_cola.dequeue()) # Salida esperada: "huevos"
Aplicaciones prácticas de un Queue basado en nodos
Un queue basado en nodos es especialmente útil en sistemas donde el manejo eficiente y dinámico de datos es crucial. Piensa en un sistema de gestión de turnos: puedes tener una base de datos de clientes o pacientes, donde un queue asegura que se atienden en el orden de llegada sin necesidad de duplicar datos en otras estructuras como arrays, que pueden tener limitaciones de tamaño.
Este tipo de estructura también se utiliza en simulaciones de playlists musicales, donde las canciones, organizadas como nodos, se tocan secuencialmente.
Más allá de lo básico
Hemos explorado cómo la integración de métodos y estructuras puede llevar a una implementación más eficiente. Pero esto es solo el comienzo. Te animo a continuar explorando y modificando esta estructura para adecuarla a tus necesidades específicas. La programación se trata de adaptabilidad y experimentación, así que ¡sigue explorando!