Queues
First in, first out.
A queue is like a line at a shop. People join at the back, and are served from the front. First in, first out. Printers, customer support tickets, and messages between programs all use queues.

- A line at a shop
- Join at the back, leave from the front
- Printers, tickets, messages
Use deque, not list
You could use a list as a queue, but pop at zero is O of N, because every item shifts. The collections module has deque, a double ended queue. Append adds to the back, and pop left removes from the front, both in O of one. Run it. Customers are served in the order they arrived.
from collections import deque
line = deque()
for name in ["Priya", "Sam", "Jo"]:
line.append(name)
print(name, "joins:", list(line))
while line:
print("serving", line.popleft())Priya joins: ['Priya'] Sam joins: ['Priya', 'Sam'] Jo joins: ['Priya', 'Sam', 'Jo'] serving Priya serving Sam serving Jo
How much faster?
Let's measure. We fill a list and a deque with one hundred thousand items, and then empty each one from the front. Run it. The deque empties almost instantly. The list is much slower, because every pop at zero shifts every remaining item.
import time
from collections import deque
n = 100_000
items = list(range(n))
start = time.perf_counter()
while items:
items.pop(0)
print(f"list.pop(0): {time.perf_counter() - start:.3f} s")
q = deque(range(n))
start = time.perf_counter()
while q:
q.popleft()
print(f"deque.popleft(): {time.perf_counter() - start:.3f} s")list.pop(0): 0.798 s deque.popleft(): 0.003 s
Summary
A queue is first in, first out. Use deque, with append and pop left, for O of one at both ends. Next, a new structure. The linked list.
Key takeaways- First in, first out
- deque.append / popleft
- Both O(1)