04 - Liste, stack, queue e deque

Un editor di testo deve annullare l'ultima modifica, un browser deve tornare alla pagina precedente, una stampante deve servire i lavori nell'ordine in cui sono arrivati, un pronto soccorso deve far passare prima il codice rosso. Sono quattro comportamenti diversi (ultimo dentro, primo fuori; primo dentro, primo fuori; entrambe le estremità; per priorità) e ciascuno ha un nome e una struttura. La scelta sbagliata non si vede con dieci elementi e ti rovina con centomila, per questo qui ogni costo è un conteggio e ogni struttura è scritta e provata.

Questo è il quarto articolo della serie Algoritmi e Strutture Dati. Conviene aver letto l'analisi ammortizzata del primo articolo, perché ricomparirà due volte, e quello sulla ricerca e le tabelle hash, di cui qui ritrovi il ridimensionamento. I listati sono in Python 3.14 con la sola libreria standard (python3 -I), le uscite sono quelle ottenute eseguendoli due volte con risultato identico, e il riferimento indipendente di ogni struttura è quasi sempre l'implementazione della libreria standard su sequenze casuali a seme fisso.

Array dinamico o lista concatenata: chi paga che cosa

Un array dinamico tiene gli elementi contigui in memoria: leggere l'indice k è un solo accesso, ma inserire in mezzo obbliga a spostare tutto ciò che segue. Una lista concatenata tiene ogni elemento in un nodo che punta al successivo: inserire dopo un nodo già raggiunto costa un puntatore, ma raggiungere il k-esimo costa k salti. Il listato implementa entrambe e conta gli spostamenti dell'array e i salti della lista, dopo averle provate contro list su 3.000 inserimenti e letture in posizioni casuali.

# Array dinamico contro lista concatenata: si contano gli spostamenti di elementi e i salti fra nodi
import random

class ArrayList:
    def __init__(self):
        self.buf, self.n, self.cost = [None] * 4, 0, 0
    def insert(self, i, x):
        if self.n == len(self.buf):                  # pieno: raddoppia e copia
            new = [None] * (2 * len(self.buf))
            for j in range(self.n):
                new[j] = self.buf[j]; self.cost += 1
            self.buf = new
        for j in range(self.n, i, -1):               # sposta a destra tutto cio' che sta dopo i
            self.buf[j] = self.buf[j - 1]; self.cost += 1
        self.buf[i] = x
        self.n += 1
    def get(self, i):
        return self.buf[i]                           # un solo accesso, nessun costo da contare
    def to_list(self):
        return self.buf[:self.n]

class Node:
    __slots__ = ("val", "next")
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt

class LinkedList:
    def __init__(self):
        self.head, self.n, self.cost = None, 0, 0
    def insert(self, i, x):
        if i == 0:
            self.head = Node(x, self.head)
        else:
            node = self.head
            for _ in range(i - 1):                   # un salto per ogni nodo attraversato
                node = node.next; self.cost += 1
            node.next = Node(x, node.next)
        self.n += 1
    def get(self, i):
        node = self.head
        for _ in range(i):
            node = node.next; self.cost += 1
        return node.val
    def to_list(self):
        out, node = [], self.head
        while node:
            out.append(node.val); node = node.next
        return out

rng = random.Random(10)
for cls in (ArrayList, LinkedList):                  # correttezza contro list: 3000 inserimenti e letture casuali
    s, ref = cls(), []
    for t in range(3000):
        i = rng.randint(0, len(ref))
        s.insert(i, t); ref.insert(i, t)
        j = rng.randrange(len(ref))
        assert s.get(j) == ref[j]
    assert s.to_list() == ref
print("ArrayList e LinkedList coerenti con list su 3000 operazioni")

print(f"{'operazione su n=1000':<28} {'array: spostamenti':>19} {'lista: salti':>13}")
for label, pos in (("inserisci in testa", 0), ("inserisci a meta'", 500), ("inserisci in coda", 1000)):
    a, l = ArrayList(), LinkedList()
    for k in range(1000):
        a.insert(a.n, k); l.insert(l.n, k)
    a.cost = l.cost = 0                              # si azzera il contatore: conta solo l'operazione misurata
    a.insert(pos, -1); l.insert(pos, -1)
    print(f"{label:<28} {a.cost:>19} {l.cost:>13}")
