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

Cues Dobles (Deques)

Següent ►
►

Aquest és el capítol on saldem el primer deute del mòdul 3. El nostre HistorialAmbLimit apilava accions per un extrem però, en omplir-se, descartava per l'altre amb un pop(0) O(n) que llavors vam qualificar de "tolerable"... prometent una solució elegant. L'estructura que ho arregla és la cua doble o deque (double-ended queue): un TAD que permet inserir i extreure en O(1) per tots dos extrems. En Python ve de sèrie com a collections.deque, que ja vam esmentar de passada al mòdul 2 ("una doblement enllaçada per blocs"); avui l'estudiarem a fons: les seves operacions, els seus costos, el seu paràmetre estrella maxlen i —igual d'important— quan no usar-la. També veurem que, en realitat, la implementació conceptual ja la tenim gairebé escrita des del mòdul 2, i la posarem a treballar a TaskFlow amb una finestra lliscant de productivitat.

Contingut

  1. El TAD deque: un contracte amb quatre portes
  2. Deque, pila i cua: una generalització
  3. collections.deque a fons
  4. Quan NO usar una deque
  5. La promesa complerta: HistorialAmbLimit amb maxlen
  6. Implementació conceptual sobre LlistaDoblementEnllacada
  7. TaskFlow: finestra lliscant de tasques completades
  8. Bonus clàssic: palíndroms

El TAD deque: un contracte amb quatre portes

Una deque és una seqüència amb accés restringit als dos extrems, i amb les quatre combinacions permeses:

Operació Extrem Promesa de cost
encuar_final(x) Dret (final) O(1)
encuar_front(x) Esquerre (front) O(1)
desencuar_final() Dret O(1)
desencuar_front() Esquerre O(1)
front() / final() Consulta tots dos extrems O(1)
esta_buida() / mida() — O(1) 
graph LR
    EF["encuar_front / desencuar_front"] <--> D["[ front | ... | final ]"]
    D <--> EFin["encuar_final / desencuar_final"]

El que continua prohibit —i això defineix la deque davant d'una llista general— és tocar l'interior: no hi ha inserció ni esborrat pel mig al contracte. Tota la potència es concentra a les vores, i a canvi les vores són sempre O(1).

Deque, pila i cua: una generalització

La deque és el TAD més general dels tres que coneixem d'accés restringit; pila i cua són casos particulars obtinguts tancant portes:

Per obtenir... Usa només... Política resultant
Una pila encuar_final + desencuar_final LIFO (un sol extrem)
Una cua encuar_final + desencuar_front FIFO (extrems oposats)
Una deque Les quatre Totes dues, a triar en cada operació

