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

HOME

La Cua de la lliçó anterior creix sense límit: mentre hi hagi memòria, accepta elements. Però molts sistemes treballen amb memòria fixa: un buffer de xarxa, el buffer de teclat, el registre dels últims esdeveniments d'una aplicació. Per a aquests casos existeix una implementació clàssica i elegantíssima: la cua circular (o ring buffer), una cua FIFO muntada sobre un array de capacitat fixa els índexs del qual, en arribar al final, "fan la volta" i reutilitzen les caselles alliberades pel front. En aquesta lliçó construirem la classe CuaCircular amb aritmètica modular, resoldrem el trencaclosques de distingir "plena" de "buida", i l'aplicarem a TaskFlow: el registre dels últims N esdeveniments del sistema. També connectarem la idea amb una vella coneguda: la LlistaCircular del mòdul 2.

Contingut

El problema: una cua sobre array fix
La idea circular: aritmètica modular
El trencaclosques: plena o buida?
La classe CuaCircular
Traça visual de l'avanç modular
Ring buffers al món real i relació amb LlistaCircular
TaskFlow: RegistreEsdeveniments, els últims N esdeveniments

El problema: una cua sobre array fix

Suposem que només disposem d'un array de capacitat fixa, posem 5 caselles, i volem una cua FIFO a sobre. El primer intent ingenu: encuar fent avançar un índex final i desencuar fent avançar un índex front:

encuar(A), encuar(B), encuar(C):         desencuar() dues vegades:

índexs:   0    1    2    3    4          índexs:   0    1    2    3    4
        [ A ][ B ][ C ][   ][   ]                [ · ][ · ][ C ][   ][   ]
          ↑front         ↑final                              ↑front ↑final

Després de desencuar A i B, les caselles 0 i 1 queden lliures... però final continua avançant cap a la dreta. Quan final arribi a la casella 4, la cua semblarà "plena" amb dues caselles desaprofitades a l'esquerra. Les alternatives dolentes són dues:

Desplaçar els elements cap a l'esquerra a cada desencuament: això és exactament el pop(0) O(n) que fa dos mòduls que evitem.
Rebutjar insercions encara que hi hagi lloc: malbaratament inacceptable en un buffer.

La solució bona: que final, en passar-se de la vora dreta, continuï per la casella 0. L'array deixa de ser una tira i es converteix, conceptualment, en un anell.

La idea circular: aritmètica modular

Per "fer la volta" no cal màgia, n'hi ha prou amb l'operador mòdul %. Si la capacitat és c, l'índex següent a i és:

seguent = (i + 1) % c

Amb c = 5: després del 3 ve el 4, i després del 4 ve (4 + 1) % 5 = 0. El mòdul converteix la recta d'índexs en un cercle:

graph LR
    I0((0)) --> I1((1)) --> I2((2)) --> I3((3)) --> I4((4)) --> I0

Et sona? És la mateixa idea que la LlistaCircular del mòdul 2, on l'últim node apuntava al primer (ultim.seguent) i el RepartidorTasques girava indefinidament. Allà el cercle es construïa amb enllaços entre nodes; aquí es construeix amb aritmètica sobre índexs d'un array. Mateix concepte, implementació diferent — i aquesta versió, en ser un array contigu de mida fixa, és més compacta en memòria i més amiga de la memòria cau del processador; per això és l'escollida en drivers i sistemes encastats.

El trencaclosques: plena o buida?

Hi ha una subtilesa famosa. Si representem la cua només amb els índexs front i final, la condició front == final és ambigua: es dona tant quan la cua és buida com quan és plena (el final ha fet la volta completa i ha atrapat el front). Hi ha dues solucions clàssiques:

Estratègia	Com funciona	Cost
Comptador d'elements	Mantenir `mida`: buida si `mida == 0`, plena si `mida == capacitat`	Un enter extra; codi molt clar
Casella lliure (sacrificada)	Reservar sempre un forat: plena si `(final + 1) % c == front`	Es desaprofita una casella; només índexs