l.cost = 0
l.get(999)
print(f"{'leggi l indice 999':<28} {'0':>19} {l.cost:>13}")

# Output:
# ArrayList e LinkedList coerenti con list su 3000 operazioni
# operazione su n=1000          array: spostamenti  lista: salti
# inserisci in testa                          1000             0
# inserisci a meta'                            500           499
# inserisci in coda                              0           999
# leggi l indice 999                             0           999

L'uscita mostra due profili opposti su una struttura di mille elementi. Inserire in testa costa 1.000 spostamenti all'array e zero salti alla lista; inserire in mezzo costa 500 contro 499; leggere l'ultimo indice costa un accesso all'array e 999 salti alla lista. La lista vince solo quando il punto d'inserimento è già in mano (un cursore, la testa); appena devi raggiungerlo, il costo di cercarlo annulla il guadagno. Inserire in coda alla lista costa 999 salti perché questa versione non tiene un puntatore all'ultimo nodo: con quel puntatore sarebbe costante, ma è un'ottimizzazione che ho scelto di non implementare, per non confondere i due costi.

C'è un terzo costo che questi conteggi non vedono: la località della memoria. Nell'array elementi vicini stanno vicini, nella lista i nodi possono stare ovunque. Non l'ho misurato (sono conteggi, non tempi) e non cito un fattore: ti basti sapere che a parità di conteggio l'array parte avvantaggiato, ed è il motivo per cui list di Python, che è un array dinamico, è la scelta di partenza. Per l'inserimento ammortizzato in coda vale quanto visto nel primo articolo, e in Python l'operazione l.pop(k) costa O(n − k) per la documentazione.

Pila (stack): ultimo dentro, primo fuori

Una pila ha due operazioni, impila e togli dalla cima, e sono entrambe a costo costante. La struttura serve ogni volta che devi ricordare «dove tornare» in ordine inverso: annullare, ricorsione, parsing. L'esempio classico è controllare che parentesi tonde, quadre e graffe siano bilanciate. Ogni apertura va impilata, ogni chiusura deve combaciare con l'ultima aperta e non ancora chiusa. Il listato si ferma al primo errore e confronta il risultato con un riferimento del tutto diverso: cancellare ripetutamente le coppie adiacenti vuote (), [], {} finché la stringa non cambia più.

# Pila (stack) LIFO: parentesi bilanciate. Il controllo si ferma al primo errore
import random

PAIRS = {")": "(", "]": "[", "}": "{"}

def balanced(s):
    stack, ops = [], 0
    for ch in s:
        if ch in "([{":
            stack.append(ch); ops += 1               # apri: impila
        elif ch in PAIRS:
            ops += 1
            if not stack or stack.pop() != PAIRS[ch]:    # chiudi: deve combaciare con l'ultima aperta
                return False, ops
    return not stack, ops

def balanced_reference(s):                           # riferimento indipendente: cancella le coppie adiacenti finche' si puo'
    prev = None
    while prev != s:
        prev, s = s, s.replace("()", "").replace("[]", "").replace("{}", "")
    return s == ""

rng = random.Random(11)
positives = 0
for _ in range(20000):
    s = "".join(rng.choice("()[]{}") for _ in range(rng.randrange(0, 13)))
    ok, ops = balanced(s)
    assert ok == balanced_reference(s) and ops <= len(s)    # ogni carattere costa al piu' un'operazione
    positives += ok
print("20000 stringhe casuali: concordano col riferimento; bilanciate:", positives)

for s in ("{[()()]}", "([)]", "((", "())"):
    print(f"{s!r:>12} ->", balanced(s))

# Output:
# 20000 stringhe casuali: concordano col riferimento; bilanciate: 1683
#   '{[()()]}' -> (True, 8)
#       '([)]' -> (False, 3)
#         '((' -> (False, 2)
#        '())' -> (False, 3)

