A waiting line and a Python implementation

A very concrete use case: the waiting line

A shared printer, a web server handling requests, a video game managing players' actions: in all these cases, a queue is used to guarantee that requests are handled in the order they arrived, without « jumping » any of them. This is the fairness principle of FIFO.

Diagram: a line at a single checkout

Arrivals in order: client1, client2, client3

waiting line:
[client1]
[client1, client2]
[client1, client2, client3]

cashier serves client1 -> dequeue client1
remaining line: [client2, client3]
cashier serves client2 -> dequeue client2
remaining line: [client3]

Python implementation using a list

class File:
    def __init__(self):
        self.elements = []

    def enfiler(self, valeur):
        self.elements.append(valeur)

    def defiler(self):
        if self.est_vide():
            raise IndexError("file vide")
        return self.elements.pop(0)

    def est_vide(self):
        return len(self.elements) == 0

f = File()
f.enfiler("A")
f.enfiler("B")
f.enfiler("C")
print(f.defiler())   # A
print(f.defiler())   # B
print(f.elements)    # ['C']

Common pitfall

With a Python list, enfiler (append) is fast, but defiler (pop(0)) has to shift every remaining element one slot towards the front: this is costly as soon as the queue grows, since each dequeue then costs a time proportional to the number of remaining elements. In practice, collections.deque is often preferred, designed to remove efficiently at the front of the queue in constant time, but the implementation with a plain list is perfectly fine for understanding the FIFO principle before optimising.