Build a queue or sliding window¶

The question. You need a structure that works at the ends: a FIFO queue, a record of the last N things, a moving average over a window, or an undo history. A list is slow at the front and unbounded; deque is built for exactly this.

Below are the four shapes you'll reach for, each a couple of lines with deque.

A FIFO queue¶

Add with append, take the oldest with popleft. This is the standard first-in-first-out queue — and unlike list.pop(0), every operation is fast.

In [ ]:

from collections import deque

tasks = deque()
tasks.append('email')      # arrivals join the back
tasks.append('build')
tasks.append('deploy')

while tasks:
    print('handling:', tasks.popleft())   # leave from the front, oldest first
# handling: email / build / deploy

from collections import deque tasks = deque() tasks.append('email') # arrivals join the back tasks.append('build') tasks.append('deploy') while tasks: print('handling:', tasks.popleft()) # leave from the front, oldest first # handling: email / build / deploy

The last N items (bounded history)¶

A deque(maxlen=N) keeps only the most recent N items — each new arrival past the limit pushes the oldest out. No manual trimming.

In [ ]:

from collections import deque

recent = deque(maxlen=5)
for event in ['login', 'view', 'click', 'view', 'logout', 'login', 'error']:
    recent.append(event)

print(list(recent))        # ['click', 'view', 'logout', 'login', 'error'] — last 5 only

from collections import deque recent = deque(maxlen=5) for event in ['login', 'view', 'click', 'view', 'logout', 'login', 'error']: recent.append(event) print(list(recent)) # ['click', 'view', 'logout', 'login', 'error'] — last 5 only

A moving average over a window¶

A bounded deque holds the current window; sum it for a rolling statistic. Each step appends one value (dropping the oldest automatically) and recomputes over the window.

In [ ]:

from collections import deque

def moving_average(values, window):
    win = deque(maxlen=window)
    averages = []
    for v in values:
        win.append(v)
        averages.append(sum(win) / len(win))   # len(win) grows then stays at `window`
    return averages

readings = [10, 20, 30, 40, 50]
print(moving_average(readings, 3))
# [10.0, 15.0, 20.0, 30.0, 40.0]

from collections import deque def moving_average(values, window): win = deque(maxlen=window) averages = [] for v in values: win.append(v) averages.append(sum(win) / len(win)) # len(win) grows then stays at `window` return averages readings = [10, 20, 30, 40, 50] print(moving_average(readings, 3)) # [10.0, 15.0, 20.0, 30.0, 40.0]

A bounded undo history¶

append to record a state, pop to undo the most recent — a LIFO stack. Adding maxlen caps how far back you can undo, quietly discarding the oldest states so memory stays bounded.

In [ ]:

from collections import deque

history = deque(maxlen=3)        # remember at most 3 steps
for state in ['', 'H', 'He', 'Hel', 'Hell', 'Hello']:
    history.append(state)

print(list(history))             # ['Hel', 'Hell', 'Hello'] — older states dropped
print('undo to:', history.pop()) # 'Hello' off; previous is now on top
print('then:', history[-1])      # 'Hell'

from collections import deque history = deque(maxlen=3) # remember at most 3 steps for state in ['', 'H', 'He', 'Hel', 'Hell', 'Hello']: history.append(state) print(list(history)) # ['Hel', 'Hell', 'Hello'] — older states dropped print('undo to:', history.pop()) # 'Hello' off; previous is now on top print('then:', history[-1]) # 'Hell'

In short¶

• FIFO queue: append + popleft (fast at both ends, unlike a list).
• Last N items: deque(maxlen=N) trims itself.
• Moving window stat: a bounded deque you sum/average each step.
• Undo stack: append/pop, with maxlen to bound the history.