Queues: First In, First Out

A line at the counter

A queue is the opposite of a stack: items join at the back and leave from the front. FIFO: first in, first out.

Think of it like this: The queue at a ticket counter, a printer printing documents in order, or messages waiting to be sent.

Use collections.deque

A list is a bad queue: pop(0) shifts every item (O(n)). A deque (“deck”, double-ended queue) adds and removes at both ends in O(1):

from collections import deque

line = deque()
line.append("Asha")         # join the back
line.append("Ravi")
line.append("Meera")
print(line)
print("served:", line.popleft())   # leave from the front
print("served:", line.popleft())
print("still waiting:", list(line))

Output

deque(['Asha', 'Ravi', 'Meera'])
served: Asha
served: Ravi
still waiting: ['Meera']

A simulation: pass the parcel

Children sit in a circle; the parcel passes k times and whoever holds it is out. A queue models the circle: passing = move the front child to the back.

from collections import deque

def last_one(names, k):
    circle = deque(names)
    while len(circle) > 1:
        for _ in range(k - 1):
            circle.append(circle.popleft())   # pass the parcel
        print("out:", circle.popleft())
    return circle[0]

print("winner:", last_one(["A", "B", "C", "D", "E"], 3))

Output

out: C
out: A
out: E
out: B
winner: D

Tip: Queues are the heart of breadth-first search (BFS), which you'll use on trees and graphs.