CKTIS / Python
`deque.pop()` — odstranjevanje elementa z desnega konca
`deque.pop()` odstrani in vrne skrajni desni element dvostranske vrste. Uporabna je za odstranjevanje dominiranih kandidatov pri iskanju maksimuma v drsečem oknu.
Različica: Python 3.12
Sintaksa
d.pop()collections.deque.pop je metoda primerka dvostranske vrste deque. Klic d.pop() ne sprejme argumentov: odstrani skrajni desni element neposredno iz vrste d in ga vrne. Če je vrsta prazna, sproži IndexError. Izraz d[-1] element le prebere, medtem ko d.popleft() odstrani in vrne skrajni levi element. Odstranjevanje na katerem koli koncu traja približno O(1).
Tudi list.pop() brez argumenta odstrani in vrne zadnji element, vendar metoda seznama sprejme neobvezen indeks. deque.pop() ne sprejme indeksa: za odstranjevanje z leve uporabi d.popleft(), ne d.pop(0).
Pri iskanju maksimuma v drsečem oknu ostane novejši kandidat, katerega vrednost je vsaj tolikšna kot vrednost starejšega kandidata, dlje v oknu. Starejši kandidat je zato dominiran. Pogoj while candidates and candidates[-1] <= incoming najprej preveri, ali vrsta ni prazna, in šele nato prebere skrajni desni element. Zanka z desne odstrani dominirane kandidate, nato pa append() na desni konec doda novo vrednost. Primer prikazuje le odstranjevanje z desne. Različica, ki uporablja indekse, hrani indekse kandidatov in na njihovi podlagi z leve odstrani tiste, ki niso več v oknu.
Primeri
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))Rezultat
[3, 6] [9, 7]
Zanka najprej odstrani `3`, nato `6` in se ustavi pri `9`. Ko doda `7`, program izpiše `[3, 6]` in `[9, 7]` v ločenih vrsticah.
Povezane lekcije
- Python · Lekcija 41 · Napredna · Različica: 5