El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

A la lliçó anterior vam definir el contracte del TAD cua; ara toca complir-lo. Veurem les tres operacions fonamentals —encuar, desencuar i front— pas a pas, amb traces de l'estat intern, i ens enfrontarem al problema central de la lliçó: la implementació "òbvia" sobre una list de Python trenca la promesa de cost O(1) per culpa del pop(0) que ja vam desemmascarar al mòdul 1. La solució elegant la tenim des del mòdul 2: la LlistaEnllacada, que insereix i elimina en O(1) just pels extrems que la cua necessita. Tancarem amb una construcció sorprenent —una cua feta amb dues piles— i amb la primera peça de TaskFlow d'aquest mòdul: la CuaNotificacions.

Contingut

Les tres operacions, pas a pas
Primer intent: cua sobre list (i per què falla)
La implementació correcta: Cua sobre LlistaEnllacada
Curiositat formativa: CuaAmbDuesPiles
Taula de costos comparada
TaskFlow: la classe CuaNotificacions

Les tres operacions, pas a pas

Abans d'escriure codi, tracem a mà una seqüència d'operacions. Representem la cua amb el front a l'esquerra i el final a la dreta:

Pas	Operació	Estat de la cua (front → final)	Retorna
1	`encuar("N1")`	`N1`	—
2	`encuar("N2")`	`N1, N2`	—
3	`encuar("N3")`	`N1, N2, N3`	—
4	`front()`	`N1, N2, N3` (sense canvis)	`"N1"`
5	`desencuar()`	`N2, N3`	`"N1"`
6	`desencuar()`	`N3`	`"N2"`
7	`encuar("N4")`	`N3, N4`	—
8	`desencuar()`	`N4`	`"N3"`

Tres invariants que es compleixen en tota la traça i que ha de garantir qualsevol implementació:

desencuar retorna els elements exactament en l'ordre en què es van encuar (N1, N2, N3...), encara que entremig hi hagi noves insercions (pas 7).
front és una consulta pura: el pas 4 no altera l'estat.
Els dos extrems treballen alhora: el final creix, el front minva. Aquest és el detall que complicarà la implementació.

sequenceDiagram
    participant P as Productor
    participant C as Cua
    participant W as Consumidor
    P->>C: encuar(N1)
    P->>C: encuar(N2)
    W->>C: desencuar()
    C-->>W: N1
    P->>C: encuar(N3)
    W->>C: desencuar()
    C-->>W: N2
    Note over C: L'ordre de sortida = ordre d'arribada,<br/>encara que productor i consumidor s'intercalin

Primer intent: cua sobre `list` (i per què falla)

La temptació natural és calcar el que vam fer amb la Pila del mòdul 3: embolcallar una list. Encuem amb append (pel final) i desencuem amb pop(0) (pel front):

class CuaLenta:
    """Cua sobre list. Funcionalment correcta, pero amb una trampa de cost."""

    def __init__(self):
        self._elements = []

    def encuar(self, element):
        self._elements.append(element)        # O(1) amortitzat: bé

    def desencuar(self):
        if self.esta_buida():
            raise IndexError("desencuar sobre una cua buida")
        return self._elements.pop(0)          # O(n): AQUÍ hi ha el problema

    def front(self):
        if self.esta_buida():
            raise IndexError("front sobre una cua buida")
        return self._elements[0]

    def esta_buida(self):
        return len(self._elements) == 0

    def mida(self):
        return len(self._elements)