Su 20.000 stringhe casuali di lunghezza fino a 12 i due metodi concordano sempre (1.683 sono bilanciate), e il numero di operazioni sulla pila non supera mai la lunghezza della stringa: ogni carattere viene impilato o tolto al più una volta, quindi il controllo è lineare. Le quattro righe finali mostrano i casi interessanti: ([)] ha lo stesso numero di aperte e chiuse di un'espressione corretta ma fallisce alla terza operazione, perché la pila non può rispondere «sì» a una chiusura che non combacia con la cima. Un semplice contatore di parentesi non lo vedrebbe.

In Python la pila è una list con append e pop, perché entrambe lavorano sull'estremità finale e sono O(1), ammortizzato per l'append. Non serve una classe dedicata a meno di voler impedire accessi al centro. La stessa pila, usata dal runtime per le chiamate di funzione, ha un limite di profondità: se una ricorsione è profonda quanto l'ingresso, convertirla in un ciclo con pila esplicita, come nel quick sort del secondo articolo, è la correzione standard.

Coda (queue): primo dentro, primo fuori, con due pile

Una coda restituisce gli elementi nell'ordine d'arrivo. Si può costruire con due pile: le nuove richieste si impilano in una (la «posta in arrivo»), e quando bisogna estrarre si prende dalla seconda (la «posta in uscita»); solo quando questa è vuota si travasa l'intera prima pila, che inverte l'ordine e rimette il più vecchio in cima. Il listato la prova contro collections.deque su 50.000 operazioni casuali e conta i travasi.

# Coda (queue) FIFO costruita con due pile: costo ammortizzato O(1), ma un singolo dequeue puo' costare n
import random
from collections import deque

class TwoStackQueue:
    def __init__(self):
        self.inbox, self.outbox = [], []
        self.moves = 0                               # travasi da una pila all'altra
        self.worst_dequeue = 0
    def enqueue(self, x):
        self.inbox.append(x)
    def dequeue(self):
        cost = 1
        if not self.outbox:                          # solo se la pila di uscita e' vuota si travasa tutto
            while self.inbox:
                self.outbox.append(self.inbox.pop())
                self.moves += 1; cost += 1
        self.worst_dequeue = max(self.worst_dequeue, cost)
        return self.outbox.pop()

# correttezza contro collections.deque su 50000 operazioni casuali (seme fisso)
rng = random.Random(12)
q, ref, pushes = TwoStackQueue(), deque(), 0
for step in range(50000):
    if ref and rng.random() < 0.45:
        assert q.dequeue() == ref.popleft()
    else:
        q.enqueue(step); ref.append(step); pushes += 1
assert q.moves <= pushes                             # ogni elemento viene travasato AL PIU' una volta
print(f"coerente con deque; enqueue: {pushes}, travasi totali: {q.moves} (<= enqueue)")

# il caso sfavorevole: n enqueue e poi n dequeue di fila
for n in (1000, 100000):
    q = TwoStackQueue()
    for k in range(n):
        q.enqueue(k)
    for k in range(n):
        assert q.dequeue() == k
    print(f"n={n}: travasi totali {q.moves}, per elemento {q.moves / n:.2f}, dequeue piu' costoso {q.worst_dequeue}")

# Output:
# coerente con deque; enqueue: 27266, travasi totali: 24353 (<= enqueue)
# n=1000: travasi totali 1000, per elemento 1.00, dequeue piu' costoso 1001
# n=100000: travasi totali 100000, per elemento 1.00, dequeue piu' costoso 100001

Ogni elemento viene travasato al più una volta, quindi i travasi totali non superano gli enqueue (24.353 contro 27.266 nella sequenza casuale, ed esattamente n nello scenario sfavorevole). Il costo ammortizzato di un'operazione è quindi costante: è un conteggio, ne avevi visto la logica nel primo articolo. Ma il «dequeue più costoso» vale 1.001 con mille elementi e 100.001 con centomila: un singolo estratto può costare n. Se hai una latenza massima da garantire, questa coda va bene per il throughput, non per il caso peggiore.

