CKTIS / Python
Usuwanie elementu z lewego końca: deque.popleft()
`popleft()` usuwa i zwraca pierwszy element kolejki dwustronnej. W oknie przesuwnym pozwala usuwać indeksy, które znalazły się przed jego lewą granicą.
Wersja: Python 3.12
Składnia
removed = d.popleft()collections.deque.popleft to metoda obiektu deque. Wywołanie d.popleft() nie przyjmuje argumentów: usuwa skrajny lewy element z d i go zwraca. Dla pustej kolejki zgłasza IndexError. Wyrażenie d[0] tylko odczytuje pierwszy element, a d.pop() usuwa i zwraca element z prawego końca.
Usunięcie elementu z lewego końca ma koszt w przybliżeniu O(1). Dla porównania list.pop(0) ma koszt O(n), ponieważ pozostałe elementy listy trzeba przesunąć.
Jeśli indeksy w kolejce są uporządkowane rosnąco, w oknie przesuwnym usuwaj pierwszy indeks, dopóki d[0] < left, gdzie left to lewa granica włącznie. Warunek while d and d[0] < left nie odczytuje d[0], gdy kolejka jest pusta. Indeks równy left pozostaje w oknie. Jeśli inny wątek może zmienić d, osobne sprawdzenie i usunięcie nie stanowią jednej operacji atomowej.
Przykłady
from collections import deque
d = deque([0, 2, 3, 5])
left = 3
while d and d[0] < left:
removed = d.popleft()
print(removed)
print(list(d))Wynik
0 2 [3, 5]
Dla `left = 3` pętla wypisuje kolejno usunięte indeksy `0` i `2`, a następnie pozostałą zawartość: `[3, 5]`.
Powiązane lekcje
- Python · Lekcja 41 · Zaawansowany · Wersja: 5