Code e collections.deque
Inserire ed estrarre rapidamente da entrambe le estremità
Code e collections.deque è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Primo entrato, primo uscito
Una queue serve gli elementi nell'ordine in cui sono arrivati, come una fila in un negozio. Il primo a entrare è il primo a uscire.
Perché non usare una list
Una list può estrarre un elemento dall'inizio, ma pop(0) richiede O(n), perché ogni altro elemento viene spostato a sinistra. È troppo lento per input di grandi dimensioni.
q = []
q.pop(0) # O(n), avoid thisIncontrare collections.deque
Il deque di collections è una coda a doppia estremità che consente di aggiungere e rimuovere elementi da entrambe le estremità in O(1). È la scelta preferita nelle gare di programmazione.
from collections import deque
q = deque()Accodare in fondo
Aggiunga i nuovi elementi all'estremità destra con append, proprio come farebbe con una list. Questa è la parte posteriore della coda.
q.append(1)
q.append(2)Rimuovere dalla parte anteriore
Rimuova l'elemento più vecchio da sinistra con popleft, che viene eseguito in tempo costante e garantisce il comportamento FIFO.
first = q.popleft() # returns 1Entrambe le estremità sono accessibili
Un deque supporta anche appendleft e pop a destra. Questa flessibilità consente a un'unica struttura di comportarsi come stack o come queue.
q.appendleft(0)
last = q.pop()Controllare prima di rimuovere
Rimuovere un elemento da un deque vuoto genera un errore, quindi nei cicli verifichi while q per mantenere sicura la visita.
while q:
x = q.popleft()Le queue alimentano la BFS
L'uso più comune nelle gare di programmazione è la BFS. Inserisca un nodo iniziale nella queue, quindi continui a estrarre l'elemento in testa e a inserire i suoi vicini.
Un piccolo scheletro BFS
Questo ciclo visita i nodi livello per livello. Ogni vicino viene aggiunto e poi elaborato nell'ordine di arrivo.
while q:
node = q.popleft()
for nb in graph[node]:
q.append(nb)Limitare la dimensione del deque
Specificare maxlen fa sì che un deque elimini l'elemento più vecchio quando è pieno, una soluzione perfetta per finestre scorrevoli e per tenere traccia della cronologia recente.
window = deque(maxlen=3)Una struttura, molti ruoli
Ricordi che deque è veloce su entrambe le estremità, quindi lo scelga ogni volta che le serve una queue, uno stack o un buffer scorrevole.
Verifica rapida
Le serve rimuovere rapidamente elementi dalla parte anteriore di una queue. Quale scelta è corretta?
Riepilogo: deque è la queue veloce
Ha incontrato collections.deque: append e popleft per operazioni FIFO in O(1), accesso a entrambe le estremità e maxlen per le finestre. È la struttura portante della BFS. 🎯
Domande Frequenti
La lezione «Code e collections.deque» è gratuita?
Sì — il testo completo di «Code e collections.deque» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Code e collections.deque»?
Inserire ed estrarre rapidamente da entrambe le estremità Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Code e collections.deque»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Stack per le parentesi corrispondenti
- Stack monotono: elemento successivo maggiore
- Code e collections.deque
- Massimo di una finestra scorrevole con Deque