Qu'est-ce qu'une queue et où est-elle utilisée ?

Question

Accepted Answer

Une **queue** est une collection **FIFO** (First-In, First-Out) : les éléments sont ajoutés à l'**arrière** et supprimés de l'**avant**, comme une file de personnes. ## Opérations ```text enqueue(1) enqueue(2) enqueue(3) dequeue()->1 front ->[1][2][3]<- back front ->[2][3]<- back ``` ## Exemple ```python from collections import deque queue = deque() queue.append('a') # enqueue (back) queue.append('b') first = queue.popleft() # dequeue (front) -> 'a' ``` Une `list` Python ordinaire rend `pop(0)` une opération **O(n)**, donc utilisez `deque` pour **O(1)** aux deux extrémités. | Opération | Temps (deque) | |---|---| | enqueue | O(1) | | dequeue | O(1) | | peek avant | O(1) | ## Cas d'usage courants - **Planification de tâches / travaux** — traiter le travail dans l'ordre d'arrivée. - **Recherche en largeur (BFS)** — visiter les nœuds niveau par niveau. - **Buffering** — pipelines producteur/consommateur, files d'impression, files de requêtes. ## Pourquoi c'est important Les queues imposent l'équité et l'ordre, ce qui est critique pour les planificateurs, les systèmes de messagerie et les BFS. Chaque fois que le travail doit être géré « dans l'ordre où il est arrivé », une queue est l'approche naturelle.