CKTIS / Python
`deque.pop()` — usuwanie elementu z prawego końca kolejki
`deque.pop()` usuwa i zwraca skrajny prawy element kolejki dwustronnej. Służy między innymi do odrzucania zdominowanych kandydatów na maksimum w oknie przesuwnym.
Wersja: Python 3.12
Składnia
d.pop()collections.deque.pop to metoda instancji kolejki dwustronnej deque. Wywołanie d.pop() nie przyjmuje argumentów: usuwa skrajny prawy element z d i zwraca właśnie ten element. Pusta kolejka powoduje zgłoszenie IndexError. Odczyt d[-1] nie usuwa elementu, a d.popleft() usuwa i zwraca element z lewego końca. Usuwanie z każdego z końców kolejki deque ma koszt około O(1).
list.pop() bez argumentu również usuwa i zwraca ostatni element, ale metoda listy przyjmuje opcjonalny indeks. deque.pop() nie przyjmuje indeksu: do usuwania z lewej strony kolejki użyj d.popleft(), a nie d.pop(0).
Przy wyznaczaniu maksimum w oknie przesuwnym nowszy kandydat o wartości co najmniej tak dużej jak starszy pozostanie w oknie dłużej. Starszy kandydat jest więc zdominowany. Warunek while candidates and candidates[-1] <= incoming sprawdza, czy kolejka nie jest pusta, zanim odczyta prawy element. Pętla usuwa zdominowanych kandydatów od prawej, po czym append() dopisuje nową wartość po prawej stronie. Przykład pokazuje tylko usuwanie z prawej. Wariant oparty na indeksach przechowuje indeksy kandydatów i na ich podstawie usuwa z lewego końca kolejki tych, którzy wypadli z okna.
Przykłady
from collections import deque
candidates = deque([9, 6, 3])
incoming = 7
removed = []
while candidates and candidates[-1] <= incoming:
removed.append(candidates.pop())
candidates.append(incoming)
print(removed)
print(list(candidates))Wynik
[3, 6] [9, 7]
Pętla usuwa najpierw `3`, a potem `6`, i zatrzymuje się na `9`. Po dopisaniu `7` program wypisuje `[3, 6]` oraz `[9, 7]` w osobnych wierszach.
Powiązane lekcje
- Python · Lekcja 41 · Zaawansowany · Wersja: 5