Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / Python

Appending to the right of a `deque`

`collections.deque.append` adds one item to the right end of a double-ended queue. In this sliding-window example, the monotonic queue stores indices rather than the values themselves.

Version: Python 3.12

Syntax

d.append(x)  # d is a collections.deque; x is passed positionally; returns None

In Python 3.12, collections.deque.append is a method of the deque type in the collections module. Call d.append(x) with x as a positional argument. It adds x as one item at the right end, even if x is iterable. It changes d in place and returns None, so don't write d = d.append(x). Use appendleft(x) to add on the left or extend(iterable) to add the iterable's items on the right.

Both list.append and deque.append add at the end. For queues, the difference is that a deque supports appends and pops at either end in approximately O(1) time, whereas list.pop(0) shifts the remaining items and takes O(n) time.

If maxlen is omitted or None, the deque has no fixed length limit. If a deque with a positive maxlen is full, append automatically discards the leftmost item instead of raising an exception because it is full. With maxlen=0, no items are retained. The example uses an unbounded deque: an index expires based on its position in the input, not on the number of candidates.

To find sliding-window maxima, remove expired indices from the left with popleft(), then use pop() to remove indices from the right whose values are less than or equal to the new value. A newer index with the same value stays in the window longer. Then call candidates.append(i) on the deque: store the index i and use values[i] for comparisons. The values at the remaining indices decrease from left to right, so values[candidates[0]] is the maximum once the window is full.

Examples

from collections import deque

values = [4, 2, 2, 5, 3, 1, 2]
width = 3
candidates = deque()
maxima = []

for i, value in enumerate(values):
    while candidates and candidates[0] <= i - width:
        candidates.popleft()
    while candidates and values[candidates[-1]] <= value:
        candidates.pop()
    candidates.append(i)
    if i >= width - 1:
        maxima.append(values[candidates[0]])

print(maxima)

Result

[4, 5, 5, 5, 3]

When the second `2` arrives, its index `2` replaces index `1`. In the last window, index `3` (value `5`) expires and is removed from the left, leaving `3` as the maximum.

Related lessons

  • Python · Lesson 41 · Advanced · Version: 5

Sources