Deque: entrambe le estremità a costo costante

Una deque (double-ended queue) aggiunge e toglie a entrambe le estremità. Il modo naturale di realizzarla è un buffer circolare: un array con un indice di testa, in cui «prima della posizione 0» è l'ultima cella, e che raddoppia quando si riempie. Il listato la implementa e la verifica contro collections.deque su 50.000 operazioni miste (append, appendleft, pop, popleft), controllando a ogni passo anche la lunghezza.

# Deque su buffer circolare: O(1) ammortizzato a entrambe le estremita'. Poi: perche' list.pop(0) e' un errore
import random, time
from collections import deque

class RingDeque:
    def __init__(self):
        self.buf, self.head, self.n = [None] * 4, 0, 0
    def _grow(self):
        if self.n == len(self.buf):
            old = [self.buf[(self.head + i) % len(self.buf)] for i in range(self.n)]
            self.buf, self.head = old + [None] * len(old), 0
    def append(self, x):
        self._grow(); self.buf[(self.head + self.n) % len(self.buf)] = x; self.n += 1
    def appendleft(self, x):
        self._grow(); self.head = (self.head - 1) % len(self.buf); self.buf[self.head] = x; self.n += 1
    def pop(self):
        i = (self.head + self.n - 1) % len(self.buf)
        x, self.buf[i] = self.buf[i], None; self.n -= 1
        return x
    def popleft(self):
        x, self.buf[self.head] = self.buf[self.head], None
        self.head = (self.head + 1) % len(self.buf); self.n -= 1
        return x

rng = random.Random(13)
d, ref = RingDeque(), deque()
for step in range(50000):                            # 50000 operazioni a caso sulle due estremita'
    op = rng.randrange(4)
    if op == 0:
        d.append(step); ref.append(step)
    elif op == 1:
        d.appendleft(step); ref.appendleft(step)
    elif ref and op == 2:
        assert d.pop() == ref.pop()
    elif ref:
        assert d.popleft() == ref.popleft()
    assert d.n == len(ref)
print("RingDeque coerente con collections.deque su 50000 operazioni; elementi rimasti:", d.n)

# svuotare una coda di n elementi con list.pop(0): ogni estrazione sposta tutti gli altri
for n in (1000, 2000, 4000):
    print(f"n={n}: spostamenti con pop(0) = n(n-1)/2 = {n * (n - 1) // 2}; con deque.popleft = 0")

# misura indicativa: si riporta solo l'ordine di grandezza del rapporto, che cambia da una macchina all'altra
n = 30000
lst, dq = list(range(n)), deque(range(n))
t0 = time.perf_counter()
while lst:
    lst.pop(0)
t_list = time.perf_counter() - t0
t0 = time.perf_counter()
while dq:
    dq.popleft()
t_deque = time.perf_counter() - t0
print("svuotare 30000 elementi: pop(0) piu' lento di popleft di oltre 10 volte?", t_list > 10 * t_deque)

# Output:
# RingDeque coerente con collections.deque su 50000 operazioni; elementi rimasti: 74
# n=1000: spostamenti con pop(0) = n(n-1)/2 = 499500; con deque.popleft = 0
# n=2000: spostamenti con pop(0) = n(n-1)/2 = 1999000; con deque.popleft = 0
# n=4000: spostamenti con pop(0) = n(n-1)/2 = 7998000; con deque.popleft = 0
# svuotare 30000 elementi: pop(0) piu' lento di popleft di oltre 10 volte? True

