CKTIS / Python
`deque.pop()` — remove the rightmost item
`deque.pop()` removes and returns the rightmost item of a double-ended queue. Use it to discard dominated candidates when computing a sliding-window maximum.
Version: Python 3.12
Syntax
d.pop()collections.deque.pop is an instance method of the double-ended queue deque. The call d.pop() takes no arguments: it removes the rightmost item from d in place and returns that item. An empty deque raises IndexError. Reading d[-1] leaves the item in place, whereas d.popleft() removes and returns the leftmost item. Removing from either end of a deque takes approximately O(1) time.
list.pop() also removes and returns the last item when called without an argument, but the list method accepts an optional index. deque.pop() does not take an index: use d.popleft(), not d.pop(0), to remove from the left.
For a sliding-window maximum, a newer candidate with a value at least as large as an older candidate stays in the window longer. The older candidate is therefore dominated. The condition while candidates and candidates[-1] <= incoming checks that the deque is nonempty before reading the rightmost item. The loop removes dominated candidates from the right, then append() adds the new value at that end. The example shows only right-end pruning. An index-based implementation stores candidate indices and uses them to remove expired candidates from the left end.
Examples
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))Result
[3, 6] [9, 7]
The loop removes `3` and then `6`, and stops at `9`. After appending `7`, the program prints `[3, 6]` and `[9, 7]` on separate lines.
Related lessons
- Python · Lesson 41 · Advanced · Version: 5