Algoritmi Python

Queue Data Structure in Python with deque

First in, first out: serve items in arrival order with collections.deque, fast at both ends.

Intermedio
2 min di lettura
1 esempio eseguibile

Cosa imparerai

append() and popleft() on a deque
Why list.pop(0) is slow
Where queues are used

Esegui nel compilatore Python →

deque(["first", "second", "third"])

firstfront

second

thirdback

↑ popleft() serves "first"

Join at the back, leave from the front

La coda (queue) segue la regola primo a entrare, primo a uscire (FIFO), come la fila alla cassa: chi arriva per primo viene servito per primo. Le code si usano per programmare l'esecuzione dei compiti e nell'algoritmo di ricerca in ampiezza (BFS).

Punti chiave

queue.append(x) adds to the back.
queue.popleft() removes from the front in O(1).
list.pop(0) must shift every element, so it is O(n).
Queues drive task scheduling and breadth-first search.

Quando si usa?

Allenare il ragionamento per risolvere problemi e capire come funziona un algoritmo passo dopo passo.
Scegliere la soluzione giusta quando devi elaborare molti dati o rendere il programma più veloce.
Prepararti a esami, esercizi e colloqui di programmazione.

Guarda come funziona

Fai enqueue e dequeue per vedere che gli elementi escono nello stesso ordine in cui sono arrivati.

Codice di esempio

Esegui codice →

main.py

from collections import deque

queue = deque(["first", "second"])
queue.append("third")

print("served:", queue.popleft())
print("waiting:", list(queue))

Crea un pulsante Run per questo esempio

Risultato dell'esecuzione

served: first
waiting: ['second', 'third']

Spiegazione del codice

deque permette di aggiungere elementi a destra con append() e di estrarli da sinistra con popleft(), entrambi in O(1). Con una lista normale, eliminare il primo elemento costa O(n), perché tutti gli elementi successivi devono spostarsi, quindi deque è la scelta giusta per le code.

Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.

Esercizi di approfondimento

Prova a modificare il codice seguendo i suggerimenti qui sotto. Cambiare il codice e osservare il risultato ti aiuta a capire molto più che leggerlo soltanto.

Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.

Esegui nel compilatore Python →

Esercitati con una sfida

Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.

Tutte le sfide