Queue in Python using deque

A queue is a collection where the first item you add is the first one you take out: first in, first out (FIFO), like people waiting in a line. collections.deque is the right tool for a queue in Python.

The program

from collections import deque

queue = deque()
queue.append("Ada")        # enqueue: join the back of the line
queue.append("Linus")
queue.append("Grace")
print(queue)

print(queue[0])            # look at the front without removing it
print(queue.popleft())     # dequeue: take from the front
print(queue)

while queue:
    print("serving", queue.popleft())
print("queue empty:", len(queue) == 0)

deque(['Ada', 'Linus', 'Grace'])
Ada
Ada
deque(['Linus', 'Grace'])
serving Linus
serving Grace
queue empty: True

How it works

• append() adds to the right end (the back of the queue). popleft() removes from the left end (the front).
• A deque (say "deck", short for double-ended queue) can add and remove at both ends quickly.
• A list can do the same with pop(0), but that is slow on long lists: every remaining item must move one place to the left. popleft() takes the same short time however long the deque is.
• popleft() on an empty deque raises an IndexError. while queue: stops when the deque is empty, because an empty deque counts as False.

A fixed-size queue

With maxlen, a deque keeps only the newest items. When it is full, adding to the back drops an item from the front. This is useful for "the last N" values, such as recent log lines:

from collections import deque

recent = deque(maxlen=3)
for page in ["home", "lessons", "errors", "notebook", "answers"]:
    recent.append(page)
    print(list(recent))

['home']
['home', 'lessons']
['home', 'lessons', 'errors']
['lessons', 'errors', 'notebook']
['errors', 'notebook', 'answers']

Related programs: Stack in Python using a list.