CKTIS / Python
`deque.pop()` — remover o elemento da extremidade direita
`deque.pop()` remove e devolve o elemento da extremidade direita de uma fila de duas extremidades. É útil para descartar candidatos dominados no cálculo do máximo de uma janela deslizante.
Versão: Python 3.12
Sintaxe
d.pop()collections.deque.pop é um método de instância de deque, uma fila de duas extremidades. A chamada d.pop() não aceita argumentos: remove o elemento da extremidade direita da própria fila d e devolve-o. Se a fila estiver vazia, lança IndexError. d[-1] lê o elemento sem o remover, ao passo que d.popleft() remove e devolve o da extremidade esquerda. Uma remoção em qualquer das extremidades demora aproximadamente O(1).
Sem argumentos, list.pop() também remove e devolve o último elemento, mas o método das listas aceita um índice opcional. deque.pop() não aceita um índice: para remover pela esquerda, usa d.popleft(), não d.pop(0).
Ao calcular o máximo de uma janela deslizante, um candidato mais recente com um valor pelo menos tão grande como o de um candidato mais antigo permanece mais tempo na janela. O candidato mais antigo fica, portanto, dominado. A condição while candidates and candidates[-1] <= incoming verifica que a fila não está vazia antes de ler o elemento à direita. O ciclo remove os candidatos dominados pela direita e, em seguida, append() acrescenta o novo valor à direita. O exemplo mostra apenas a remoção pela direita. Uma implementação baseada em índices guarda os índices dos candidatos e usa-os para remover pela esquerda os que saíram da janela.
Exemplos
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))Resultado
[3, 6] [9, 7]
O ciclo remove primeiro `3`, depois `6`, e para em `9`. Após acrescentar `7`, o programa escreve `[3, 6]` e `[9, 7]` em linhas separadas.
Lições relacionadas
- Python · Lição 41 · Avançado · Versão: 5