Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

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

Zdroje