La parte istruttiva è nel confronto con list.pop(0). La documentazione di Python dice che le liste, ottimizzate per operazioni a lunghezza fissa, comportano costi di spostamento di memoria O(n) per pop(0) e insert(0, v), e consiglia la deque per lavorare a entrambe le estremità; vale lo stesso per collections.deque, che garantisce append e pop thread-safe a O(1), con costo circa uguale da entrambi i lati. Nel modello del listato, svuotare una coda di n elementi con pop(0) sposta n(n − 1)/2 elementi in totale (7.998.000 con n = 4.000), contro zero della deque. La misura indicativa dell'ultima riga conferma l'ordine di grandezza (oltre dieci volte più lento con 30.000 elementi su questa macchina): è l'unico tempo di questo articolo, e non va letto come un valore ma come una soglia, perché cambia fra macchine ed esecuzioni.

La conseguenza pratica è semplice. Una list come coda funziona finché ha poche decine di elementi, e diventa il collo di bottiglia quando cresce. Se stai scrivendo una visita in ampiezza di un grafo, come vedrai nell'articolo su BFS e DFS, la frontiera da esplorare è una coda, e la struttura giusta è la deque.

Coda a priorità: l'heap binario

Una coda a priorità restituisce sempre l'elemento più piccolo (o più grande) fra quelli presenti, non il più vecchio. La realizzazione standard è un heap binario: un albero memorizzato in un array in cui ogni nodo è minore dei suoi figli, quindi il minimo sta sempre in posizione 0. Inserire aggiunge in fondo e risale scambiando con il padre finché serve; estrarre sostituisce la radice con l'ultimo elemento e lo fa scendere. Il listato implementa lo heap contando i confronti e lo verifica contro heapq, sia con operazioni miste sia svuotandolo.

# Coda a priorita': heap binario minimo con confronti contati, verificato contro heapq
import heapq, random

