CKTIS / Python
`deque.pop()` — eliminar el elemento del extremo derecho
`deque.pop()` elimina y devuelve el elemento del extremo derecho de una cola de doble extremo. Sirve para descartar candidatos dominados al calcular el máximo de una ventana deslizante.
Versión: Python 3.12
Sintaxis
d.pop()collections.deque.pop es un método de instancia de deque, una cola de doble extremo. La llamada d.pop() no acepta argumentos: elimina el elemento del extremo derecho de la propia cola d y lo devuelve. Si la cola está vacía, se produce IndexError. d[-1] lee el elemento sin eliminarlo, mientras que d.popleft() elimina y devuelve el del extremo izquierdo. Eliminar en cualquiera de los dos extremos lleva un tiempo de aproximadamente O(1).
list.pop() también elimina y devuelve el último elemento si se llama sin argumentos, pero el método de lista admite un índice opcional. deque.pop() no admite un índice: para eliminar por la izquierda, usa d.popleft(), no d.pop(0).
Para calcular el máximo de una ventana deslizante, un candidato más reciente cuyo valor es al menos tan grande como el de otro más antiguo permanece más tiempo en la ventana. Por eso, el candidato más antiguo queda dominado. La condición while candidates and candidates[-1] <= incoming comprueba que la cola no está vacía antes de leer el elemento derecho. El bucle elimina los candidatos dominados por la derecha y, a continuación, append() añade el nuevo valor por ese extremo. El ejemplo solo muestra la eliminación por la derecha. Una implementación basada en índices guarda los índices de los candidatos y los usa para eliminar por la izquierda los que han salido de la ventana.
Ejemplos
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]
El bucle elimina primero `3`, luego `6`, y se detiene en `9`. Tras añadir `7`, el programa imprime `[3, 6]` y `[9, 7]` en líneas distintas.
Lecciones relacionadas
- Python · Lección 41 · Avanzado · Versión: 5