Això explica per què en Python professional collections.deque s'usa també com a pila i com a cua: una sola estructura ben feta cobreix els tres contractes. Compte, però, amb el raonament invers: que pugui usar-se de tres maneres no vol dir que el teu codi les hagi de barrejar. Si la teva variable és conceptualment una cua, usa només el parell FIFO; el nom de la variable i la disciplina d'accés documenten la intenció (és la lliçó d'"exposa només el contracte" de 04-02).

collections.deque a fons

collections.deque és la implementació de deque de la biblioteca estàndard. Internament —ho vam avançar al mòdul 2— és una llista doblement enllaçada de blocs: en lloc d'un node per element, enllaça blocs de 64 caselles, cosa que redueix moltíssim el cost en memòria i el nombre de salts entre nodes, conservant O(1) a tots dos extrems.

La seva correspondència amb el nostre contracte:

Contracte del TAD collections.deque Cost
encuar_final(x) d.append(x) O(1)
encuar_front(x) d.appendleft(x) O(1)
desencuar_final() d.pop() O(1)
desencuar_front() d.popleft() O(1)
front() / final() d[0] / d[-1] O(1)
mida() len(d) O(1)
— (extra) d.extend(iterable), d.extendleft(iterable) O(k)
— (extra) d.rotate(n) (rota n posicions) O(min(n, len))
— (extra) maxlen (longitud màxima) — 
from collections import deque

d = deque(["B", "C"])       # es pot crear des de qualsevol iterable
d.append("D")               # pel final:  B, C, D
d.appendleft("A")           # pel front:  A, B, C, D
print(d[0], d[-1])          # A D  (consultar extrems: O(1))
print(d.popleft())          # A    (FIFO si combines append + popleft)
print(d.pop())              # D    (LIFO si combines append + pop)
print(list(d))              # ['B', 'C']

Detalls que convé conèixer:

  • extendleft insereix els elements un a un per l'esquerra, així que l'iterable queda invertit dins la deque: deque([3]); d.extendleft([2, 1]) produeix 1, 2, 3. És una sorpresa habitual.
  • rotate(1) mou l'últim element al front (i rotate(-1) al revés): és el "gir" de la LlistaCircular del mòdul 2, de franc.
  • Una deque buida llança IndexError a pop()/popleft(): la mateixa política EAFP que venim usant a les nostres classes des del mòdul 3.

El paràmetre maxlen

La joia per als nostres propòsits: una deque creada amb deque(maxlen=k) mai no supera k elements. Si és plena i fas append, descarta automàticament l'element de l'extrem oposat (el front); amb appendleft, descarta el del final. Tot en O(1):

from collections import deque

ultims = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    ultims.append(x)
    print(list(ultims))
# [1]
# [1, 2]
# [1, 2, 3]
# [2, 3, 4]   ← l'1 s'ha descartat sol, sense pop(0), sense O(n)
# [3, 4, 5]

Compara amb la lliçó anterior de cues circulars: maxlen et dona la política "descartar el més antic" del RegistreEsdeveniments, però sense escriure la classe. Quina usar? deque(maxlen=k) en el Python del dia a dia; la CuaCircular artesanal quan necessitis control total (o quan programis en un llenguatge sense deque de sèrie) — i, sobretot, per entendre què fa la màgia per dins.

Quan NO usar una deque

Cap estructura no és gratis en totes les operacions; la deque paga el seu O(1) als extrems amb un interior car:

Operació list deque
x[i] als extrems O(1) O(1)
x[i] pel mig O(1) O(n) — cal saltar de bloc en bloc
Llesques x[a:b] O(k) No suportades directament
insert/del pel mig O(n) O(n) (i contra l'esperit del TAD)
sort() O(n log n) No existeix (cal passar per list)
append / pop final O(1) am. O(1)
insert(0) / pop(0) O(n) O(1) (appendleft/popleft)

Regla pràctica: si el teu patró d'accés és "pels extrems", deque; si és "per índex a qualsevol posició" o necessites ordenar i llescar, list. Una deque usada com a array d'accés aleatori (bucles amb d[i] sobre el mig) amaga un O(n²) tan traïdor com el pop(0) en bucle que vam denunciar al mòdul 1 — la trampa simètrica.

La promesa complerta: HistorialAmbLimit amb maxlen

Recordem el problema del mòdul 3: guardar les últimes k accions de l'usuari per desfer, descartant les més antigues en superar el límit. La nostra versió sobre list apilava amb append (bé) però descartava amb pop(0) (O(n), "tolerable" per a k petit). La reescriptura amb deque és gairebé anticlimàtica de tan curta:

from collections import deque

class HistorialAmbLimit:
    """Ultimes k accions de l'usuari. Versio deque: tot O(1).

    Mateix contracte que la versio del modul 3; nomes canvia el motor.
    """

    def __init__(self, limit):
        self._accions = deque(maxlen=limit)

    def registrar(self, accio):
        self._accions.append(accio)       # si es ple, maxlen descarta
                                          # el mes antic pel front: O(1)

    def desfer(self):
        if self.esta_buida():
            raise IndexError("no hi ha accions per desfer")
        return self._accions.pop()        # LIFO pel final: O(1)

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

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

Fixa't en l'anatomia: registrar/desfer treballen pel final (comportament de pila, com exigeix el "desfer"), mentre maxlen descarta pel front (comportament de cua). Dos extrems actius alhora: per això ni la pila ni la cua simples no bastaven, i per això la deque és *l'*estructura dels historials amb límit. El contracte públic no ha canviat des del mòdul 3 — codi client intacte, cost millorat: la victòria perfecta del TAD.

Implementació conceptual sobre LlistaDoblementEnllacada

I si l'haguéssim d'implementar nosaltres? La sorpresa és que ja gairebé ho vam fer. La LlistaDoblementEnllacada del mòdul 2 manté cap, cua i nodes NodeDoble amb anterior i seguent; per això pot inserir i eliminar per tots dos extrems en O(1) (per eliminar per la cua, l'enllaç anterior ens dona el penúltim sense recórrer — just el que a la llista simple li faltava a 04-02). Una deque és, conceptualment, una LlistaDoblementEnllacada amb el contracte restringit als extrems:

class CuaDoble:
    """Deque didactica: embolcalla la LlistaDoblementEnllacada del modul 2
    i exposa NOMES les operacions d'extrem."""

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

    def encuar_front(self, x):
        self._elements.inserir_al_principi(x)      # O(1): reajusta el cap

    def encuar_final(self, x):
        self._elements.inserir_al_final(x)         # O(1): reajusta la cua

    def desencuar_front(self):
        if self.esta_buida():
            raise IndexError("desencuar sobre una deque buida")
        return self._elements.eliminar_del_principi()     # O(1)

    def desencuar_final(self):
        if self.esta_buida():
            raise IndexError("desencuar sobre una deque buida")
        return self._elements.eliminar_del_final()        # O(1) gracies a 'anterior'

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

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

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

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

No hi ha algorismes nous: només una muralla de contracte al voltant d'una estructura que ja ho sabia fer tot. És la mateixa jugada que Cua sobre LlistaEnllacada (04-02) i Pila sobre list (mòdul 3). La diferència entre aquesta classe i collections.deque és d'enginyeria, no de concepte: els blocs de 64 elements estalvien memòria i acceleren constants, però el Big O és idèntic.

TaskFlow: finestra lliscant de tasques completades

Estrenem la deque a TaskFlow amb un patró professional de primera: la finestra lliscant (sliding window). L'equip vol veure al panell la mitjana mòbil de tasques completades per dia durant els últims 7 dies: cada dia entra la dada nova i "cau" la de fa 8 dies. És exactament deque(maxlen=7) més una suma mantinguda:

from collections import deque

class FinestraProductivitat:
    """Mitjana mobil de tasques completades/dia sobre els ultims k dies."""

    def __init__(self, dies=7):
        self._finestra = deque(maxlen=dies)
        self._suma = 0                        # suma mantinguda: mitjana en O(1)

    def tancar_dia(self, completades):
        if len(self._finestra) == self._finestra.maxlen:
            self._suma -= self._finestra[0]   # el dia que caura (front: O(1))
        self._finestra.append(completades)    # entra el dia nou (maxlen descarta)
        self._suma += completades

    def mitjana_mobil(self):
        if not self._finestra:
            return 0.0
        return self._suma / len(self._finestra)


# --- Us: dues setmanes de feina de l'equip ---
panell = FinestraProductivitat(dies=7)
for dia, completades in enumerate([3, 5, 2, 4, 6, 1, 0, 7, 8, 6, 5, 9, 4, 3], 1):
    panell.tancar_dia(completades)
    print(f"dia {dia:2}: completades={completades}  mitjana 7 dies={panell.mitjana_mobil():.2f}")

Els detalls fins, que són els que converteixen això en O(1) per dia:

  • La suma mantinguda: recalcular sum(self._finestra) a cada consulta seria O(k). En canvi, en lliscar la finestra restem el valor que surt i sumem el que entra: la mitjana queda disponible en O(1). Aquest patró "actualitza, no recalculis" és parent directe de la PilaAmbMinim del mòdul 3, que mantenia el mínim en lloc de buscar-lo.
  • Llegir self._finestra[0] abans de l'append: amb maxlen assolit, l'append descarta el front silenciosament; si no l'haguéssim restat abans, la suma quedaria corrupta. L'accés [0] és extrem → O(1), dins de les regles de la deque.
  • Durant els primers dies (finestra encara no plena) la mitjana es calcula sobre els dies disponibles: len(self._finestra) ho gestiona sol.

Aquest mateix esquelet de finestra lliscant resol mitjanes de càrrega de servidors, sensors, cotitzacions... i una variant amb truc (el màxim en finestra) t'espera als exercicis de 04-06.

Bonus clàssic: palíndroms

L'exercici canònic de deques: és una paraula un palíndrom (es llegeix igual del dret i del revés)? Amb una deque, la idea és física: compara els dos extrems i ves tancant la pinça:

from collections import deque

def es_palindrom(text):
    lletres = deque(c.lower() for c in text if c.isalnum())  # neteja espais/signes
    while len(lletres) > 1:
        if lletres.popleft() != lletres.pop():   # front vs final: tots dos O(1)
            return False
    return True                                  # 0 o 1 lletres restants: simetric

print(es_palindrom("I ara rai"))                 # True
print(es_palindrom("TaskFlow"))                  # False

Cada volta consumeix una lletra de cada extrem: n/2 comparacions, totes O(1) → O(n) total. Fer-ho amb una list i pop(0) seria O(n²); la deque és la diferència entre l'algorisme i la seva caricatura.

Errors Comuns i Consells

  • Indexar l'interior d'una deque en un bucle: for i in range(len(d)): usar(d[i]) és O(n²) perquè cada d[i] central és O(n). Itera amb for x in d (O(n) total) o converteix a list si de debò necessites índexs.
  • Oblidar que maxlen descarta en silenci: no hi ha excepció ni avís quan un append expulsa el més antic. Si la teva lògica depèn de l'element que cau (com la suma de FinestraProductivitat), captura'l abans de l'append.
  • extendleft inverteix: d.extendleft([1, 2, 3]) deixa 3, 2, 1, ... al front. Si vols conservar l'ordre, d.extendleft(reversed(sequencia)).
  • Usar deque quan necessites ordenar o llescar: ni sort() ni d[2:5] no existeixen. Si el teu algorisme els demana sovint, l'estructura correcta era una list (o mantenir l'ordre amb inserció ordenada, mòdul 2).
  • Consell: quan dubtis entre list i deque, escriu primer les operacions que farà el teu codi (no les que "potser" farà) i marca-les a la taula de costos d'aquesta lliçó. L'estructura correcta sol quedar assenyalada sola — és el mètode que venim aplicant des de la taula de costos del mòdul 1.

Exercicis

Exercici 1: traça de les quatre portes

Partint d'una deque buida, traça el contingut (de front a final) després de cada operació: encuar_final(2), encuar_front(1), encuar_final(3), desencuar_front(), encuar_front(0), desencuar_final(), desencuar_final(). Indica també què retorna cada desencuar_*. Quina estructura clàssica hauries obtingut si totes les operacions haguessin estat encuar_final/desencuar_front?

Exercici 2: últims k errors, amb lectura no destructiva

Amb deque(maxlen=k), escriu la classe UltimsErrors per a TaskFlow: anotar(missatge) guarda un error (descartant el més antic si se supera k) i llistat() retorna una list amb els errors del més recent al més antic, sense modificar la deque. Tot anotar ha de ser O(1).

Exercici 3: mitjana mòbil robusta a dies sense dades

Amplia FinestraProductivitat amb un mètode tancar_dia_sense_dades() per a dies festius: la finestra s'ha de lliscar (el dia compta, i expulsa el més antic si toca) però el dia no aporta tasques i no ha de comptar en el denominador de la mitjana. Pista: encua tuples (valor, compta_en_mitjana) o el valor None, i mantén, a més de _suma, un comptador _dies_valids.

Solucions

Solució 1:

Operació Deque (front → final) Retorna
encuar_final(2) 2 —
encuar_front(1) 1, 2 —
encuar_final(3) 1, 2, 3 —
desencuar_front() 2, 3 1
encuar_front(0) 0, 2, 3 —
desencuar_final() 0, 2 3
desencuar_final() 0 2

Només amb encuar_final + desencuar_front hauríem usat la deque com a cua FIFO (el parell d'operacions de la taula de generalització).

Solució 2:

from collections import deque

class UltimsErrors:
    def __init__(self, k=10):
        self._errors = deque(maxlen=k)

    def anotar(self, missatge):
        self._errors.append(missatge)          # O(1); maxlen descarta el vell

    def llistat(self):
        return list(reversed(self._errors))    # copia, el mes recent primer

reversed(deque) itera del final al front en O(n) sense tocar la deque, i list(...) materialitza la còpia: el client pot fer-hi el que vulgui sense corrompre l'historial. Anotar continua sent O(1) perquè el cost O(n) només es paga en consultar.

Solució 3:

class FinestraProductivitat(FinestraProductivitat):   # ampliem la classe
    def __init__(self, dies=7):
        super().__init__(dies)
        self._dies_valids = 0

    def _lliscar(self, entrant):
        if len(self._finestra) == self._finestra.maxlen:
            sortint = self._finestra[0]
            if sortint is not None:           # nomes restar si comptava
                self._suma -= sortint
                self._dies_valids -= 1
        self._finestra.append(entrant)

    def tancar_dia(self, completades):
        self._lliscar(completades)
        self._suma += completades
        self._dies_valids += 1

    def tancar_dia_sense_dades(self):
        self._lliscar(None)                   # ocupa forat, no aporta dades

    def mitjana_mobil(self):
        if self._dies_valids == 0:
            return 0.0
        return self._suma / self._dies_valids

La idea: None és un "forat amb dret a casella": llisca la finestra (i pot expulsar dies antics) però ni suma ni compta. En sortir de la finestra, un None tampoc no resta res. Error comú aquí: usar 0 en lloc de None — la suma sortiria bé, però el denominador comptaria el festiu i enfonsaria la mitjana injustament!

Conclusió

La deque completa la nostra família de cues: quatre operacions d'extrem, totes O(1), de les quals pila i cua són casos particulars. Hem espremut collections.deque —append/appendleft/pop/popleft, rotate, i el decisiu maxlen que descarta el més antic de franc—, n'hem après el límit real (l'interior és O(n): no és un array d'accés aleatori), hem complert la promesa del mòdul 3 reescrivint HistorialAmbLimit en quatre línies O(1), i hem comprovat que la implementació conceptual era la LlistaDoblementEnllacada del mòdul 2 amb el contracte restringit. De propina, TaskFlow estrena panell de productivitat amb una finestra lliscant de mitjana mòbil en O(1) per dia. Amb això, la teoria del mòdul és completa: cua FIFO, cua circular, cua de prioritat i deque. A la propera lliçó no hi ha conceptes nous: hi ha sis exercicis progressius on aquestes quatre estructures —i les piles del mòdul 3— treballen juntes sobre TaskFlow. És el moment de consolidar; ens veiem al gimnàs.

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