Implementazione della coda e deque
Costruisca una coda con deque di Python, implementi una coda circolare e risolva sliding-window-maximum usando una deque monotona
Implementazione della coda e deque è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 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 Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
La struttura dati coda
Una coda è una struttura dati FIFO, cioè «primo a entrare, primo a uscire». Il primo elemento accodato è il primo a essere rimosso, proprio come in una fila alla cassa. Le operazioni fondamentali sono enqueue (aggiungere in fondo) e dequeue (rimuovere dalla testa). Entrambe devono avere complessità O(1) perché la coda sia efficiente.
Usare una lista Python come coda è allettante, ma errato: list.pop(0) ha complessità O(n) perché sposta tutti gli elementi. Lo strumento corretto è collections.deque, che fornisce appendleft, append, popleft e pop in O(1).
from collections import deque
queue = deque()
# Enqueue (add to rear)
queue.append(10)
queue.append(20)
queue.append(30)
print('Queue:', queue) # deque([10, 20, 30])
# Peek front
print('Front:', queue[0]) # 10
# Dequeue (remove from front)
print('Dequeued:', queue.popleft()) # 10
print('Queue after:', queue) # deque([20, 30])Classe Queue con deque
Racchiuda deque in una classe Queue con operazioni denominate in modo esplicito, come si aspettano gli esaminatori. Internamente, enqueue chiama append e dequeue chiama popleft. L'operazione peek legge queue[0] senza rimuoverlo.
from collections import deque
class Queue:
def __init__(self):
self._data = deque()
def enqueue(self, val):
self._data.append(val)
def dequeue(self):
if self.is_empty():
raise IndexError('dequeue from empty queue')
return self._data.popleft()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty queue')
return self._data[0]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
q = Queue()
q.enqueue(1); q.enqueue(2); q.enqueue(3)
print(q.peek()) # 1
print(q.dequeue()) # 1
print(len(q)) # 2BFS con una coda
L'applicazione classica di una coda è la ricerca in ampiezza (BFS). Si accoda la radice; finché la coda non è vuota, si rimuove un nodo, lo si elabora e si accodano i suoi vicini non ancora visitati. Poiché i nodi vengono elaborati livello per livello, la BFS trova naturalmente il cammino più breve in un grafo non pesato. La coda contiene sempre nodi appartenenti al massimo a due livelli adiacenti.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
return order
graph = {0:[1,2], 1:[0,3,4], 2:[0,5], 3:[1], 4:[1], 5:[2]}
print(bfs(graph, 0)) # [0, 1, 2, 3, 4, 5]Coda circolare (LeetCode 622)
LeetCode 622 'Design Circular Queue': implementare una coda a capacità fissa che si riavvolge su se stessa. Si usa un array di dimensione k e due puntatori: head e tail. Si accoda in corrispondenza di tail, si rimuove in corrispondenza di head e si calcolano le posizioni modulo k. Una variabile count distingue la coda piena da quella vuota (in entrambi i casi head == tail modulo k, altrimenti).
class MyCircularQueue:
def __init__(self, k):
self.data = [0] * k
self.head = 0
self.tail = 0
self.count = 0
self.k = k
def enQueue(self, value):
if self.isFull(): return False
self.data[self.tail] = value
self.tail = (self.tail + 1) % self.k
self.count += 1
return True
def deQueue(self):
if self.isEmpty(): return False
self.head = (self.head + 1) % self.k
self.count -= 1
return True
def Front(self):
return -1 if self.isEmpty() else self.data[self.head]
def Rear(self):
return -1 if self.isEmpty() else self.data[(self.tail - 1) % self.k]
def isEmpty(self): return self.count == 0
def isFull(self): return self.count == self.k
cq = MyCircularQueue(3)
print(cq.enQueue(1), cq.enQueue(2), cq.enQueue(3)) # True True True
print(cq.enQueue(4)) # False (full)
print(cq.Rear()) # 3
print(cq.isFull()) # True
print(cq.deQueue()) # True
print(cq.enQueue(4)) # TrueMassimo in una finestra scorrevole con deque monotono
LeetCode 239 'Sliding Window Maximum': per ogni finestra di dimensione k, trovare l'elemento massimo. L'approccio esaustivo richiede O(n*k). L'approccio O(n) usa un deque monotono decrescente che memorizza gli indici. Per ogni nuovo elemento: si rimuovono dalla testa gli indici esterni alla finestra; si rimuovono dalla coda gli indici con valori più piccoli (non potranno mai essere il massimo in una finestra futura). In testa si trova sempre il massimo.
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove smaller elements from back
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]Perché usare deque invece di una semplice lista per una coda?
list.pop(0) di Python rimuove il primo elemento in O(n), perché ogni elemento rimanente deve spostarsi di una posizione verso sinistra. Con n inserimenti e n rimozioni, il costo totale è O(n²). collections.deque è una lista doppiamente concatenata di blocchi di dimensione fissa; popleft ha complessità O(1) perché modifica soltanto un puntatore. Nella BFS di un grafo con 10^5 nodi, la differenza tra O(n) e O(n²) equivale alla differenza tra 100 ms e 100 secondi.
import timeit
n = 10000
# Using list (O(n) per popleft)
list_time = timeit.timeit(
stmt='q = list(range(n)); [q.pop(0) for _ in range(n)]',
globals={'n': n}, number=10
)
# Using deque (O(1) per popleft)
from collections import deque
deque_time = timeit.timeit(
stmt='q = deque(range(n)); [q.popleft() for _ in range(n)]',
globals={'n': n, 'deque': deque}, number=10
)
print(f'List: {list_time:.4f}s')
print(f'Deque: {deque_time:.4f}s')
print(f'Speedup: {list_time / deque_time:.1f}x')Visita di un albero binario per livelli (LeetCode 102)
LeetCode 102 'Binary Tree Level Order Traversal': restituire tutti i valori dei nodi livello per livello. Si usa una coda; all'inizio di ogni livello si registra la dimensione della coda, che indica quanti nodi appartengono a quel livello. Si rimuovono esattamente quel numero di nodi, raccogliendone i valori e accodandone i figli. Si ripete finché la coda non è vuota.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(levelOrder(root)) # [[3], [9, 20], [15, 7]]Coda con priorità usando heapq
Il modulo heapq di Python fornisce un min-heap (coda con priorità): l'elemento più piccolo viene sempre estratto per primo. heapq.heappush(h, item) aggiunge un elemento in O(log n) e heapq.heappop(h) rimuove il minimo in O(log n). Per attività come l'algoritmo di Dijkstra e i problemi top-k, heapq sostituisce la coda semplice.
import heapq
pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
heapq.heappush(pq, 2)
print('Min:', heapq.heappop(pq)) # 1
print('Min:', heapq.heappop(pq)) # 2
print('Min:', heapq.heappop(pq)) # 3
# Tasks with priorities
tasks = [(2, 'send email'), (1, 'fix bug'), (3, 'write docs')]
heapq.heapify(tasks)
while tasks:
priority, task = heapq.heappop(tasks)
print(f'Priority {priority}: {task}')Pattern ricorrente: coda per Word Ladder
LeetCode 127 «Word Ladder»: determini il numero minimo di sostituzioni di un singolo carattere necessarie per trasformare una parola in un'altra, usando solo parole presenti nel dizionario. Modelli il problema come un grafo in cui gli archi collegano le parole che differiscono per un carattere. L'attraversamento BFS di questo grafo trova il percorso più breve (il numero minimo di passaggi) in O(n * L²), dove n è la dimensione del dizionario e L è la lunghezza delle parole.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
word_set = set(wordList)
if endWord not in word_set:
return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for ch in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + ch + word[i+1:]
if new_word == endWord:
return steps + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, steps + 1))
return 0
print(ladderLength('hit', 'cog', ['hot','dot','dog','lot','log','cog'])) # 5deque come coda a doppia estremità
collections.deque è una coda a doppia estremità (deque): consente di aggiungere e rimuovere elementi in modo efficiente da entrambe le estremità. Metodi: appendleft e popleft per l'estremità anteriore; append e pop per quella posteriore. Questo consente a deque di fungere sia da coda FIFO (appendright + popleft) sia da pila LIFO (append + pop). Il massimo in una finestra scorrevole usa entrambe le estremità: rimuove gli indici obsoleti da sinistra e i valori più piccoli da destra.
from collections import deque
dq = deque([3, 4, 5])
dq.appendleft(2) # add to front: [2,3,4,5]
dq.appendleft(1) # add to front: [1,2,3,4,5]
dq.append(6) # add to rear: [1,2,3,4,5,6]
print(dq.popleft()) # 1 (from front)
print(dq.pop()) # 6 (from rear)
print(list(dq)) # [2, 3, 4, 5]Riepilogo: coda vs deque vs heap
Scelga lo strumento adatto al problema. Utilizzi una coda semplice (deque) per l'elaborazione FIFO e la BFS. Utilizzi una deque monotona quando deve trovare il massimo o il minimo in una finestra scorrevole: mantiene un invariante ordinato rimuovendo gli elementi dominati. Utilizzi una coda con priorità (heapq) quando serve il minimo o il massimo globale indipendentemente dall'ordine, ad esempio nei problemi di Dijkstra o top-k. Sapere quale strumento scegliere e perché è una competenza fondamentale verificata durante i colloqui tecnici.
Verifica rapida
Verifichi la sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha appreso che: collections.deque fornisce operazioni di accodamento e rimozione in O(1), rendendola l'implementazione corretta di una coda in Python, la BFS usa una coda per elaborare i nodi livello per livello, trovando i percorsi più brevi nei grafi non pesati e una deque monotona decrescente risolve il problema del massimo in una finestra scorrevole in O(n), rimuovendo gli indici dominati. Nella prossima lezione esamineremo in dettaglio il pattern della pila monotona.
Domande Frequenti
La lezione «Implementazione della coda e deque» è gratuita?
Sì — il testo completo di «Implementazione della coda e 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 Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Implementazione della coda e deque»?
Costruisca una coda con deque di Python, implementi una coda circolare e risolva sliding-window-maximum usando una deque monotona Eserciti Coding Interview Prep 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 Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Implementazione della coda e 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 Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep 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
- Implementazione e applicazioni dello stack
- Implementazione della coda e deque
- Schema dello stack monotono
- Simulazione reciproca di stack e coda