Nosaltres usarem el comptador, que a més ens dona mida() de franc (és al contracte). L'estratègia de la casella sacrificada la veuràs en codi C de baix nivell, on evitar un camp extra importa; convé reconèixer-la quan la llegeixis.

Amb comptador, ni tan sols necessitem emmagatzemar final: es dedueix de front i mida:

final = (front + mida) % capacitat   # casella on caura el PROXIM element

Menys estat per mantenir vol dir menys invariants per trencar: és un principi de disseny que ja vam aplicar a la LlistaCircular (només guardàvem self.ultim).

La classe `CuaCircular`

class CuaCircular:
    """Cua FIFO de capacitat fixa sobre un array, amb indexs modulars.

    Compleix el contracte de cua (encuar, desencuar, front, esta_buida,
    mida) i afegeix esta_plena() i capacitat(), propis de la mida fixa.
    """

    def __init__(self, capacitat):
        if capacitat <= 0:
            raise ValueError("la capacitat ha de ser positiva")
        self._dades = [None] * capacitat   # array fix: es crea d'una vegada
        self._capacitat = capacitat
        self._front = 0                    # index de l'element mes antic
        self._mida = 0                     # nombre d'elements ocupats

    def encuar(self, element):
        if self.esta_plena():
            raise OverflowError("encuar sobre una cua plena")
        final = (self._front + self._mida) % self._capacitat
        self._dades[final] = element       # escriu a la casella del final
        self._mida += 1

    def desencuar(self):
        if self.esta_buida():
            raise IndexError("desencuar sobre una cua buida")
        element = self._dades[self._front]
        self._dades[self._front] = None    # alliberar la referencia (higiene)
        self._front = (self._front + 1) % self._capacitat   # avanc modular
        self._mida -= 1
        return element

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

    def esta_buida(self):
        return self._mida == 0

    def esta_plena(self):
        return self._mida == self._capacitat

    def mida(self):
        return self._mida

    def capacitat(self):
        return self._capacitat

Punts que mereixen una explicació detallada:

Tot és O(1), sense lletra petita: encuar i desencuar fan una escriptura, una suma i un mòdul. No hi ha desplaçaments (el gran pecat de CuaLenta) ni nodes per crear (a diferència de la Cua enllaçada). Tampoc no hi ha redimensionaments: la memòria es reserva una única vegada a __init__.
self._dades[self._front] = None a desencuar: no és obligatori perquè funcioni, però si la casella reté la referència a l'objecte, Python no pot alliberar-lo de memòria fins que la casella se sobreescrigui. En cues de rotació lenta això manté vius objectes "fantasma". És el mateix tipus d'higiene que les referències penjants del mòdul 2.
OverflowError en omplir-se: la cua fixa ha de decidir la seva política de saturació. Llançar una excepció és la política honesta per defecte; a l'exemple de TaskFlow veurem l'altra política habitual (descartar el més antic). L'important és que sigui una decisió explícita.

Traça visual de l'avanç modular

Seguim una CuaCircular(4) operació a operació. Marquem F sota l'índex front i calculem final = (front + mida) % 4 (casella del proper encuament):

Operació	Array `[0][1][2][3]`	front	mida	final (proper)	Retorna
(inicial)	`[ · ][ · ][ · ][ · ]`	0	0	0	—
`encuar(A)`	`[ A ][ · ][ · ][ · ]`	0	1	1	—
`encuar(B)`	`[ A ][ B ][ · ][ · ]`	0	2	2	—
`encuar(C)`	`[ A ][ B ][ C ][ · ]`	0	3	3	—
`desencuar()`	`[ · ][ B ][ C ][ · ]`	1	2	3	A
`encuar(D)`	`[ · ][ B ][ C ][ D ]`	1	3	0	—
`encuar(E)`	`[ E ][ B ][ C ][ D ]`	1	4	— (plena)	—
`desencuar()`	`[ E ][ · ][ C ][ D ]`	2	3	1	B
`desencuar()`	`[ E ][ · ][ · ][ D ]`	3	2	1	C

