Què és una Cua?
Una cua és una estructura de dades lineal que segueix el principi FIFO (First In, First Out), és a dir, el primer element que entra és el primer que surt. Les cues són molt útils en situacions on l'ordre d'arribada dels elements és important, com en la gestió de tasques o en la transmissió de dades.
Característiques Principals de les Cues
- FIFO (First In, First Out): El primer element afegit a la cua serà el primer a ser eliminat.
- Operacions Bàsiques:
- Enqueue: Afegir un element al final de la cua.
- Dequeue: Eliminar un element del principi de la cua.
- Front: Obtenir el primer element de la cua sense eliminar-lo.
- Rear: Obtenir l'últim element de la cua sense eliminar-lo.
- Aplicacions:
- Gestió de tasques en sistemes operatius.
- Gestió de processos en sistemes de xarxes.
- Implementació de buffers en sistemes de transmissió de dades.
Operacions Bàsiques amb Cues
Enqueue (Afegir un Element)
L'operació d'enqueue afegeix un element al final de la cua. Aquesta operació és generalment O(1), ja que només implica afegir un element al final de la llista.
class Cua:
def __init__(self):
self.elements = []
def enqueue(self, element):
self.elements.append(element)
print(f"Element {element} afegit a la cua.")Dequeue (Eliminar un Element)
L'operació de dequeue elimina el primer element de la cua. Aquesta operació també és generalment O(1), ja que només implica eliminar el primer element de la llista.
class Cua:
def __init__(self):
self.elements = []
def enqueue(self, element):
self.elements.append(element)
print(f"Element {element} afegit a la cua.")
def dequeue(self):
if not self.is_empty():
element = self.elements.pop(0)
print(f"Element {element} eliminat de la cua.")
return element
else:
print("La cua està buida.")
return NoneFront (Obtenir el Primer Element)
L'operació de front retorna el primer element de la cua sense eliminar-lo. Aquesta operació és O(1).
class Cua:
def __init__(self):
self.elements = []
def enqueue(self, element):
self.elements.append(element)
print(f"Element {element} afegit a la cua.")
def dequeue(self):
if not self.is_empty():
element = self.elements.pop(0)
print(f"Element {element} eliminat de la cua.")
return element
else:
print("La cua està buida.")
return None
def front(self):
if not self.is_empty():
return self.elements[0]
else:
print("La cua està buida.")
return NoneRear (Obtenir l'Últim Element)
L'operació de rear retorna l'últim element de la cua sense eliminar-lo. Aquesta operació és O(1).
class Cua:
def __init__(self):
self.elements = []
def enqueue(self, element):
self.elements.append(element)
print(f"Element {element} afegit a la cua.")
def dequeue(self):
if not self.is_empty():
element = self.elements.pop(0)
print(f"Element {element} eliminat de la cua.")
return element
else:
print("La cua està buida.")
return None
def front(self):
if not self.is_empty():
return self.elements[0]
else:
print("La cua està buida.")
return None
def rear(self):
if not self.is_empty():
return self.elements[-1]
else:
print("La cua està buida.")
return NoneComprovar si la Cua està Buida
És important tenir una funció per comprovar si la cua està buida abans de realitzar operacions com dequeue, front o rear.
class Cua:
def __init__(self):
self.elements = []
def enqueue(self, element):
self.elements.append(element)
print(f"Element {element} afegit a la cua.")
def dequeue(self):
if not self.is_empty():
element = self.elements.pop(0)
print(f"Element {element} eliminat de la cua.")
return element
else:
print("La cua està buida.")
return None
def front(self):
if not self.is_empty():
return self.elements[0]
else:
print("La cua està buida.")
return None
def rear(self):
if not self.is_empty():
return self.elements[-1]
else:
print("La cua està buida.")
return None
def is_empty(self):
return len(self.elements) == 0Exemple Pràctic
A continuació, es mostra un exemple pràctic d'ús de la classe Cua:
# Crear una cua
cua = Cua()
# Afegir elements a la cua
cua.enqueue(10)
cua.enqueue(20)
cua.enqueue(30)
# Obtenir el primer element
print(f"Primer element: {cua.front()}") # Output: Primer element: 10
# Obtenir l'últim element
print(f"Últim element: {cua.rear()}") # Output: Últim element: 30
# Eliminar elements de la cua
cua.dequeue() # Output: Element 10 eliminat de la cua.
cua.dequeue() # Output: Element 20 eliminat de la cua.
# Comprovar si la cua està buida
print(f"La cua està buida? {cua.is_empty()}") # Output: La cua està buida? False
# Eliminar l'últim element
cua.dequeue() # Output: Element 30 eliminat de la cua.
# Comprovar si la cua està buida
print(f"La cua està buida? {cua.is_empty()}") # Output: La cua està buida? TrueConclusió
Les cues són una estructura de dades fonamental en la programació, especialment útils en situacions on l'ordre d'arribada dels elements és crucial. Hem vist les operacions bàsiques amb cues i com implementar-les en Python. En els següents temes, explorarem variacions de les cues com les cues circulars i les cues de prioritat, així com les seves aplicacions pràctiques.
Curs d'Estructures de Dades
Mòdul 1: Introducció a les Estructures de Dades
- Què són les Estructures de Dades?
- Importància de les Estructures de Dades en la Programació
- Tipus d'Estructures de Dades
Mòdul 2: Llistes
- Introducció a les Llistes
- Llistes Enllaçades
- Llistes Doblement Enllaçades
- Llistes Circulars
- Exercicis amb Llistes
Mòdul 3: Piles
- Introducció a les Piles
- Operacions Bàsiques amb Piles
- Implementació de Piles
- Aplicacions de les Piles
- Exercicis amb Piles
Mòdul 4: Cues
- Introducció a les Cues
- Operacions Bàsiques amb Cues
- Cues Circulars
- Cues de Prioritat
- Exercicis amb Cues
Mòdul 5: Arbres
- Introducció als Arbres
- Arbres Binàries
- Arbres Binàries de Cerca
- Arbres AVL
- Arbres B
- Exercicis amb Arbres
Mòdul 6: Grafs
- Introducció als Grafs
- Representació de Grafs
- Algoritmes de Cerca en Grafs
- Algoritmes de Camins Mínims
- Aplicacions dels Grafs
- Exercicis amb Grafs