Una guida per principianti per comprendere le code e le code prioritarie

Come programmatore, lavorerai con diverse strutture di dati a seconda dell'ambito dei tuoi progetti. Un tale concetto è una struttura di dati di coda; le code sono essenziali per gli studenti e vengono utilizzate in molti algoritmi importanti. Come le code, le code prioritarie condividono un concetto simile ma presentano alcune differenze fondamentali.

Continua a leggere per capire le code e le code prioritarie.

Che cos'è una coda?

Una coda è una semplice struttura di dati che ha una varietà di applicazioni in progetti di codifica reali. Le strutture di dati sono intrinsecamente astratte, ma per semplicità immaginiamo che una struttura di dati di coda abbia una forma lineare con due estremità diverse.

In termini di complessità temporale, una coda consente l'inserimento (accodamento) e la cancellazione (dequeue) in tempo O(1). A causa della sua efficienza asintotica, le code sono efficienti per set di dati di grandi dimensioni. Le code sono di natura FIFO (first-in-first-out), il che significa che si accederà per primo a un elemento di dati inserito per primo. Al contrario, gli stack hanno una natura di last-in-first-out (LIFO) e hanno solo un'estremità aperta.

Immagina una coda per i biglietti al cinema; ogni nuovo cliente che arriva si unisce alla coda a un'estremità. Uno per uno, ogni cliente acquista un biglietto e lascia la coda dal front-end. La struttura dei dati della coda funziona esattamente come qualsiasi coda del mondo reale e i dati vengono inseriti (accodati) a un'estremità e rimossi (rimuovi dalla coda) all'altra estremità. Ora puoi sperare di capire il motivo per cui le code seguono una metodologia FIFO.

Una coda ha molte applicazioni di codifica nella vita reale. È più comunemente utilizzato nelle applicazioni in cui i dati non devono essere elaborati immediatamente, ma piuttosto in un ordine FIFO. La pianificazione del disco, il trasferimento asincrono dei dati, i semafori sono alcune applicazioni tipiche. Anche le attività di pianificazione in ordine di arrivo, come lo spooling di stampa oi buffer dei dispositivi di input, utilizzano una coda.

Che cos'è una coda prioritaria?

Una coda prioritaria è simile a una coda, ma ha proprietà aggiuntive. Quando un elemento di dati viene accodato nella coda di priorità, gli viene assegnato un numero di priorità. Contrariamente alla rimozione dalla coda di una coda standard, gli elementi di dati con priorità alta vengono rimossi dalla coda prima degli elementi di dati con priorità bassa. La priorità sostituisce l'ordine di arrivo in una coda prioritaria, motivo per cui le code prioritarie non hanno una natura FIFO coerente.

Imparentato: Algoritmi che ogni programmatore dovrebbe conoscere

I programmatori possono implementare una coda prioritaria in diversi modi. Un'implementazione semplice consiste nell'utilizzare un array con un elemento di dati struct/class e l'elemento di dati conterrà la priorità di ciascun elemento di dati e i dati stessi. Un'altra implementazione primitiva della coda di priorità consiste nell'utilizzare un elenco collegato. Le code prioritarie implementate tramite elenchi collegati sono funzionali ma non ideali a causa delle loro prestazioni.

Puoi implementare una coda con priorità migliore con un mucchio. Se ricordi, gli heap binari danno l'elemento massimo o minimo in 0 (1) tempo e l'inserimento richiede solo 0 (logN) tempo. Con l'aiuto degli heap, le code con priorità offrono prestazioni migliori in modo asintotico rispetto alle code o agli array.

Una coda prioritaria ha anche una varietà di applicazioni essenziali. Le code prioritarie sono cruciali negli algoritmi grafici come il Minimum Spanning Tree di Prim e l'algoritmo Shortest Path di Dijkstra. Sono ideali anche negli algoritmi di pianificazione del processo delle unità di elaborazione del computer (CPU).

Impara le strutture dei dati

Le code e le code prioritarie sono strutture dati importanti per tutti i principianti. È fondamentale che gli studenti si sentano a proprio agio nell'implementare queste strutture di dati e nell'utilizzarle in diversi progetti.

Altre strutture di dati come heap, stack e alberi sono ugualmente importanti per studenti e professionisti. È anche molto comune che gli intervistatori interroghino i candidati sulle strutture di dati.

Dopo aver letto questo articolo, ora dovresti avere una buona idea di come funzionano le code e le code prioritarie. Se tutto sembra ancora un po' poco chiaro, farai i conti con questi man mano che acquisirai più esperienza nell'usarli.

Cumuli vs. Stack: cosa li distingue?

Hai sentito parlare di cumuli e pile, ma quando dovresti usarne uno sull'altro?

Leggi Avanti

Circa l'autore