IndexError: pop from an empty deque
Ai apelat coada.popleft() (sau pop()) pe un deque gol: bucla a continuat după ce coada s-a golit, sau ai scos de două ori pentru un singur element pus. Folosește while coada: și scoate un singur element pe iterație.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
deque.popleft() scoate primul element al cozii, iar deque.pop() ultimul. Pe o coadă goală amândouă aruncă IndexError: pop from an empty deque.
La BFS bucla corectă este while coada:, care se oprește singură când nu mai sunt noduri de procesat. Eroarea apare când condiția buclei e alta (while True, while len(rezultat) < n, for _ in range(n)) și coada se golește mai devreme decât te așteptai, de exemplu pentru că graful nu e conex. Sau când faci două popleft() într-o iterație (unul ca să citești, altul ca să scoți).
În simulări (coada de la casă, procese care așteaptă), coada goală înseamnă de obicei „nu e nimeni de servit”: tratează explicit acest caz.
De ce apare: cauzele frecvente
1Bucla nu se oprește când coada e goală
ordine = []
while len(ordine) < len(graf):
nod = coada.popleft()
ordine.append(nod)ordine = []
while coada:
nod = coada.popleft()
ordine.append(nod)Dacă unele noduri nu se pot atinge din start, ordine nu ajunge niciodată la len(graf), iar coada se golește. while coada se oprește corect.
2Două scoateri pentru un element
while coada:
if coada.popleft() == tinta:
break
nod = coada.popleft()while coada:
nod = coada.popleft()
if nod == tinta:
breakFiecare popleft() scoate un element. Citește elementul o dată, într-o variabilă; pentru „uită-te fără să scoți” folosește coada[0].
Repară eroarea, direct în pagină
Funcția ordine_bfs(graf, start) returnează nodurile în ordinea BFS, dar pe graful cu un nod izolat dă IndexError: pop from an empty deque. Repar-o ca să afișeze [1, 2, 3, 4] și [1, 2] (nodul 3 nu se poate atinge).
from collections import deque
def ordine_bfs(graf, start):
ordine = []
vazut = {start}
coada = deque([start])
while len(ordine) < len(graf):
nod = coada.popleft()
ordine.append(nod)
for v in graf[nod]:
if v not in vazut:
vazut.add(v)
coada.append(v)
return ordine
print(ordine_bfs({1: [2, 3], 2: [4], 3: [], 4: []}, 1))
print(ordine_bfs({1: [2], 2: [1], 3: []}, 1))[1, 2, 3, 4] [1, 2]
Indiciu
Bucla trebuie să ruleze cât timp coada mai are noduri, nu până se vizitează tot graful.
Reparația
from collections import deque
def ordine_bfs(graf, start):
ordine = []
vazut = {start}
coada = deque([start])
while coada:
nod = coada.popleft()
ordine.append(nod)
for v in graf[nod]:
if v not in vazut:
vazut.add(v)
coada.append(v)
return ordine
print(ordine_bfs({1: [2, 3], 2: [4], 3: [], 4: []}, 1))
print(ordine_bfs({1: [2], 2: [1], 3: []}, 1))De ce merge
Pe al doilea graf, nodul 3 nu are legătură cu 1 și 2, deci ordine nu ajunge niciodată la 3 elemente. Codul stricat continua bucla și după ce coada se golise, iar popleft() pe coada goală arunca eroarea. while coada oprește BFS-ul exact când nu mai sunt noduri descoperite de procesat, oricât de mare ar fi graful.
Alte forme ale mesajului
IndexError: pop from empty listIndexError: deque index out of range
Cum o eviți pe viitor
La BFS și la simulări cu coadă, condiția buclei este while coada:. Scoate exact un element pe iterație și salvează-l într-o variabilă. Dacă ai nevoie de procesare pe niveluri, ia for _ in range(len(coada)) la începutul nivelului: lungimea e calculată o singură dată. Pentru a vedea primul element fără să-l scoți, folosește coada[0] după ce ai verificat că nu e goală.
Întrebări frecvente
Mesajul e diferit de cel de la liste?
Da: la liste e pop from empty list, la deque pop from an empty deque. Cauza și reparația sunt aceleași.
Cum procesez BFS-ul pe niveluri fără eroarea asta?
La începutul fiecărui nivel salvează n = len(coada) și fă exact n scoateri. Elementele adăugate în timpul nivelului vor fi procesate la nivelul următor.
Erori înrudite
IndexError: pop from empty list Ai apelat stiva.pop() pe o stivă goală. La verificarea parantezelor înseamnă de obicei o paranteză închisă fără pereche. Verifică înainte cu if not stiva: (și tratează cazul) sau pune condiția în while stiva and ... AttributeError: 'list' object has no attribute 'popleft' popleft() există doar la collections.deque, nu la liste. Creează coada cu from collections import deque și coada = deque([start]); lista.pop(0) ar merge, dar e O(n) la fiecare scoatere. BFS-ul nu se mai oprește pe un graf cu ciclu (lipsesc nodurile vizitate) BFS-ul pune în coadă vecinii fără să verifice dacă au mai fost descoperiți, iar pe un graf cu ciclu (sau neorientat) aceleași noduri intră în coadă la nesfârșit; editorul oprește programul după limita de timp. Marchează nodul ca vizitat când îl pui în coadă. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