Les dues files en negreta expliquen la història completa:

Després d'encuar(D), el proper final és (1 + 3) % 4 = 0: ha fet la volta. Per això E aterra a la casella 0, que A va deixar lliure. Cap casella no es desaprofita, res no es desplaça.
Amb la cua plena (mida == 4), front val 1 i la casella del "final" coincidiria amb ell: exactament l'ambigüitat que el comptador resol.

Observa també que l'ordre FIFO es conserva perfectament encara que físicament E sigui "abans" que B a l'array: l'ordre lògic el dicten front i l'avanç modular, no la posició física. És la distinció TAD/implementació del mòdul 1 en la seva versió més gràfica.

Ring buffers al món real i relació amb `LlistaCircular`

El nom professional d'aquesta estructura és ring buffer (buffer circular) i apareix així que grates qualsevol sistema:

Buffers de teclat i de xarxa: el maquinari produeix bytes al seu ritme; el programari els consumeix al seu. Un ring buffer de mida fixa absorbeix la diferència sense demanar memòria mai (crucial en un driver, on no es pot "demanar més memòria").
Àudio i vídeo en streaming: el reproductor llegeix del front mentre la descàrrega escriu pel final; si la descàrrega s'avança massa, espera (cua plena); si es retarda, el reproductor espera (cua buida).
Logs d'últims esdeveniments: journals del sistema, caixes negres d'aviònica, l'historial "últims N" de qualsevol aplicació: el vell se sobreescriu automàticament.

Comparativa amb la seva cosina del mòdul 2:

	`LlistaCircular` (mòdul 2)	`CuaCircular` (aquesta lliçó)
Circularitat aconseguida amb	Enllaç de l'últim node al primer	Operador `%` sobre índexs
Capacitat	Il·limitada (creix node a node)	Fixa (array reservat per endavant)
Memòria	Un `Node` per element, dispersa	Contigua i compacta
Ús típic	Rotació infinita (round-robin del `RepartidorTasques`)	Buffer productor/consumidor de mida acotada

TaskFlow: `RegistreEsdeveniments`, els últims N esdeveniments

A TaskFlow volem un panell d'"activitat recent": els últims 100 esdeveniments del sistema (tasca creada, completada, reassignada...). No volem guardar-los tots —per a això ja hi haurà una base de dades—, només els N més recents, amb memòria constant. És el cas d'ús perfecte del ring buffer amb política de descartar el més antic:

class RegistreEsdeveniments:
    """Guarda els ultims N esdeveniments de TaskFlow amb memoria fixa.

    Politica de saturacio: en omplir-se, l'esdeveniment mes antic es descarta
    per deixar lloc al nou (a diferencia de l'OverflowError per defecte).
    """

    def __init__(self, maxim=100):
        self._esdeveniments = CuaCircular(maxim)

    def registrar(self, tasca, accio):
        if self._esdeveniments.esta_plena():
            self._esdeveniments.desencuar()     # descarta el mes antic: O(1)
        self._esdeveniments.encuar({
            "tasca_id": tasca["id"],
            "titol": tasca["titol"],
            "accio": accio,
        })

    def activitat_recent(self):
        """Retorna els esdeveniments del mes antic al mes recent (O(n))."""
        recents = []
        for _ in range(self._esdeveniments.mida()):
            esdeveniment = self._esdeveniments.desencuar()
            recents.append(esdeveniment)
            self._esdeveniments.encuar(esdeveniment)   # rota la cua una volta completa
        return recents


# --- Us ---
registre = RegistreEsdeveniments(maxim=3)       # 3 per veure-ho amb poc soroll
t1 = {"id": 1, "titol": "Dissenyar el logo", "prioritat": 2, "estat": "pendent"}
t2 = {"id": 2, "titol": "Configurar la CI", "prioritat": 1, "estat": "pendent"}

registre.registrar(t1, "creada")
registre.registrar(t2, "creada")
registre.registrar(t2, "en curs")
registre.registrar(t2, "completada")            # ple! descarta "t1 creada"

