CKTIS / Python
`deque.pop()` — odebrání prvku z pravého konce
`deque.pop()` odebere a vrátí prvek z pravého konce oboustranné fronty. Hodí se k vyřazení dominovaných kandidátů při hledání maxima v posuvném okně.
Verze: Python 3.12
Syntaxe
d.pop()collections.deque.pop je metoda instance oboustranné fronty deque. Volání d.pop() nepřijímá žádné argumenty: odebere prvek přímo z pravého konce fronty d a vrátí ho. Je-li fronta prázdná, vyvolá IndexError. Výraz d[-1] prvek pouze přečte, zatímco d.popleft() odebere a vrátí prvek z levého konce. Odebrání prvku z kteréhokoli konce trvá přibližně O(1).
list.pop() bez argumentu také odebere a vrátí poslední prvek, ale metoda seznamu přijímá volitelný index. deque.pop() index nepřijímá: k odebrání z levého konce použij d.popleft(), nikoli d.pop(0).
Při hledání maxima v posuvném okně zůstane novější kandidát s hodnotou alespoň tak velkou, jakou má starší kandidát, v okně déle. Starší kandidát je proto dominovaný. Podmínka while candidates and candidates[-1] <= incoming nejprve ověří, že fronta není prázdná, a teprve potom přečte prvek vpravo. Smyčka odebírá dominované kandidáty zprava a poté append() přidá novou hodnotu na pravý konec. Příklad ukazuje pouze odebírání zprava. Varianta založená na indexech si ukládá indexy kandidátů a podle nich zleva odebírá ty, kteří už z okna vypadli.
Příklady
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))Výsledek
[3, 6] [9, 7]
Smyčka odebere nejprve `3`, potom `6` a zastaví se u `9`. Po přidání `7` program vypíše `[3, 6]` a `[9, 7]` na samostatné řádky.
Související lekce
- Python · Lekce 41 · Pokročilá · Verze: 5