1. Une file d'attente peut être définie comme une liste ordonnée qui permet d'effectuer des opérations d'insertion à une extrémité appelée ARRIÈRE et supprimer les opérations à effectuer à une autre extrémité appelée DEVANT .
2. La file d'attente est appelée liste Premier entré, premier sorti.
3. Par exemple, les personnes qui font la queue pour un billet de train forment une file d'attente.
Applications de la file d'attente
En raison du fait que la file d'attente effectue les actions sur la base du premier entré, premier sorti, ce qui est tout à fait juste pour l'ordre des actions. Il existe diverses applications des files d'attente décrites ci-dessous.
- Les files d'attente sont largement utilisées comme listes d'attente pour une seule ressource partagée comme une imprimante, un disque ou un processeur.
- Les files d'attente sont utilisées dans le transfert asynchrone de données (où les données ne sont pas transférées au même rythme entre deux processus), par exemple. tuyaux, fichiers IO, sockets.
- Les files d'attente sont utilisées comme tampons dans la plupart des applications comme le lecteur multimédia MP3, le lecteur CD, etc.
- Les files d'attente sont utilisées pour maintenir la liste de lecture dans les lecteurs multimédias afin d'ajouter et de supprimer des chansons de la liste de lecture.
- Les files d'attente sont utilisées dans les systèmes d'exploitation pour gérer les interruptions.
Complexité
| Structure de données | Complexité temporelle | Complétude de l'espace | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Moyenne | Pire | Pire | |||||||
| Accéder | Recherche | Insertion | Effacement | Accéder | Recherche | Insertion | Effacement | ||
| File d'attente | dans) | dans) | je(1) | je(1) | Sur) | Sur) | O(1) | O(1) | Sur) |