WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / Python

`deque.pop()` — das Element am rechten Ende entfernen

`deque.pop()` entfernt das äußerste rechte Element einer doppelseitigen Warteschlange und gibt es zurück. Damit lassen sich dominierte Kandidaten für das Maximum eines gleitenden Fensters verwerfen.

Version: Python 3.12

Syntax

d.pop()

collections.deque.pop ist eine Instanzmethode der doppelseitigen Warteschlange deque. Der Aufruf d.pop() nimmt keine Argumente entgegen: Er entfernt das äußerste rechte Element direkt aus d und gibt es zurück. Ist die Warteschlange leer, wird IndexError ausgelöst. d[-1] liest das Element nur, während d.popleft() das äußerste linke Element entfernt und zurückgibt. Das Entfernen an beiden Enden dauert jeweils ungefähr O(1).

Auch list.pop() entfernt ohne Argument das letzte Element und gibt es zurück. Die Listenmethode akzeptiert aber einen optionalen Index. deque.pop() akzeptiert keinen Index: Zum Entfernen am linken Ende dient d.popleft(), nicht d.pop(0).

Beim Maximum eines gleitenden Fensters bleibt ein neuerer Kandidat mit mindestens so großem Wert wie ein älterer Kandidat länger im Fenster. Der ältere Kandidat ist daher dominiert. Die Bedingung while candidates and candidates[-1] <= incoming prüft vor dem Lesen des rechten Elements, ob die Warteschlange nicht leer ist. Die Schleife entfernt dominierte Kandidaten von rechts; danach hängt append() den neuen Wert rechts an. Das Beispiel zeigt nur das Entfernen am rechten Ende. Eine indexbasierte Implementierung speichert die Indizes der Kandidaten und entfernt damit am linken Ende diejenigen, die nicht mehr im Fenster liegen.

Beispiele

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))

Ergebnis

[3, 6]
[9, 7]

Die Schleife entfernt zuerst `3`, dann `6` und hält bei `9` an. Nachdem `7` angehängt wurde, gibt das Programm `[3, 6]` und `[9, 7]` in getrennten Zeilen aus.

Zugehörige Lektionen

  • Python · Lektion 41 · Fortgeschritten · Version: 5

Quellen