Introducció a les Cues Circulars

Les cues circulars són una variació de les cues lineals en les quals l'últim element està connectat al primer, formant un cercle. Aquesta estructura permet una utilització més eficient de la memòria, ja que es pot reutilitzar l'espai alliberat pels elements que es treuen de la cua.

Característiques de les Cues Circulars

Capacitat fixa: Les cues circulars tenen una mida fixa, definida en el moment de la seva creació.
Reutilització d'espai: Quan la cua arriba al final de l'array, el següent element s'insereix al principi de l'array si hi ha espai disponible.
Dos punters: Utilitzen dos punters, front i rear, per mantenir el seguiment dels elements de la cua.

Operacions Bàsiques amb Cues Circulars

Inserció (Enqueue)

L'operació d'inserció afegeix un element al final de la cua. Si la cua està plena, no es pot afegir cap element més.

Extracció (Dequeue)

L'operació d'extracció elimina l'element del principi de la cua. Si la cua està buida, no es pot eliminar cap element.

Comprovar si la Cua està Plena

Es pot comprovar si la cua està plena comparant els punters front i rear.

Comprovar si la Cua està Buida

Es pot comprovar si la cua està buida comparant els punters front i rear.

Implementació de Cues Circulars en Python

A continuació es mostra una implementació bàsica d'una cua circular en Python:

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

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

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

    def enqueue(self, element):
        if self.is_full():
            print("La cua està plena")
            return
        if self.is_empty():
            self.front = 0
        self.rear = (self.rear + 1) % self.capacitat
        self.cua[self.rear] = element

    def dequeue(self):
        if self.is_empty():
            print("La cua està buida")
            return None
        element = self.cua[self.front]
        if self.front == self.rear:
            self.front = -1
            self.rear = -1
        else:
            self.front = (self.front + 1) % self.capacitat
        return element

    def display(self):
        if self.is_empty():
            print("La cua està buida")
            return
        index = self.front
        while True:
            print(self.cua[index], end=" ")
            if index == self.rear:
                break
            index = (index + 1) % self.capacitat
        print()

# Exemple d'ús
cua = CuaCircular(5)
cua.enqueue(10)
cua.enqueue(20)
cua.enqueue(30)
cua.enqueue(40)
cua.enqueue(50)
cua.display()
print("Element eliminat:", cua.dequeue())
cua.display()
cua.enqueue(60)
cua.display()

Explicació del Codi

Inicialització: La classe CuaCircular inicialitza la cua amb una capacitat fixa i dos punters (front i rear).
is_full: Comprova si la cua està plena.
is_empty: Comprova si la cua està buida.
enqueue: Afegeix un element a la cua. Si la cua està plena, mostra un missatge d'error.
dequeue: Elimina un element de la cua. Si la cua està buida, mostra un missatge d'error.
display: Mostra els elements de la cua.

Exercicis Pràctics

Exercici 1: Implementar una Cua Circular amb Capacitat Dinàmica

Modifica la implementació anterior per permetre que la capacitat de la cua s'ajusti dinàmicament quan la cua està plena.

Exercici 2: Aplicació de Cues Circulars

Implementa una cua circular per gestionar les sol·licituds d'impressió en una impressora compartida. Cada sol·licitud d'impressió té un identificador únic i una prioritat.

Solucions

Solució a l'Exercici 1

class CuaCircularDinamica:
    def __init__(self, capacitat):
        self.capacitat = capacitat
        self.cua = [None] * capacitat
        self.front = -1
        self.rear = -1

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

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

    def resize(self):
        nova_capacitat = self.capacitat * 2
        nova_cua = [None] * nova_capacitat
        index = 0
        i = self.front
        while True:
            nova_cua[index] = self.cua[i]
            index += 1
            if i == self.rear:
                break
            i = (i + 1) % self.capacitat
        self.front = 0
        self.rear = index - 1
        self.capacitat = nova_capacitat
        self.cua = nova_cua

    def enqueue(self, element):
        if self.is_full():
            self.resize()
        if self.is_empty():
            self.front = 0
        self.rear = (self.rear + 1) % self.capacitat
        self.cua[self.rear] = element

    def dequeue(self):
        if self.is_empty():
            print("La cua està buida")
            return None
        element = self.cua[self.front]
        if self.front == self.rear:
            self.front = -1
            self.rear = -1
        else:
            self.front = (self.front + 1) % self.capacitat
        return element

    def display(self):
        if self.is_empty():
            print("La cua està buida")
            return
        index = self.front
        while True:
            print(self.cua[index], end=" ")
            if index == self.rear:
                break
            index = (index + 1) % self.capacitat
        print()

# Exemple d'ús
cua = CuaCircularDinamica(5)
cua.enqueue(10)
cua.enqueue(20)
cua.enqueue(30)
cua.enqueue(40)
cua.enqueue(50)
cua.display()
print("Element eliminat:", cua.dequeue())
cua.display()
cua.enqueue(60)
cua.display()

Resum

En aquesta secció, hem après sobre les cues circulars, les seves característiques i operacions bàsiques, i hem implementat una cua circular en Python. També hem proporcionat exercicis pràctics per reforçar els conceptes apresos. Les cues circulars són una eina poderosa per gestionar coles de manera eficient, especialment en sistemes amb recursos limitats.

Cues Circulars

Introducció a les Cues Circulars

Característiques de les Cues Circulars

Operacions Bàsiques amb Cues Circulars

Inserció (Enqueue)

Extracció (Dequeue)

Comprovar si la Cua està Plena

Comprovar si la Cua està Buida

Implementació de Cues Circulars en Python

Explicació del Codi

Exercicis Pràctics

Exercici 1: Implementar una Cua Circular amb Capacitat Dinàmica

Exercici 2: Aplicació de Cues Circulars

Solucions

Solució a l'Exercici 1

Resum

Curs d'Estructures de Dades

Mòdul 1: Introducció a les Estructures de Dades

Mòdul 2: Llistes

Mòdul 3: Piles

Mòdul 4: Cues

Mòdul 5: Arbres

Mòdul 6: Grafs

Mòdul 7: Conclusions i Recursos Addicionals