Aquesta classe compleix el contracte funcional (passa qualsevol prova d'ordre FIFO), però incompleix la promesa de cost. Al mòdul 1 vam demostrar amb timeit que pop(0) és O(n): en treure el primer element, Python desplaça en memòria tots els altres una posició cap a l'esquerra, perquè una list és un array dinàmic i ha de mantenir els seus elements contigus. Pots repetir aquí l'experiment del mòdul 1:

import timeit

def buidar(cua_cls, n):
    cua = cua_cls()
    for i in range(n):
        cua.encuar(i)
    while not cua.esta_buida():
        cua.desencuar()

# Duplicar n hauria de duplicar el temps si desencuar fos O(1)...
print(timeit.timeit(lambda: buidar(CuaLenta, 10_000), number=1))
print(timeit.timeit(lambda: buidar(CuaLenta, 20_000), number=1))
# ...pero es multiplica per ~4: el buidatge complet es O(n^2)

I al revés? Si encuem amb insert(0, ...) i desencuem amb pop(), només movem el problema d'extrem: insert(0) també és O(n), com vam veure al mòdul 1. Amb un array, un dels dos extrems sempre surt car. La cua necessita els dos extrems barats, així que la list a pèl no és l'eina adequada.

La implementació correcta: `Cua` sobre `LlistaEnllacada`

Aquí és on cobra sentit la feina del mòdul 2. La nostra LlistaEnllacada manté referències al cap i a la cua (l'últim node), i per això pot inserir pel final i eliminar pel principi en O(1): no cal desplaçar res, només reajustar enllaços. Recordem la part que necessitem:

class Node:
    def __init__(self, dada):
        self.dada = dada
        self.seguent = None


class LlistaEnllacada:
    """Versio reduida de la classe del modul 2: nomes el que la cua necessita."""

    def __init__(self):
        self.cap = None
        self.cua = None
        self.mida = 0

    def inserir_al_final(self, dada):         # O(1) gracies a self.cua
        nou = Node(dada)
        if self.cua is None:                  # llista buida
            self.cap = nou
            self.cua = nou
        else:
            self.cua.seguent = nou            # l'ultim apunta al nou
            self.cua = nou                    # el nou passa a ser l'ultim
        self.mida += 1

    def eliminar_del_principi(self):          # O(1): nomes es toca el cap
        if self.cap is None:
            raise IndexError("eliminar d'una llista buida")
        dada = self.cap.dada
        self.cap = self.cap.seguent           # el cap avanca un node
        if self.cap is None:                  # si era l'unic node...
            self.cua = None                   # ...la cua tambe queda buida
        self.mida -= 1
        return dada

La decisió clau de disseny és per quin extrem entra i per quin extrem surt:

Encuar pel final (inserir_al_final): O(1) perquè guardem la referència self.cua.
Desencuar pel cap (eliminar_del_principi): O(1) perquè n'hi ha prou de fer avançar self.cap.

Podríem fer-ho al revés (encuar pel cap, desencuar per la cua)? Encuar continuaria sent O(1), però desencuar per la cua seria O(n): per eliminar l'últim node necessitem el penúltim, i en una llista enllaçada simple només s'hi arriba recorrent des del cap. L'orientació correcta no és opcional: és l'única que dona O(1) en totes dues operacions.

Amb la llista a punt, la classe Cua és una capa fina que restringeix l'accés al contracte FIFO (igual que la Pila restringia la list al contracte LIFO):

class Cua:
    """Cua FIFO amb encuar i desencuar en O(1), sobre LlistaEnllacada."""

    def __init__(self):
        self._elements = LlistaEnllacada()

    def encuar(self, element):
        self._elements.inserir_al_final(element)

    def desencuar(self):
        if self.esta_buida():
            raise IndexError("desencuar sobre una cua buida")
        return self._elements.eliminar_del_principi()

    def front(self):
        if self.esta_buida():
            raise IndexError("front sobre una cua buida")
        return self._elements.cap.dada

    def esta_buida(self):
        return self._elements.mida == 0

    def mida(self):
        return self._elements.mida

Com que Cua i CuaLenta comparteixen contracte, pots verificar que es comporten igual amb la mateixa tècnica del provar_contracte del mòdul 3: executar la mateixa seqüència d'operacions sobre totes dues i comparar resultats. Només canvia el cost, no el comportament — aquesta és l'essència del TAD.

Curiositat formativa: `CuaAmbDuesPiles`

Hi ha una construcció clàssica que sembla una endevinalla: implementar una cua usant només dues piles. Val la pena veure-la perquè ensenya un concepte nou, el cost amortitzat, i perquè apareix sovint en entrevistes tècniques.

La idea: una pila inverteix l'ordre; dues inversions el restauren.

entrada: pila on apilem tot el que s'encua.
sortida: pila d'on desapilem. Quan és buida, aboquem tota l'entrada a sortida, cosa que inverteix l'ordre i deixa l'element més antic al cim.

class CuaAmbDuesPiles:
    def __init__(self):
        self._entrada = Pila()    # la Pila del modul 3 (apilar/desapilar/esta_buida)
        self._sortida = Pila()

    def encuar(self, element):
        self._entrada.apilar(element)             # O(1) sempre

    def desencuar(self):
        if self._sortida.esta_buida():
            # Abocament: inverteix l'ordre d''entrada' dins de 'sortida'
            while not self._entrada.esta_buida():
                self._sortida.apilar(self._entrada.desapilar())
        if self._sortida.esta_buida():
            raise IndexError("desencuar sobre una cua buida")
        return self._sortida.desapilar()

    def esta_buida(self):
        return self._entrada.esta_buida() and self._sortida.esta_buida()

    def mida(self):
        return self._entrada.mida() + self._sortida.mida()

Traça: encuem A, B, C → entrada = [A, B, C] (C al cim). Primer desencuar: abocament → sortida = [C, B, A] (A al cim) → retorna A. Correcte: A va ser el primer d'entrar. Els següents desencuar retornen B i C sense abocar res, perquè ja estan ordenats a sortida.

I el cost? Un desencuar concret pot costar O(n) (el que provoca l'abocament), però cada element s'apila i es desapila com a màxim dues vegades en tota la seva vida (una a cada pila). Repartit entre n operacions, el cost mitjà per operació és O(1): es diu que és O(1) amortitzat. És la mateixa idea per la qual l'append de list és O(1) amortitzat malgrat els redimensionaments ocasionals (mòdul 1). No usarem aquesta classe a TaskFlow —la versió enllaçada és més simple i O(1) sempre—, però el concepte de cost amortitzat t'acompanyarà tota la carrera.

Taula de costos comparada

Operació	`CuaLenta` (`list`)	`Cua` (`LlistaEnllacada`)	`CuaAmbDuesPiles`
`encuar`	O(1) amortitzat	O(1)	O(1)
`desencuar`	O(n)	O(1)	O(1) amortitzat
`front`	O(1)	O(1)	O(1) amortitzat
`esta_buida` / `mida`	O(1)	O(1)	O(1)
Memòria extra per element	Cap	Un node (referència extra)	Cap

La llista enllaçada paga un petit sobrecost de memòria (cada dada viatja dins d'un Node), a canvi de garanties de temps constants. Avançament honest: en Python professional, la implementació de referència per a cues és collections.deque, que ja vam presentar al mòdul 2 com a "llista doblement enllaçada per blocs" i que estudiarem a fons a la lliçó 04-05. Aquí construïm la nostra perquè entendre per què és O(1) val més que usar-la a cegues.

TaskFlow: la classe `CuaNotificacions`

Apliquem la Cua al cas que va motivar el mòdul: les notificacions pendents d'enviar. Cada notificació referencia la tasca que la va provocar (el nostre dict habitual amb id/titol/prioritat/estat):

class CuaNotificacions:
    """Gestiona l'enviament de notificacions de TaskFlow per ordre d'arribada."""

    def __init__(self):
        self._pendents = Cua()

    def notificar(self, tasca, missatge):
        """El productor: l'app encua a l'instant (O(1)) i segueix treballant."""
        notificacio = {
            "tasca_id": tasca["id"],
            "destinatari": tasca.get("assignada_a", "sense assignar"),
            "missatge": missatge,
        }
        self._pendents.encuar(notificacio)

    def pendents(self):
        return self._pendents.mida()

    def processar(self, maxim=None):
        """El consumidor: envia per ordre d'arribada, fins a 'maxim' enviaments."""
        enviades = 0
        while not self._pendents.esta_buida():
            if maxim is not None and enviades == maxim:
                break                              # respecta el lot demanat
            notif = self._pendents.desencuar()
            print(f"[enviament] a {notif['destinatari']}: "
                  f"{notif['missatge']} (tasca {notif['tasca_id']})")
            enviades += 1
        return enviades


# --- Us ---
tasca_a = {"id": 7, "titol": "Migrar la base de dades", "prioritat": 1,
           "estat": "en curs", "assignada_a": "anna"}
tasca_b = {"id": 8, "titol": "Redactar el changelog", "prioritat": 3,
           "estat": "pendent", "assignada_a": "bruno"}

bustia = CuaNotificacions()
bustia.notificar(tasca_a, "Se t'ha assignat la tasca")
bustia.notificar(tasca_b, "Se t'ha assignat la tasca")
bustia.notificar(tasca_a, "La tasca ha passat a 'en curs'")

print(bustia.pendents())   # 3
bustia.processar(maxim=2)  # envia les DUES mes antigues, en el seu ordre
bustia.processar()         # envia la resta

Detalls de disseny que convé subratllar:

El paràmetre maxim permet processar per lots: en una aplicació real, el consumidor s'executa periòdicament i envia unes quantes notificacions cada vegada, sense bloquejar res. La cua conserva la resta, en ordre, per al lot següent.
L'Anna rep les seves dues notificacions en l'ordre correcte (assignació abans que canvi d'estat): aquesta coherència la regala el FIFO.
La prioritat de la tasca viatja dins el dict però no s'usa per ordenar: en un FIFO no s'ha d'usar. La safata on la prioritat mana arriba a la lliçó 04-04.

Errors Comuns i Consells

Usar list.pop(0) en producció "perquè funciona": funciona fins que la cua creix. Un buidatge complet passa de lineal a quadràtic, i són els errors que no apareixen a les proves (amb 10 elements) però tomben el sistema amb 100.000. Mesura amb timeit davant del dubte, com al mòdul 1.
Oblidar actualitzar self.cua en buidar la llista enllaçada: a eliminar_del_principi, si s'elimina l'únic node, self.cua s'ha de posar a None. Si ho oblides, el següent inserir_al_final encadenarà el node nou a un node fantasma ja eliminat. És l'error més freqüent en implementar cues enllaçades.
Desencuar per l'extrem equivocat: encuar i desencuar pel cap converteix la teva "cua" en una pila. Escriu una prova que encui 1, 2, 3 i comprovi que surten 1, 2, 3.
A CuaAmbDuesPiles, abocar quan sortida no és buida: barrejaries els ordres i trencaries el FIFO. L'abocament només procedeix amb sortida buida; és un invariant, protegeix-lo amb la condició i, si vols, amb una asserció.
Consell: quan embolcallis una estructura (com Cua embolcalla LlistaEnllacada), exposa només el contracte. Si publiques cap o inserir_al_principi, algun codi client acabarà usant-los i la teva cua deixarà de ser una cua.

Exercicis

Exercici 1: traça sobre la llista enllaçada

Parteix d'una Cua buida i executa: encuar(10), encuar(20), desencuar(), encuar(30), desencuar(), desencuar(). Dibuixa (o escriu) l'estat de cap, cua i mida de la LlistaEnllacada interna després de cada operació. Para una atenció especial al moment en què la cua queda buida.

Exercici 2: `buidar` i `en_espera` sense trencar el contracte

Afegeix a la classe Cua dos mètodes: buidar() (deixa la cua sense elements, en O(1)) i en_espera() (retorna una list de Python amb els elements en ordre de front a final, sense modificar la cua, en O(n)). Pista: per a en_espera hauràs de recórrer els nodes interns; fes-ho dins de la classe per no exposar els nodes a fora.

Exercici 3: la traça de les dues piles

Amb CuaAmbDuesPiles, executa: encuar(1), encuar(2), desencuar(), encuar(3), encuar(4), desencuar(), desencuar(), desencuar(). Indica, després de cada operació, el contingut d'entrada i sortida (de fons a cim) i quan es produeix cada abocament. Quantes vegades passa l'element 3 per una operació d'apilar/desapilar en total?

Solucions

Solució 1:

Operació	cap	cua	mida
(inicial)	`None`	`None`	0
`encuar(10)`	node(10)	node(10)	1
`encuar(20)`	node(10)	node(20)	2
`desencuar()` → 10	node(20)	node(20)	1
`encuar(30)`	node(20)	node(30)	2
`desencuar()` → 20	node(30)	node(30)	1
`desencuar()` → 30	`None`	`None`	0

El punt crític és l'última fila: en eliminar l'únic node, cap queda a None i també cua; si no, l'estructura queda corrupta.

Solució 2:

class Cua(Cua):  # ampliem la classe anterior
    def buidar(self):
        # N'hi ha prou de substituir la llista interna: els nodes antics
        # queden sense referencies i el recollidor de brossa els allibera.
        self._elements = LlistaEnllacada()

    def en_espera(self):
        resultat = []
        actual = self._elements.cap
        while actual is not None:      # recorregut O(n) classic del modul 2
            resultat.append(actual.dada)
            actual = actual.seguent
        return resultat                # copia: modificar-la no toca la cua

buidar és O(1) perquè no eliminem node a node: deixem anar la llista sencera. en_espera retorna una còpia, de manera que el client no pot alterar la cua a través d'ella.

Solució 3:

Operació	`entrada` (fons→cim)	`sortida` (fons→cim)	Retorna
`encuar(1)`	1	—	—
`encuar(2)`	1, 2	—	—
`desencuar()`	—	2, 1 → 2	1 (abocament núm. 1)
`encuar(3)`	3	2	—
`encuar(4)`	3, 4	2	—
`desencuar()`	3, 4	—	2 (sense abocament)
`desencuar()`	—	4, 3 → 4	3 (abocament núm. 2)
`desencuar()`	—	—	4

Hi ha dos abocaments (quan sortida es queda buida i es demana desencuar). L'element 3 participa en 4 operacions: apilar a entrada, desapilar d'entrada, apilar a sortida, desapilar de sortida. Cap element no supera aquest màxim de 2 apilats + 2 desapilats: per això el cost amortitzat és O(1).

Conclusió

Ja tenim una cua de debò: n'hem traçat les operacions, hem comprovat que la list a pèl condemna desencuar (o encuar) a O(n), i l'hem implementada correctament sobre la LlistaEnllacada del mòdul 2 —encuar per la cua, desencuar pel cap, tots dos O(1)—. De regal, la CuaAmbDuesPiles ens ha presentat el cost amortitzat, i la CuaNotificacions de TaskFlow ja processa avisos per ordre just d'arribada i per lots. Però la nostra cua creix sense límit, i hi ha contextos —buffers de xarxa, registres d'esdeveniments— on la memòria és fixa i el que és raonable és que el nou acabi ocupant el lloc del vell. Per a això cal fer que els índexs "facin la volta": és la cua circular, cosina de la LlistaCircular del mòdul 2, i protagonista de la propera lliçó.

Operacions Bàsiques amb Cues

Contingut

Les tres operacions, pas a pas

Primer intent: cua sobre `list` (i per què falla)

La implementació correcta: `Cua` sobre `LlistaEnllacada`

Curiositat formativa: `CuaAmbDuesPiles`

Taula de costos comparada

TaskFlow: la classe `CuaNotificacions`

Errors Comuns i Consells

Exercicis

Exercici 1: traça sobre la llista enllaçada

Exercici 2: `buidar` i `en_espera` sense trencar el contracte

Exercici 3: la traça de les dues piles

Solucions

Conclusió

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: Taules Hash i Diccionaris

Mòdul 6: Arbres

Mòdul 7: Grafs

Mòdul 8: Conclusions i Recursos Addicionals

Operacions Bàsiques amb Cues

Contingut

Les tres operacions, pas a pas

Primer intent: cua sobre list (i per què falla)

La implementació correcta: Cua sobre LlistaEnllacada

Curiositat formativa: CuaAmbDuesPiles

Taula de costos comparada

TaskFlow: la classe CuaNotificacions

Errors Comuns i Consells

Exercicis

Exercici 1: traça sobre la llista enllaçada

Exercici 2: buidar i en_espera sense trencar el contracte

Exercici 3: la traça de les dues piles

Solucions

Conclusió

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: Taules Hash i Diccionaris

Mòdul 6: Arbres

Mòdul 7: Grafs

Mòdul 8: Conclusions i Recursos Addicionals

Primer intent: cua sobre `list` (i per què falla)

La implementació correcta: `Cua` sobre `LlistaEnllacada`

Curiositat formativa: `CuaAmbDuesPiles`

TaskFlow: la classe `CuaNotificacions`

Exercici 2: `buidar` i `en_espera` sense trencar el contracte