Come uno stack, la coda è una struttura di dati lineare che memorizza gli elementi in un First In First Out ( FIFO ) maniera. Con una coda, l'elemento aggiunto meno di recente viene rimosso per primo. Un buon esempio di coda è qualsiasi coda di consumatori per una risorsa in cui il consumatore arrivato per primo viene servito per primo.

Le operazioni associate alla coda sono:

• Accodare: Aggiunge un elemento alla coda. Se la coda è piena, si parla di condizione di Overflow – Complessità temporale: O(1)
• Di conseguenza: Rimuove un elemento dalla coda. Gli elementi vengono estratti nello stesso ordine in cui vengono inseriti. Se la coda è vuota, si parla di condizione di underflow – Complessità temporale: O(1)
• Davanti: Ottieni l'elemento in primo piano dalla coda – Complessità temporale: O(1)
• Posteriore: Ottieni l'ultimo elemento dalla coda – Complessità temporale: O(1)

Implementa una coda in Python

Esistono vari modi per implementare una coda in Pitone. Questo articolo tratta l'implementazione della coda utilizzando strutture dati e moduli della libreria Python. La coda Python può essere implementata nei seguenti modi:

• elenco
• collezioni.deque
• coda.coda

Implementazione utilizzando l'elenco

List è una struttura dati incorporata di Python che può essere utilizzata come coda. Invece di enqueue() e di conseguenza () , aggiungere() E pop() viene utilizzata la funzione. Tuttavia, le liste sono piuttosto lente per questo scopo perché l'inserimento o l'eliminazione di un elemento all'inizio richiede lo spostamento di uno di tutti gli altri elementi, richiedendo tempo O(n).
Il codice simula una coda utilizzando un elenco Python. Aggiunge elementi 'UN' , 'B' , E 'C' alla coda e poi li rimuove dalla coda, risultando in una coda vuota alla fine. L'output mostra la coda iniziale, gli elementi rimossi dalla coda ( 'UN' , 'B' , 'C' ) e lo stato vuoto della coda.

Python3

Produzione:

Initial queue ['a', 'b', 'c'] Elements dequeued from queue a b c Queue after removing elements [] 

Traceback (most recent call last):  File '/home/ef51acf025182ccd69d906e58f17b6de.py', line 25, in   print(queue.pop(0)) IndexError: pop from empty list 

Implementazione utilizzandocollection.deque

La coda in Python può essere implementata utilizzando la classe deque dal modulocollections. Deque è preferibile rispetto a list nei casi in cui abbiamo bisogno di operazioni di accodamento e pop più rapide da entrambe le estremità del contenitore, poiché deque fornisce una complessità temporale O(1) per le operazioni di accodamento e pop rispetto a list che fornisce una complessità temporale O(n) . Invece di enqueue e deque, vengono utilizzate le funzioni append() e popleft().
Il codice utilizza a deque> dal collections> modulo per rappresentare una coda. Si aggiunge 'UN' , 'B' , E 'C' alla coda e li rimuove dalla coda con q.popleft()> , risultando in una coda vuota. Senza commenti q.popleft()> dopo che la coda è vuota verrà generato un IndexError> . Il codice illustra le operazioni sulla coda e gestisce uno scenario di coda vuota.

Python3

Produzione:

Initial queue deque(['a', 'b', 'c']) Elements dequeued from the queue a b c Queue after removing elements deque([]) 

Traceback (most recent call last):  File '/home/b2fa8ce438c2a9f82d6c3e5da587490f.py', line 23, in   q.popleft() IndexError: pop from an empty deque 

Implementazione utilizzando tail.Queue

Queue è un modulo integrato di Python che viene utilizzato per implementare una coda. coda.Queue(maxsize) inizializza una variabile su una dimensione massima di maxsize. Una dimensione massima pari a zero '0' indica una coda infinita. Questa coda segue la regola FIFO.
In questo modulo sono disponibili diverse funzioni:

• maxsize – Numero di elementi consentiti nella coda.
• vuoto() – Restituisce True se la coda è vuota, False altrimenti.
• pieno() – Restituisce True se nella coda sono presenti elementi di dimensione massima. Se la coda è stata inizializzata con maxsize=0 (il valore predefinito), full() non restituisce mai True.
• Ottenere() – Rimuovere e restituire un elemento dalla coda. Se la coda è vuota, attendi finché un articolo non è disponibile.
• get_nowait() – Restituisce un elemento se è immediatamente disponibile, altrimenti solleva QueueEmpty.
• mettere (oggetto) – Metti un elemento in coda. Se la coda è piena, attendi che sia disponibile uno spazio libero prima di aggiungere l'articolo.
• put_nowait(oggetto) – Metti un elemento in coda senza bloccarlo. Se nessuno slot libero è immediatamente disponibile, rilancia QueueFull.
• qdimensione() – Restituisce il numero di elementi in coda.

Esempio: Questo codice utilizza il Queue> classe da queue> modulo. Inizia con una coda vuota e la riempie con ' UN', 'B' , E 'C' . Dopo la rimozione dalla coda, la coda si svuota e viene aggiunto '1'. Nonostante fosse vuota in precedenza, rimane piena, poiché la dimensione massima è impostata su 3. Il codice mostra le operazioni sulla coda, incluso il controllo del pieno e del vuoto.

Python3

Produzione:

0 Full: True Elements dequeued from the queue a b c Empty: True Empty: False Full: False