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

Ejercicios con Colas

Siguiente ►
►

En esta sección, pondremos en práctica los conceptos aprendidos sobre colas mediante una serie de ejercicios. Cada ejercicio está diseñado para reforzar tu comprensión y habilidades en la implementación y manipulación de colas. Asegúrate de intentar resolver los ejercicios por tu cuenta antes de consultar las soluciones.

Ejercicio 1: Implementación Básica de una Cola

Descripción: Implementa una cola utilizando una lista en Python. La cola debe soportar las siguientes operaciones:

  • enqueue(item): Añadir un elemento al final de la cola.
  • dequeue(): Eliminar y devolver el elemento al frente de la cola.
  • is_empty(): Verificar si la cola está vacía.
  • size(): Devolver el número de elementos en la cola.

Código:

class Cola:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)
        else:
            return None

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

# Ejemplo de uso
cola = Cola()
cola.enqueue(1)
cola.enqueue(2)
cola.enqueue(3)
print(cola.dequeue())  # Salida: 1
print(cola.size())     # Salida: 2

Explicación:

  • __init__: Inicializa una lista vacía para almacenar los elementos de la cola.
  • enqueue: Añade un elemento al final de la lista.
  • dequeue: Elimina y devuelve el primer elemento de la lista (el frente de la cola).
  • is_empty: Devuelve True si la lista está vacía, de lo contrario False.
  • size: Devuelve el número de elementos en la lista.

Ejercicio 2: Cola Circular

Descripción: Implementa una cola circular utilizando una lista fija de tamaño n. La cola debe soportar las siguientes operaciones:

  • enqueue(item): Añadir un elemento al final de la cola.
  • dequeue(): Eliminar y devolver el elemento al frente de la cola.
  • is_empty(): Verificar si la cola está vacía.
  • is_full(): Verificar si la cola está llena.
  • size(): Devolver el número de elementos en la cola.

Código:

class ColaCircular:
    def __init__(self, n):
        self.size = n
        self.items = [None] * n
        self.front = -1
        self.rear = -1

    def enqueue(self, item):
        if self.is_full():
            print("La cola está llena")
            return
        if self.front == -1:
            self.front = 0
        self.rear = (self.rear + 1) % self.size
        self.items[self.rear] = item

    def dequeue(self):
        if self.is_empty():
            print("La cola está vacía")
            return None
        item = self.items[self.front]
        if self.front == self.rear:
            self.front = -1
            self.rear = -1
        else:
            self.front = (self.front + 1) % self.size
        return item

    def is_empty(self):
        return self.front == -1

    def is_full(self):
        return (self.rear + 1) % self.size == self.front

    def size(self):
        if self.is_empty():
            return 0
        elif self.rear >= self.front:
            return self.rear - self.front + 1
        else:
            return self.size - self.front + self.rear + 1

# Ejemplo de uso
cola_circular = ColaCircular(3)
cola_circular.enqueue(1)
cola_circular.enqueue(2)
cola_circular.enqueue(3)
print(cola_circular.dequeue())  # Salida: 1
cola_circular.enqueue(4)
print(cola_circular.dequeue())  # Salida: 2

Explicación:

  • __init__: Inicializa una lista fija de tamaño n y establece los índices front y rear en -1.
  • enqueue: Añade un elemento al final de la cola circular. Si la cola está llena, muestra un mensaje de error.
  • dequeue: Elimina y devuelve el primer elemento de la cola circular. Si la cola está vacía, muestra un mensaje de error.
  • is_empty: Devuelve True si la cola está vacía, de lo contrario False.
  • is_full: Devuelve True si la cola está llena, de lo contrario False.
  • size: Calcula y devuelve el número de elementos en la cola.

Ejercicio 3: Cola de Prioridad

Descripción: Implementa una cola de prioridad donde cada elemento tiene una prioridad asociada. La cola debe soportar las siguientes operaciones:

  • enqueue(item, priority): Añadir un elemento con una prioridad específica.
  • dequeue(): Eliminar y devolver el elemento con la mayor prioridad.
  • is_empty(): Verificar si la cola está vacía.
  • size(): Devolver el número de elementos en la cola.

Código:

import heapq

class ColaPrioridad:
    def __init__(self):
        self.heap = []

    def enqueue(self, item, priority):
        heapq.heappush(self.heap, (priority, item))

    def dequeue(self):
        if not self.is_empty():
            return heapq.heappop(self.heap)[1]
        else:
            return None

    def is_empty(self):
        return len(self.heap) == 0

    def size(self):
        return len(self.heap)

# Ejemplo de uso
cola_prioridad = ColaPrioridad()
cola_prioridad.enqueue("tarea1", 2)
cola_prioridad.enqueue("tarea2", 1)
cola_prioridad.enqueue("tarea3", 3)
print(cola_prioridad.dequeue())  # Salida: tarea2
print(cola_prioridad.size())     # Salida: 2

Explicación:

  • __init__: Inicializa una lista vacía para almacenar los elementos de la cola de prioridad.
  • enqueue: Añade un elemento a la cola con una prioridad específica utilizando heapq.heappush.
  • dequeue: Elimina y devuelve el elemento con la mayor prioridad utilizando heapq.heappop.
  • is_empty: Devuelve True si la lista está vacía, de lo contrario False.
  • size: Devuelve el número de elementos en la lista.

Retroalimentación sobre Errores Comunes

  1. Olvidar verificar si la cola está vacía antes de hacer dequeue:

    • Asegúrate de siempre verificar si la cola está vacía antes de intentar eliminar un elemento. Esto evitará errores y excepciones.

  2. Confundir los índices front y rear en colas circulares:

    • Mantén un seguimiento claro de los índices front y rear en colas circulares. Recuerda que rear se mueve hacia adelante al agregar elementos y front se mueve hacia adelante al eliminar elementos.

  3. No manejar correctamente las prioridades en colas de prioridad:

    • Asegúrate de utilizar una estructura de datos adecuada, como un heap, para manejar las prioridades de manera eficiente.

Conclusión

En esta sección, hemos practicado la implementación de diferentes tipos de colas: colas simples, colas circulares y colas de prioridad. Estos ejercicios te ayudarán a comprender mejor cómo funcionan las colas y cómo pueden ser utilizadas en diferentes contextos. Asegúrate de revisar y entender cada solución antes de pasar al siguiente módulo.

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