Français
Menu

Qu'est-ce que File d'attente ?

Structure de données FIFO (premier entré, premier sorti) dans laquelle l'élément ajouté en premier est retiré en premier. L'ajout à l'arrière s'appelle enqueue (enfilage) et le retrait à l'avant dequeue (défilage). Les files d'attente servent aux files de travaux en attente, à la transmission de données entre tâches et au parcours en largeur.

Nom japonais: キュー

« File d'attente » apparaît dans 7 questions d'entraînement réparties sur 4 thèmes, dont Structures de données et algorithmes, Bases de la programmation (trace de pseudo-code), Bases des réseaux informatiques.

Domaine: Structures de données et algorithmes

S'entraîner : questions sur File d'attente

On ajoute dans cet ordre les éléments A, B et C à une file d'attente vide. Ensuite, on retire un élément, on ajoute D et on retire un élément, puis on ajoute E et on retire un élément. Dans quel ordre les éléments sont-ils retirés ?

  1. AA, B, C
  2. BC, D, E
  3. CC, B, A
Afficher la réponse et l'explication

Réponse : A. A, B, C

Une file d'attente est une structure FIFO (premier entré, premier sorti) : les éléments sont retirés dans l'ordre où ils ont été ajoutés. Après l'ajout de A, B et C, le premier retrait prend A. Même si D et E sont ensuite ajoutés à l'arrière, B et C, placés devant, sortent d'abord : l'ordre de retrait est donc A, B, C, et D et E restent dans la file. C, D, E serait l'ordre obtenu avec une pile (LIFO), qui retire à chaque fois l'élément ajouté le plus récemment. Les files servent pour les travaux d'impression, pour les files de messages qui transmettent des données entre tâches et pour le parcours en largeur.

« File d'attente » dans les explications

Questions mentionnant « File d'attente » (7)

  1. On ajoute dans cet ordre les éléments A, B et C à une file d'attente vide. Ensuite, on retire un élément, on ajoute D et on retire un élément, puis on ajoute E et on retire un élément. Dans quel ordre les éléments sont-ils retirés ?
  2. Une file d'attente utilise de façon circulaire le tableau de chaînes q de 4 éléments. head et tail valent 1 au départ. enq(v) exécute q[tail] ← v puis tail ← tail mod 4 + 1 ; deq() renvoie la valeur de q[head] puis exécute head ← head mod 4 + 1. Lors de l'exécution du programme suivant, dans quel élément de q « E » est-il stocké ?
  3. Quelle description de l'idée de base du contrôle de congestion de TCP est correcte ?
  4. Sur une pile vide, on effectue dans cet ordre les opérations push 1, push 2, pop, push 3, push 4, pop, pop. Dans quel ordre les valeurs sont-elles retirées par pop ?
  5. Un tas max, dans lequel la valeur de chaque parent est supérieure ou égale à celles de ses enfants, est stocké dans un tableau avec la racine en a[0]. On ajoute 45 au tas 50, 30, 40, 10, 20, 35 en le plaçant à la fin, puis en l'échangeant avec son parent tant qu'il est plus grand que celui-ci. Quel est le tableau obtenu ?
  6. Dans un graphe dont les arêtes n'ont pas de poids, on veut trouver le plus petit nombre d'arêtes entre un sommet de départ et chacun des autres sommets. Quelle association entre méthode de recherche et structure de données convient ?
  7. Lorsque le taux d'utilisation d'un serveur (proportion de temps occupé) approche 100 %, comment évolue le temps d'attente des requêtes ?

Termes associés

Pile (stack) Parcours en largeur (breadth-first search) Tableau Tas binaire (binary heap) Parcours en profondeur (depth-first search) Récursion (récursivité) Algorithme de Dijkstra Algorithme glouton (greedy) Arbre binaire de recherche (binary search tree) Complexité temporelle (notation grand O)

Retour au glossaire