El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Exercicis amb Cues

Següent ►
►

En aquesta secció, posarem en pràctica els conceptes apresos sobre les cues. Els exercicis estan dissenyats per reforçar la comprensió de les operacions bàsiques, les cues circulars i les cues de prioritat. Cada exercici inclou una explicació detallada i la seva solució.

Exercici 1: Implementació Bàsica d'una Cua

Descripció: Implementa una cua bàsica utilitzant una llista en Python. La cua ha de suportar les operacions d'enqueue (afegir un element) i dequeue (eliminar un element).

Requisits:

  1. Crear una classe Cua.
  2. Implementar els mètodes enqueue i dequeue.
  3. Afegir un mètode is_empty per comprovar si la cua està buida.

Solució:

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

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

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

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)
        else:
            raise IndexError("La cua està buida")

# Exemple d'ús
cua = Cua()
cua.enqueue(1)
cua.enqueue(2)
cua.enqueue(3)
print(cua.dequeue())  # Sortida: 1
print(cua.dequeue())  # Sortida: 2
print(cua.is_empty())  # Sortida: False
print(cua.dequeue())  # Sortida: 3
print(cua.is_empty())  # Sortida: True

Explicació:

  • La classe Cua utilitza una llista per emmagatzemar els elements.
  • enqueue afegeix un element al final de la llista.
  • dequeue elimina i retorna el primer element de la llista.
  • is_empty comprova si la llista està buida.

Exercici 2: Cua Circular

Descripció: Implementa una cua circular amb una capacitat fixa. La cua ha de suportar les operacions d'enqueue i dequeue, i ha de gestionar correctament el desbordament i el subdesbordament.

Requisits:

  1. Crear una classe CuaCircular amb una capacitat fixa.
  2. Implementar els mètodes enqueue i dequeue.
  3. Afegir un mètode is_full per comprovar si la cua està plena.

Solució:

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

    def is_empty(self):
        return self.size == 0

    def is_full(self):
        return self.size == self.capacitat

    def enqueue(self, item):
        if self.is_full():
            raise OverflowError("La cua està plena")
        self.rear = (self.rear + 1) % self.capacitat
        self.items[self.rear] = item
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("La cua està buida")
        item = self.items[self.front]
        self.items[self.front] = None
        self.front = (self.front + 1) % self.capacitat
        self.size -= 1
        return item

# Exemple d'ús
cua = CuaCircular(3)
cua.enqueue(1)
cua.enqueue(2)
cua.enqueue(3)
print(cua.dequeue())  # Sortida: 1
cua.enqueue(4)
print(cua.dequeue())  # Sortida: 2
print(cua.dequeue())  # Sortida: 3
print(cua.dequeue())  # Sortida: 4

Explicació:

  • La classe CuaCircular utilitza una llista de mida fixa per emmagatzemar els elements.
  • enqueue afegeix un element a la posició rear i actualitza la posició de manera circular.
  • dequeue elimina i retorna l'element a la posició front i actualitza la posició de manera circular.
  • is_full comprova si la cua està plena.

Exercici 3: Cua de Prioritat

Descripció: Implementa una cua de prioritat on cada element té una prioritat associada. Els elements amb prioritat més alta es processen primer.

Requisits:

  1. Crear una classe CuaDePrioritat.
  2. Implementar els mètodes enqueue i dequeue.
  3. Els elements s'han d'emmagatzemar en una llista de tuples (prioritat, element).

Solució:

import heapq

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

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

    def enqueue(self, item, prioritat):
        heapq.heappush(self.items, (prioritat, item))

    def dequeue(self):
        if self.is_empty():
            raise IndexError("La cua està buida")
        return heapq.heappop(self.items)[1]

# Exemple d'ús
cua = CuaDePrioritat()
cua.enqueue("tarea1", 2)
cua.enqueue("tarea2", 1)
cua.enqueue("tarea3", 3)
print(cua.dequeue())  # Sortida: "tarea2"
print(cua.dequeue())  # Sortida: "tarea1"
print(cua.dequeue())  # Sortida: "tarea3"

Explicació:

  • La classe CuaDePrioritat utilitza un heap per emmagatzemar els elements amb les seves prioritats.
  • enqueue afegeix un element al heap amb la seva prioritat.
  • dequeue elimina i retorna l'element amb la prioritat més alta (menor valor de prioritat).

Conclusió

En aquesta secció, hem treballat amb diferents tipus de cues: cues bàsiques, cues circulars i cues de prioritat. Aquests exercicis han de proporcionar una comprensió sòlida de com implementar i utilitzar cues en diferents contextos. Practicar amb aquests exercicis ajudarà a consolidar els coneixements i a preparar-se per a situacions reals en la programació.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats