CKTIS / Python
`deque.pop()` — het meest rechtse element verwijderen
`deque.pop()` verwijdert het meest rechtse element van een dubbelzijdige wachtrij en geeft het terug. Zo kun je gedomineerde kandidaten voor het maximum van een schuivend venster verwijderen.
Versie: Python 3.12
Syntax
d.pop()collections.deque.pop is een instantiemethode van deque, een dubbelzijdige wachtrij. De aanroep d.pop() neemt geen argumenten aan: hij verwijdert het meest rechtse element uit d zelf en geeft dat element terug. Is de deque leeg, dan wordt IndexError opgegooid. d[-1] leest het element zonder het te verwijderen, terwijl d.popleft() het meest linkse element verwijdert en teruggeeft. Verwijderen aan beide uiteinden kost per bewerking ongeveer O(1) tijd.
Ook list.pop() verwijdert zonder argument het laatste element en geeft het terug, maar de lijstmethode accepteert een optionele index. deque.pop() accepteert geen index: gebruik d.popleft() en niet d.pop(0) om links een element te verwijderen.
Bij het berekenen van het maximum in een schuivend venster blijft een nieuwere kandidaat met minstens dezelfde waarde als een oudere kandidaat langer in het venster. De oudere kandidaat is dus gedomineerd. De voorwaarde while candidates and candidates[-1] <= incoming controleert eerst of de deque niet leeg is voordat het meest rechtse element wordt gelezen. De lus verwijdert gedomineerde kandidaten aan de rechterkant, waarna append() de nieuwe waarde rechts toevoegt. Het voorbeeld toont alleen het verwijderen aan de rechterkant. Een implementatie op basis van indices houdt de indices van de kandidaten bij en gebruikt die om kandidaten die buiten het venster zijn gevallen aan de linkerkant te verwijderen.
Voorbeelden
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))Resultaat
[3, 6] [9, 7]
De lus verwijdert eerst `3`, dan `6`, en stopt bij `9`. Nadat `7` is toegevoegd, drukt het programma `[3, 6]` en `[9, 7]` op afzonderlijke regels af.
Gerelateerde lessen
- Python · Les 41 · Gevorderd · Versie: 5