Queues

A queue is a line at the counter. People join at the back and are served from the front, so the first in is the first out. Anything that must be handled in arrival order is a queue: customers, print jobs, messages.

Why not a list?

A list can do it: append at the back, pop(0) at the front. But pop(0) has to shift every remaining item one place left, so it gets slower as the list grows. For a few items nobody notices. For thousands it matters.

Python's standard library has a type built for this: deque (say "deck"), from the collections module. It is fast at both ends.

from collections import deque

line = deque()
line.append("Ada")
line.append("Grace")
line.append("Linus")
print(line)

served = line.popleft()
print("Serving", served)
print(line)

append adds at the back as usual. popleft removes and returns the item at the front. The from collections import deque line brings the type in; collections is part of Python, nothing to install.

The rest of deque

A deque works like a list for most things: len, in, looping, [0] for the front and [-1] for the back. It also has appendleft and pop, so it can be a stack too, or a line that people can jump.

from collections import deque

line = deque(["Ada", "Grace"])
line.appendleft("Linus")
print(line)
print(line[0], line[-1])
print(len(line))

Only the last few

deque(maxlen=n) keeps at most n items. Adding at the back of a full one silently drops the item at the front, the oldest. That is exactly "the last three things that happened".

from collections import deque

recent = deque(maxlen=3)
for item in ["apple", "bread", "milk", "eggs", "flour"]:
    recent.append(item)
    print(list(recent))

The queue loop

The standard shape: while the queue is not empty, take from the front, deal with it, and possibly add new things to the back. An empty deque counts as False, just like an empty list, so while orders: runs until it is drained. It is how you process work that generates more work.

from collections import deque

orders = deque(["bread", "cake"])
while orders:
    order = orders.popleft()
    print("Making", order)
    if order == "cake":
        orders.append("icing")

Try it

Serve in order

arrivals is a list of customer names in the order they joined the line. Write serve_all(arrivals) that uses a deque to serve them one at a time from the front, and returns a list of the names in the order they were served. Do not change arrivals itself; the starter copies it into a deque for you.

serve_all(["Ada", "Grace", "Linus"])  ->  ["Ada", "Grace", "Linus"]

It looks trivial, and it is: the point is to write the queue loop once.

from collections import deque

def serve_all(arrivals):
    line = deque(arrivals)
    served = []
    while line:
        ...
    return served

Move to the back

A customer at the front of the line forgot their wallet and goes to the back. Write to_back(line) that takes a deque, moves the front item to the back, and returns the deque you were given, not a new one. An empty deque is returned unchanged.

to_back(deque(["Ada", "Grace", "Linus"]))  ->  deque(["Grace", "Linus", "Ada"])

from collections import deque

def to_back(line):
    ...

Recent items

Write last_n(items, n) that returns a list of the last n items of items, in their original order, using a deque with maxlen. If there are fewer than n items, return all of them.

last_n(["apple", "bread", "milk", "eggs"], 2)  ->  ["milk", "eggs"]
last_n(["apple"], 3)                           ->  ["apple"]

from collections import deque

def last_n(items, n):
    recent = deque(maxlen=n)
    for item in items:
        ...
    return list(recent)

Next: Priority queues.