El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Colas Circulares

Siguiente ►
►

Introducción

Las colas circulares son una variante de las colas lineales en las que el último elemento está conectado al primer elemento, formando un círculo. Este tipo de estructura es útil para optimizar el uso del espacio en memoria y es comúnmente utilizada en aplicaciones donde se requiere un buffer circular, como en sistemas de transmisión de datos y en la gestión de recursos en sistemas operativos.

Conceptos Clave

  • Cola Circular: Una cola en la que el último elemento está conectado al primer elemento, formando un círculo.
  • Frente (Front): El primer elemento de la cola.
  • Final (Rear): El último elemento de la cola.
  • Capacidad: El número máximo de elementos que la cola puede contener.
  • Tamaño: El número actual de elementos en la cola.

Ventajas de las Colas Circulares

  1. Uso Eficiente de Memoria: Las colas circulares permiten reutilizar el espacio de memoria que se libera cuando se eliminan elementos, evitando la necesidad de mover elementos.
  2. Implementación Simple: Facilita la implementación de buffers circulares y estructuras de datos que requieren un acceso cíclico.

Implementación de una Cola Circular

Estructura de Datos

Para implementar una cola circular, necesitamos un array para almacenar los elementos, y dos punteros o índices para rastrear el frente y el final de la cola.

class ColaCircular:
    def __init__(self, capacidad):
        self.capacidad = capacidad
        self.cola = [None] * capacidad
        self.frente = -1
        self.final = -1

Operaciones Básicas

1. Encolar (Insertar)

Para encolar un elemento en una cola circular:

  1. Verificar si la cola está llena.
  2. Si la cola está vacía, inicializar frente y final a 0.
  3. Si no, actualizar el índice final de manera circular.
  4. Insertar el nuevo elemento en la posición final.
def encolar(self, elemento):
    if (self.final + 1) % self.capacidad == self.frente:
        print("La cola está llena")
        return
    if self.frente == -1:
        self.frente = 0
    self.final = (self.final + 1) % self.capacidad
    self.cola[self.final] = elemento

2. Desencolar (Eliminar)

Para desencolar un elemento de una cola circular:

  1. Verificar si la cola está vacía.
  2. Guardar el elemento en la posición frente.
  3. Si frente y final son iguales, la cola está vacía después de la operación.
  4. Si no, actualizar el índice frente de manera circular.
def desencolar(self):
    if self.frente == -1:
        print("La cola está vacía")
        return None
    elemento = self.cola[self.frente]
    if self.frente == self.final:
        self.frente = -1
        self.final = -1
    else:
        self.frente = (self.frente + 1) % self.capacidad
    return elemento

3. Verificar si la Cola está Vacía

def esta_vacia(self):
    return self.frente == -1

4. Verificar si la Cola está Llena

def esta_llena(self):
    return (self.final + 1) % self.capacidad == self.frente

Ejemplo Completo

class ColaCircular:
    def __init__(self, capacidad):
        self.capacidad = capacidad
        self.cola = [None] * capacidad
        self.frente = -1
        self.final = -1

    def encolar(self, elemento):
        if (self.final + 1) % self.capacidad == self.frente:
            print("La cola está llena")
            return
        if self.frente == -1:
            self.frente = 0
        self.final = (self.final + 1) % self.capacidad
        self.cola[self.final] = elemento

    def desencolar(self):
        if self.frente == -1:
            print("La cola está vacía")
            return None
        elemento = self.cola[self.frente]
        if self.frente == self.final:
            self.frente = -1
            self.final = -1
        else:
            self.frente = (self.frente + 1) % self.capacidad
        return elemento

    def esta_vacia(self):
        return self.frente == -1

    def esta_llena(self):
        return (self.final + 1) % self.capacidad == self.frente

# Ejemplo de uso
cola = ColaCircular(5)
cola.encolar(1)
cola.encolar(2)
cola.encolar(3)
print(cola.desencolar())  # Salida: 1
cola.encolar(4)
cola.encolar(5)
cola.encolar(6)  # La cola está llena
print(cola.desencolar())  # Salida: 2

Ejercicios Prácticos

Ejercicio 1: Implementar una Cola Circular

Implementa una cola circular con una capacidad dada y realiza las siguientes operaciones:

  1. Encolar los números del 1 al 5.
  2. Desencolar dos elementos.
  3. Encolar los números 6 y 7.
  4. Desencolar todos los elementos restantes.

Solución

class ColaCircular:
    def __init__(self, capacidad):
        self.capacidad = capacidad
        self.cola = [None] * capacidad
        self.frente = -1
        self.final = -1

    def encolar(self, elemento):
        if (self.final + 1) % self.capacidad == self.frente:
            print("La cola está llena")
            return
        if self.frente == -1:
            self.frente = 0
        self.final = (self.final + 1) % self.capacidad
        self.cola[self.final] = elemento

    def desencolar(self):
        if self.frente == -1:
            print("La cola está vacía")
            return None
        elemento = self.cola[self.frente]
        if self.frente == self.final:
            self.frente = -1
            self.final = -1
        else:
            self.frente = (self.frente + 1) % self.capacidad
        return elemento

    def esta_vacia(self):
        return self.frente == -1

    def esta_llena(self):
        return (self.final + 1) % self.capacidad == self.frente

# Ejemplo de uso
cola = ColaCircular(5)
for i in range(1, 6):
    cola.encolar(i)
print(cola.desencolar())  # Salida: 1
print(cola.desencolar())  # Salida: 2
cola.encolar(6)
cola.encolar(7)
while not cola.esta_vacia():
    print(cola.desencolar())

Ejercicio 2: Verificar el Estado de la Cola

Implementa métodos adicionales para verificar el estado de la cola (vacía o llena) y prueba estos métodos con diferentes operaciones de encolado y desencolado.

Solución

# Métodos ya implementados en la clase ColaCircular

# Ejemplo de uso
cola = ColaCircular(3)
print(cola.esta_vacia())  # Salida: True
cola.encolar(1)
cola.encolar(2)
print(cola.esta_llena())  # Salida: False
cola.encolar(3)
print(cola.esta_llena())  # Salida: True
cola.desencolar()
print(cola.esta_llena())  # Salida: False

Conclusión

Las colas circulares son una estructura de datos eficiente para gestionar elementos en un buffer circular. Su implementación y uso son esenciales en aplicaciones que requieren un manejo cíclico de datos. En este módulo, hemos cubierto la teoría, la implementación y algunos ejercicios prácticos para reforzar el aprendizaje.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2024. Todos los derechos reservados