for e in registre.activitat_recent():
    print(f"tasca {e['tasca_id']}: {e['accio']}")
# tasca 2: creada
# tasca 2: en curs
# tasca 2: completada

Dues decisions dignes de comentari:

registrar implementa "descartar el vell" component el contracte públic (esta_plena + desencuar + encuar), sense tocar les tripes de CuaCircular. La política viu a la capa de TaskFlow; l'estructura queda genèrica i reutilitzable.
activitat_recent usa el truc de la rotació completa: desencua cada element i el torna a encuar, de manera que després de mida() voltes la cua queda exactament com estava. És la manera de recórrer una cua respectant-ne el contracte (sense accedir a l'array intern).

Potser recordes que l'HistorialAmbLimit del mòdul 3 feia una cosa semblant ("quedar-me amb els últims k") pagant un pop(0) O(n). El RegistreEsdeveniments ja ho fa tot en O(1)... a canvi de fixar la capacitat per endavant. A la lliçó 04-05 veurem la tercera via, la més pythònica: deque(maxlen=k).

Errors Comuns i Consells

Oblidar el % en algun avanç: si escrius self._front += 1 sense mòdul, la cua funciona de meravella... fins a la primera volta, i llavors indexa fora de l'array (IndexError) o llegeix brossa. Els errors "de segona volta" són traïdors perquè les proves curtes no els detecten: prova sempre amb més operacions que capacitat.
Usar front == final com a prova de buida amb només dos índexs: és l'ambigüitat plena/buida. Decideix estratègia (comptador o casella sacrificada) i sigues conseqüent; amb comptador, ni comparis índexs.
Confondre capacitat amb mida: capacitat() és quants n'hi caben; mida() és quants n'hi ha. Al codi de saturació (esta_plena) es comparen entre si, i barrejar-los produeix cues que "s'omplen" a mitges.
Triar malament la política de saturació: excepció, descartar el nou o descartar el vell? Per a un buffer d'ordres d'un usuari, perdre el nou sol ser pitjor; per a un registre d'activitat, perdre el vell és just el que es vol. No hi ha política universal: documenta l'escollida.
Consell: en depurar una cua circular, imprimeix sempre la tripleta (front, mida, capacitat) al costat de l'array. Veure front = 3, mida = 2 sobre [E][·][·][D] t'ensenya més que vint print de l'array sol.

Exercicis

Exercici 1: traça amb volta completa

Sobre una CuaCircular(3), executa en ordre: encuar(1), encuar(2), desencuar(), encuar(3), encuar(4), desencuar(), desencuar(), encuar(5). Construeix la taula de traça (array, front, mida, valor retornat) després de cada operació. A quina casella física acaba el 5 i per què?

Exercici 2: `ultim_encuat`

Afegeix a CuaCircular un mètode ultim_encuat() que retorni (sense extreure'l) l'element més recent, llançant IndexError si la cua és buida. Compte: la casella de l'últim element no és (front + mida) % capacitat (aquesta és la del proper). Fes-ho en O(1).

Exercici 3: redimensionar conservant l'ordre

Escriu un mètode redimensionar(nova_capacitat) que substitueixi l'array intern per un de la nova capacitat, conservant els elements en ordre FIFO i deixant front = 0. Ha de rebutjar amb ValueError una capacitat menor que mida(). Pista: no copiïs caselles per posició física; recol·loca seguint l'ordre lògic, amb índexs modulars des del front antic.

Solucions

Solució 1:

Operació	`[0][1][2]`	front	mida	Retorna
`encuar(1)`	`[1][·][·]`	0	1	—
`encuar(2)`	`[1][2][·]`	0	2	—
`desencuar()`	`[·][2][·]`	1	1	1
`encuar(3)`	`[·][2][3]`	1	2	—
`encuar(4)`	`[4][2][3]`	1	3	—
`desencuar()`	`[4][·][3]`	2	2	2
`desencuar()`	`[4][·][·]`	0	1	3
`encuar(5)`	`[4][5][·]`	0	2	—

El 4 va caure a la casella 0 perquè (1 + 2) % 3 = 0 (primera volta), i el 5 cau a la casella 1 perquè, amb front = 0 i mida = 1, el proper final és (0 + 1) % 3 = 1. L'ordre lògic (front→final) és 4, 5, encara que el 4 sigui físicament abans: el FIFO el dicten els índexs, no la posició.

Solució 2:

def ultim_encuat(self):
    if self.esta_buida():
        raise IndexError("ultim_encuat sobre una cua buida")
    # El proper forat es (front + mida) % capacitat;
    # l'ultim ocupat es la casella ANTERIOR a aquest forat:
    index = (self._front + self._mida - 1) % self._capacitat
    return self._dades[index]

El - 1 dins del mòdul gestiona també el cas de la volta: amb front = 2, mida = 1, capacitat = 3, l'últim és a (2 + 1 - 1) % 3 = 2, correcte. En Python, fins i tot (0 - 1) % 3 dona 2 (el mòdul de Python mai no és negatiu), així que la fórmula és segura.

Solució 3:

def redimensionar(self, nova_capacitat):
    if nova_capacitat < self._mida:
        raise ValueError("els elements actuals no hi caben")
    nous = [None] * nova_capacitat
    for i in range(self._mida):
        # i-esim element en ordre logic, comencant pel front:
        nous[i] = self._dades[(self._front + i) % self._capacitat]
    self._dades = nous
    self._capacitat = nova_capacitat
    self._front = 0             # l'ordre logic queda "desenrotllat" des de 0

La clau és l'índex (self._front + i) % self._capacitat: recorre els elements en ordre FIFO real, encara que estiguin partits en dos trams físics (final de l'array + principi). Copiar l'array tal qual (self._dades[:]) seria un error: barrejaria caselles buides pel mig i trencaria l'ordre.

Conclusió

La cua circular resol el problema de la cua sobre memòria fixa: dos índexs que avancen amb aritmètica modular ((i + 1) % capacitat), un comptador que desfà l'ambigüitat plena/buida, i totes les operacions en O(1) sense desplaçar mai cap element. És la versió "d'array" de la idea que ja vam veure amb enllaços a la LlistaCircular, i és l'estructura dels ring buffers que sostenen drivers, streaming i registres d'activitat — inclòs el nostre RegistreEsdeveniments dels últims N esdeveniments de TaskFlow. Fins ara, totes les nostres cues comparteixen un dogma: surt el més antic. Però a TaskFlow hi ha tasques amb prioritat 1 que no poden esperar el seu torn darrere de vint tasques rutinàries. Toca trencar el dogma amb seny: a la propera lliçó, la cua de prioritat, on desencuar vol dir "dona'm el més urgent" — i on per fi extraurem allò que el min-stack del mòdul 3 només podia mirar.

Cues Circulars

Contingut

El problema: una cua sobre array fix

La idea circular: aritmètica modular

El trencaclosques: plena o buida?

La classe `CuaCircular`

Traça visual de l'avanç modular

Ring buffers al món real i relació amb `LlistaCircular`

TaskFlow: `RegistreEsdeveniments`, els últims N esdeveniments

Errors Comuns i Consells

Exercicis

Exercici 1: traça amb volta completa

Exercici 2: `ultim_encuat`

Exercici 3: redimensionar conservant l'ordre

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

Cues Circulars

Contingut

El problema: una cua sobre array fix

La idea circular: aritmètica modular

El trencaclosques: plena o buida?

La classe CuaCircular

Traça visual de l'avanç modular

Ring buffers al món real i relació amb LlistaCircular

TaskFlow: RegistreEsdeveniments, els últims N esdeveniments

Errors Comuns i Consells

Exercicis

Exercici 1: traça amb volta completa

Exercici 2: ultim_encuat

Exercici 3: redimensionar conservant l'ordre

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

La classe `CuaCircular`

Ring buffers al món real i relació amb `LlistaCircular`

TaskFlow: `RegistreEsdeveniments`, els últims N esdeveniments

Exercici 2: `ultim_encuat`