In informatica, una coda è una struttura di dati, usata per immagazzinare elementi, prima che vengano elaborati. Generalmente la coda segue la politica FIFO (First In, First Out): l'elemento inserito per primo viene rimosso per primo. In genere, le operazioni principali sono:

  • Enqueue: aggiunge un elemento in coda (alla fine).
  • Dequeue: rimuove e restituisce l'elemento in testa alla coda (l'elemento più vecchio).
  • Peek (o Front): opzionalmente, guarda l'elemento in testa senza rimuoverlo.
  • isEmpty: verifica se la coda è vuota.
  • size: restituisce il numero di elementi presenti.

Gli elementi che si trovano tra il primo e l'ultimo elemento della coda non sono direttamente accessibili: per raggiungerli bisogna rimuovere quelli davanti (rispettando la politica FIFO).

Implementazioni comuni e complessità

  • Lista collegata: una lista collegata singolarmente con puntatori a testa e coda permette enqueue e dequeue in tempo O(1) costante, senza spostamenti di memoria.
  • Array circolare (ring buffer): utile per code con capacità limitata; permette operazioni O(1) e usa lo spazio in modo efficiente evitando lo spostamento degli elementi.
  • Array dinamico: implementazioni semplici possono usare un array che cresce; talvolta le operazioni possono avere costo ammortizzato O(1) per l'enqueue, ma richiedere copie quando l'array viene riallocato.
  • Heap o struttura ordinata: usato per code di priorità (vedi sotto), con complessità tipica O(log n) per inserimento e rimozione del massimo/minimo.

Varianti

  • Deque (double-ended queue): struttura che consente inserimenti e rimozioni sia in testa sia in coda.
  • coda di priorità: ogni elemento ha una priorità (peso) che determina l'ordine di rimozione. Non necessariamente segue FIFO: l'elemento con priorità più alta viene rimosso prima. Implementazioni comuni includono heap binari, heap binomiale, Fibonacci heap, o strutture bilanciate che consentono operazioni efficienti.
  • Queue bloccante (blocking queue): in ambito concorrente, una coda che sospende (blocca) l'operazione di enqueue quando è piena o l'operazione di dequeue quando è vuota, riprendendo l'esecuzione quando la condizione cambia. Utile per producer-consumer e pipeline.
  • Coda stabile vs instabile: nelle code di priorità la stabilità indica se elementi con la stessa priorità mantengono l'ordine relativo di inserimento. Alcune implementazioni preservano questa proprietà, altre no.

Applicazioni pratiche

  • Scheduling di processi e job (coda di esecuzione, scheduler).
  • Buffering: stampanti, gestione dei messaggi, code di rete.
  • Algoritmi sui grafi: ad esempio Breadth-First Search (BFS) usa una coda FIFO.
  • Comunicazione tra thread o componenti (producer-consumer pattern).
  • Implementazione di servizi in tempo reale o a priorità con code di priorità per decidere l'ordine di servizio.

Considerazioni implementative

  • Thread-safety: per l'uso concorrente è necessario sincronizzare l'accesso (mutex, lock-free, atomic operations) o usare implementazioni già thread-safe.
  • Capacità limitata: alcune code hanno capacità fissa (bounded queues) e richiedono politiche per il caso di overflow (rifiuto, sovrascrittura, blocco).
  • Scelte di prestazioni: per esigenze real-time o ad alto throughput si preferiscono strutture con operazioni O(1) e basso overhead di allocazione; per esigenze di priorità si bilancia il costo logaritmico con i benefici dell'ordinamento.

In sintesi, la coda è una struttura semplice ma fondamentale, con numerose varianti e implementazioni adatte a differenti scenari: dalla gestione sequenziale di attività (FIFO) alle code di priorità che ordinano gli elementi per importanza.