CKTIS / Python
`deque.pop()` — odobratie prvku z pravého konca
`deque.pop()` odoberie a vráti prvok z pravého konca obojstranného frontu. Hodí sa na vyradenie dominovaných kandidátov pri hľadaní maxima v posuvnom okne.
Verzia: Python 3.12
Syntax
d.pop()collections.deque.pop je metóda inštancie obojstranného frontu deque. Volanie d.pop() neprijíma žiadne argumenty: odoberie prvok priamo z pravého konca frontu d a vráti ho. Ak je front prázdny, vyvolá IndexError. Výraz d[-1] prvok iba prečíta, zatiaľ čo d.popleft() odoberie a vráti prvok z ľavého konca. Odobratie prvku z ktoréhokoľvek konca trvá približne O(1).
list.pop() bez argumentu tiež odoberie a vráti posledný prvok, ale metóda zoznamu prijíma voliteľný index. deque.pop() index neprijíma: na odobratie z ľavého konca použi d.popleft(), nie d.pop(0).
Pri hľadaní maxima v posuvnom okne zostáva novší kandidát s hodnotou aspoň takou veľkou, akú má starší kandidát, v okne dlhšie. Starší kandidát je preto dominovaný. Podmienka while candidates and candidates[-1] <= incoming najprv overí, že front nie je prázdny, a až potom prečíta prvok vpravo. Cyklus odoberá dominovaných kandidátov sprava a potom append() pridá novú hodnotu na pravý koniec. Príklad ukazuje iba odoberanie sprava. Variant založený na indexoch si ukladá indexy kandidátov a podľa nich zľava odoberá tých, ktorí už vypadli z okna.
Prí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ýsledok
[3, 6] [9, 7]
Cyklus odoberie najprv `3`, potom `6` a zastaví sa pri `9`. Po pridaní `7` program vypíše `[3, 6]` a `[9, 7]` na samostatné riadky.
Súvisiace lekcie
- Python · Lekcia 41 · Pokročilá · Verzia: 5