Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / Python

`deque.pop()` — usuwanie elementu z prawego końca kolejki

`deque.pop()` usuwa i zwraca skrajny prawy element kolejki dwustronnej. Służy między innymi do odrzucania zdominowanych kandydatów na maksimum w oknie przesuwnym.

Wersja: Python 3.12

Składnia

d.pop()

collections.deque.pop to metoda instancji kolejki dwustronnej deque. Wywołanie d.pop() nie przyjmuje argumentów: usuwa skrajny prawy element z d i zwraca właśnie ten element. Pusta kolejka powoduje zgłoszenie IndexError. Odczyt d[-1] nie usuwa elementu, a d.popleft() usuwa i zwraca element z lewego końca. Usuwanie z każdego z końców kolejki deque ma koszt około O(1).

list.pop() bez argumentu również usuwa i zwraca ostatni element, ale metoda listy przyjmuje opcjonalny indeks. deque.pop() nie przyjmuje indeksu: do usuwania z lewej strony kolejki użyj d.popleft(), a nie d.pop(0).

Przy wyznaczaniu maksimum w oknie przesuwnym nowszy kandydat o wartości co najmniej tak dużej jak starszy pozostanie w oknie dłużej. Starszy kandydat jest więc zdominowany. Warunek while candidates and candidates[-1] <= incoming sprawdza, czy kolejka nie jest pusta, zanim odczyta prawy element. Pętla usuwa zdominowanych kandydatów od prawej, po czym append() dopisuje nową wartość po prawej stronie. Przykład pokazuje tylko usuwanie z prawej. Wariant oparty na indeksach przechowuje indeksy kandydatów i na ich podstawie usuwa z lewego końca kolejki tych, którzy wypadli z okna.

Przykłady

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

Wynik

[3, 6]
[9, 7]

Pętla usuwa najpierw `3`, a potem `6`, i zatrzymuje się na `9`. Po dopisaniu `7` program wypisuje `[3, 6]` oraz `[9, 7]` w osobnych wierszach.

Powiązane lekcje

  • Python · Lekcja 41 · Zaawansowany · Wersja: 5

Źródła