class MinHeap:
    def __init__(self):
        self.a, self.comparisons = [], 0
    def _less(self, x, y):
        self.comparisons += 1
        return x < y
    def push(self, x):
        a = self.a; a.append(x); i = len(a) - 1
        while i > 0 and self._less(a[i], a[(i - 1) // 2]):       # risale finche' e' minore del padre
            a[i], a[(i - 1) // 2] = a[(i - 1) // 2], a[i]
            i = (i - 1) // 2
    def pop(self):
        a = self.a; top, last = a[0], a.pop()
        if a:
            a[0], i = last, 0
            while True:                                          # scende scambiando col figlio minore
                c = 2 * i + 1
                if c >= len(a):
                    break
                if c + 1 < len(a) and self._less(a[c + 1], a[c]):
                    c += 1
                if not self._less(a[c], a[i]):
                    break
                a[i], a[c] = a[c], a[i]; i = c
        return top

rng = random.Random(14)
for _ in range(500):                                             # operazioni miste, confronto con heapq
    h, ref = MinHeap(), []
    for _ in range(200):
        if ref and rng.random() < 0.4:
            assert h.pop() == heapq.heappop(ref)
        else:
            v = rng.randrange(1000); h.push(v); heapq.heappush(ref, v)
    assert [h.pop() for _ in ref] == [heapq.heappop(ref) for _ in range(len(ref))]
print("MinHeap coerente con heapq su 500 sequenze miste di push e pop")

class C:                                                         # heapify di heapq lavora in loco: una classe registra i confronti
    calls = 0
    def __init__(self, k): self.k = k
    def __lt__(self, o): C.calls += 1; return self.k < o.k

print(f"{'n':>6} {'n push (casuale)':>17} {'n push (decrescente)':>21} {'heapify di heapq':>17} | {'pop medio':>10} {'2 lg n':>7}")
for n in (1000, 10000):
    vals = rng.sample(range(10**6), n)
    h = MinHeap()
    for v in vals:
        h.push(v)
    c_random = h.comparisons
    h2 = MinHeap()
    for v in range(n, 0, -1):                                    # caso peggiore per l'inserimento: ogni nuovo e' il minimo
        h2.push(v)
    c_worst = h2.comparisons
    h.comparisons = 0
    for _ in range(n):
        h.pop()
    C.calls = 0
    arr = [C(v) for v in vals]
    heapq.heapify(arr)
    print(f"{n:>6} {c_random:>17} {c_worst:>21} {C.calls:>17} | {h.comparisons / n:>10.1f} {2 * (n.bit_length() - 1):>7}")

# parita' di priorita': un contatore d'arrivo nella tupla mantiene l'ordine FIFO fra elementi uguali
tasks, h, count = [("stampa", 2), ("backup", 1), ("mail", 2), ("log", 1)], [], 0
for name, prio in tasks:
    heapq.heappush(h, (prio, count, name)); count += 1
print("ordine di uscita:", [heapq.heappop(h)[2] for _ in range(len(tasks))])

# Output:
# MinHeap coerente con heapq su 500 sequenze miste di push e pop
#      n  n push (casuale)  n push (decrescente)  heapify di heapq |  pop medio  2 lg n
#   1000              2248                  7987              1639 |       15.0      18
#  10000             22703                113631             16443 |       21.7      26
# ordine di uscita: ['backup', 'log', 'stampa', 'mail']

I numeri hanno tre letture. Costruire un heap con n inserimenti costa circa 2,2 confronti per elemento su dati casuali (2.248 per n = 1.000), ma 7.987 se ogni nuovo elemento è il minimo (sequenza decrescente): è il caso peggiore dell'inserimento, vicino a n lg n. Costruirlo in un solo colpo con heapq.heapify costa meno di 2n confronti (1.639 contro 2.000), perché lavora dal basso: i nodi vicini alle foglie hanno poco da scendere. E ogni estrazione costa in media 15,0 confronti a n = 1.000 e 21,7 a n = 10.000, entro il limite 2·⌊lg n⌋ (18 e 26). Quindi inserire e togliere sono O(log n), e costruire da un elenco già pronto conviene.

L'ultima riga risolve un problema pratico: se due compiti hanno la stessa priorità, l'heap non garantisce che escano nell'ordine d'arrivo (la documentazione di heapq nota che l'ordinamento ottenuto con un heap non è stabile). La soluzione è quella raccomandata dalla documentazione: mettere nella tupla un contatore d'arrivo come secondo criterio. Nel listato «backup» e «log» (priorità 1) escono nell'ordine in cui sono arrivati, poi «stampa» e «mail» (priorità 2). Per i confronti fra elementi non confrontabili, il contatore evita anche l'errore di confronto fra i compiti stessi.

Strutture sincronizzate: queue.Queue fra thread

Quando più thread usano la stessa coda, lo stato condiviso va protetto. Il modulo queue della libreria standard fornisce code FIFO, LIFO e a priorità che, come dice la documentazione, implementano tutta la semantica di blocco necessaria. Il listato mette tre produttori e due consumatori su una coda limitata a otto posti, in un solo processo e senza aprire porte, e verifica che nessun elemento si perda o si duplichi.

# queue.Queue e' gia' sincronizzata: tre produttori e due consumatori nello stesso processo (nessuna rete, nessuna porta)
import queue, threading

q = queue.Queue(maxsize=8)                       # coda limitata: put() blocca se e' piena
results, lock = [], threading.Lock()
PRODUCERS, ITEMS = 3, 1000

def producer(pid):
    for i in range(ITEMS):
        q.put((pid, i))

def consumer():
    while True:
        item = q.get()
        if item is None:                         # sentinella: fine del lavoro
            q.task_done()
            return
        with lock:
            results.append(item)
        q.task_done()

consumers = [threading.Thread(target=consumer) for _ in range(2)]
producers = [threading.Thread(target=producer, args=(p,)) for p in range(PRODUCERS)]
for t in consumers + producers:
    t.start()
for t in producers:
    t.join()
for _ in consumers:
    q.put(None)
for t in consumers:
    t.join()

print("elementi consegnati:", len(results), "su", PRODUCERS * ITEMS)
print("nessuno perso ne' duplicato:", sorted(results) == sorted((p, i) for p in range(PRODUCERS) for i in range(ITEMS)))
# con DUE consumatori l'ordine di scrittura in 'results' non e' garantito; l'ordine di PRELIEVO invece si': lo si verifica con uno solo
q2 = queue.Queue()
for i in range(5):
    q2.put(i)
print("un solo consumatore, ordine di prelievo:", [q2.get() for _ in range(5)])

# Output:
# elementi consegnati: 3000 su 3000
# nessuno perso ne' duplicato: True
# un solo consumatore, ordine di prelievo: [0, 1, 2, 3, 4]

Due cose da notare. La coda ha una capienza massima (maxsize=8): quando è piena put blocca il produttore, e questo trasmette la pressione verso monte invece di far crescere la memoria senza limite. E l'ordine di prelievo è FIFO, ma l'ordine con cui due consumatori scrivono il risultato non è garantito: per questo il controllo confronta insiemi ordinati e non liste, e l'ordine di prelievo si verifica con un solo consumatore. Le code concorrenti di Java (BlockingQueue, ConcurrentLinkedQueue) hanno scopi analoghi, ma non le ho eseguite per questo articolo e non le descrivo.

Quale struttura scegliere

• Accesso per indice e inserimenti in coda: array dinamico (list), con accesso costante e append ammortizzato.
• Annulla, ricorsione, parsing: pila, ancora una list usata solo dalla fine.
• Elaborazione in ordine d'arrivo: collections.deque, mai list.pop(0).
• Sempre il più urgente per primo: heap, con heapq e un contatore d'arrivo per gli spareggi.
• Più thread: queue.Queue, con capienza limitata per trasmettere la pressione.

Le voci non sono alternative interscambiabili: ciascuna risponde a una domanda diversa sull'ordine in cui vuoi recuperare i dati. La domanda da farsi è sempre la stessa, prima di scegliere il nome: in che ordine voglio riavere ciò che metto dentro, e a quali estremità lavoro? La lista concatenata, che non compare nell'elenco, ha un posto solo quando hai già un cursore sul punto d'inserimento e non ti serve alcun accesso per indice.

Esercizi

1. Aggiungi a LinkedList un puntatore all'ultimo nodo e verifica che l'inserimento in coda costi zero salti.
2. Estendi il controllo delle parentesi per restituire la posizione del primo errore, e verificalo contro un riferimento a forza bruta.
3. Fai in modo che la coda a due pile riporti anche la lunghezza massima raggiunta dalla pila di uscita, e verifica che non superi mai il numero di elementi presenti nella coda.
4. Implementa un heap massimo cambiando il verso dei confronti e verificalo con heapq sui valori negati.

Il terzo esercizio rende visibile l'invariante della coda a due pile: la pila di uscita contiene gli elementi più vecchi in ordine di uscita, e una volta vuota si riempie solo travasando. Il quarto è un'abitudine da avere: in Python heapq offre solo il minimo, e il massimo si ottiene negando le chiavi.

Domande frequenti

Perché non usare list.pop(0) per una coda?

Perché ogni estrazione sposta tutti gli altri elementi: svuotare una coda di n elementi costa n(n − 1)/2 spostamenti. collections.deque estrae dalla testa a costo costante.

Una coda con due pile è davvero O(1)?

Lo è in media: ogni elemento viene travasato al più una volta, quindi i travasi totali non superano gli inserimenti. Un singolo estratto può però costare n, se la pila di uscita è vuota.

Come si mantiene l'ordine d'arrivo in una coda a priorità?

Si inserisce nell'heap una tupla (priorità, contatore d'arrivo, compito): a parità di priorità decide il contatore, che è lo spareggio indicato dalla documentazione di heapq.

Che cosa sai fare adesso

Sai dire quale struttura risponde a quale ordine di recupero, e sai motivarlo con un conteggio: spostamenti dell'array contro salti della lista, travasi ammortizzati della coda a due pile, confronti dell'heap. Hai scritto una deque circolare, hai visto perché pop(0) su una lista è un errore, e sai far uscire in ordine d'arrivo i compiti a pari priorità. Nell'articolo sugli alberi binari di ricerca e gli AVL la stessa idea di struttura nell'array lascia il posto ai puntatori, e l'heap ritorna come albero.

Nella stessa serie trovi anche il riepilogo sulla programmazione dinamica.