Queues and deque

A queue works like a line of people: you join at the back and leave from the front, so the first item in is the first out. In Python, use collections.deque for a queue, not a list.

First in, first out

A queue has two main operations:

• enqueue (join): add an item at the back;
• dequeue (leave): take the item at the front.

A stack gives back the newest item; a queue gives back the oldest. Use a queue when things must be handled in the order they arrived.

Why list.pop(0) is slow

A list can act as a queue: append to join and pop(0) to leave. It gives the right answers. But a list keeps its items from place 0 with no gaps, so after the front item leaves, every other item moves one place to the left. Step through it, then switch to the deque:

With n items waiting, each pop(0) moves n − 1 items: O(n). A program that puts n items through the queue then does about n² / 2 moves (n multiplied by n, then halved). For 100,000 items that is 5 billion moves.

collections.deque

A deque (double-ended queue) adds and removes at both ends in O(1). Inside, it is a two-way linked list of blocks of 64 items (LINK-3), so taking from the front never moves other items.

from collections import deque

q = deque()
q.append('A')          # join at the back
q.append('B')
q.popleft()            # 'A': leave from the front
q[0]                   # look at the front without removing it
len(q), bool(q)        # size, and whether it has anything in it

d = deque(maxlen=3)    # keeps only the 3 newest items
for x in range(5):
    d.append(x)        # d is now deque([2, 3, 4])

A deque also has appendleft and pop, so it works as a stack too. What it does badly is reach the middle: q[k] is O(n) for k far from both ends. Use a list when you read by position, and a deque when you work at the ends.

Where queues appear

• Breadth-first search (GRPH): visit the places one step away, then two steps away, and so on. A queue keeps them in that order.
• Jobs waiting for a worker: print jobs, requests to a web server.
• Recent events: keep events in time order; drop old ones from the front when they get too old. This is the idea behind STAQ-P3.

Now try STAQ-P3, Recent pings.