FIFO, buffers et round-robin

Idee et operations

Une file suit la regle FIFO. Les operations: enqueue, dequeue, head. Temps O(1), espace O(n).

Tableau circulaire

index: 0  1  2  3  4  5
data:  [A][B][C][ ][ ][ ]
head -> 0         tail -> 3
dequeue(): retire A, head -> 1
enqueue(D): place D en 3, tail -> 4
          

Maintenir size evite le cas ambigu head == tail.

Applications

Ordonnancement round-robin, buffers, pipes, queues de messages.

Parcours en largeur (BFS)

BFS utilise une file pour visiter un graphe niveau par niveau. C'est l'opposé poli du DFS.