Queues and Sliding Windows with deque

Your program hands out jobs in the order they arrived. Or it reads sensor values and keeps only the last three. Both need a container that adds items at one end and removes them from the other. A list can do it, but list.pop(0) moves every remaining item down one place. A collections.deque, pronounced "deck", adds and removes at either end without moving anything.

from collections import deque

pending: deque[str] = deque(["read", "parse"])
pending.append("report")
assert pending.popleft() == "read"
assert list(pending) == ["parse", "report"]

Pick the container for the work you do

Here n is the number of items. A deque stores its items in linked blocks. It reaches either end in one step, but has to step through the blocks to reach the middle. Use a list when you mostly index into it, and a deque when you mostly work at the ends.

Taking the first item off a list n times costs O(n²) in total, because each removal shifts everything that remains. A deque does the same job in O(n).

Keep only the most recent items

from collections import deque

recent: deque[int] = deque(maxlen=3)
for value in [10, 20, 30, 40]:
    recent.append(value)
assert list(recent) == [20, 30, 40]
recent.appendleft(5)
assert list(recent) == [5, 20, 30]

A deque with maxlen never grows past that size. When it is full, adding an item at one end drops an item from the other end. The extend and extendleft methods follow the same rule for each item they add. The insert method is the exception. It raises IndexError on a full deque.

deque(source, maxlen=w) reads the whole source and keeps its last w items. That gives you the end of a file or a stream in one call. It never finishes on a source that never ends.

Add to the left and rotate

from collections import deque

left: deque[int] = deque([3])
left.extendleft([1, 2])
assert list(left) == [2, 1, 3]

kept: deque[int] = deque([3])
kept.extendleft(reversed([1, 2]))
assert list(kept) == [1, 2, 3]
kept.rotate(1)
assert list(kept) == [3, 1, 2]
kept.rotate(-1)
assert list(kept) == [1, 2, 3]

The extendleft method adds the items one at a time at the left, so they end up in reverse order. To keep their order, pass reversed(items). That works for a list, but not for a one-shot iterator. A one-shot iterator is an iterator you can loop over only once, such as a generator or an open file. Turn it into a list first. The article "Generators and One-Shot Iterators", later in this track, covers them.

rotate(1) moves the last item to the front, and rotate(-1) moves the first item to the back.

Handle a deque with no limit

from collections import deque


def headroom(buffer: deque[float]) -> int:
    limit = buffer.maxlen
    if limit is None:
        return -1
    return limit - len(buffer)


assert headroom(deque([1.0], maxlen=3)) == 2
assert headroom(deque([1.0])) == -1

The maxlen attribute is int | None, and None means the deque has no limit. Check for None before you subtract, and mypy accepts the function. Returning -1 for a deque with no limit is this exercise's choice, not part of the deque API.