Guide du débutant pour comprendre les files d'attente et les files d'attente prioritaires

En tant que programmeur, vous travaillerez avec différentes structures de données en fonction de la portée de vos projets. L'un de ces concepts est une structure de données de file d'attente; les files d'attente sont essentielles pour les étudiants et sont utilisées dans de nombreux algorithmes importants. Comme les files d'attente, les files d'attente prioritaires partagent un concept similaire mais présentent quelques différences fondamentales.

Lisez la suite pour comprendre les files d'attente et les files d'attente prioritaires.

Qu'est-ce qu'une file d'attente ?

Une file d'attente est une structure de données simple qui a une variété d'applications dans des projets de codage réels. Les structures de données sont intrinsèquement abstraites, mais par souci de simplicité, nous imaginons qu'une structure de données de file d'attente a une forme linéaire avec deux extrémités différentes.

En termes de complexité temporelle, une file d'attente permet l'insertion (enqueue) et la suppression (dequeue) en temps O(1). En raison de son efficacité asymptotique, les files d'attente sont efficaces pour les grands ensembles de données. Les files d'attente sont de nature premier entré, premier sorti (FIFO), ce qui signifie qu'un élément de données inséré en premier sera accessible en premier. En revanche, les piles ont une nature dernier entré, premier sorti (LIFO) et n'ont qu'une seule extrémité ouverte.

Imaginez une file d'attente dans un cinéma; chaque nouveau client qui arrive rejoint la file d'attente à une extrémité. Un par un, chaque client achète un billet et quitte la file d'attente par le front-end. La structure de données de file d'attente fonctionne exactement comme n'importe quelle file d'attente réelle, et les données sont insérées (mise en file d'attente) à une extrémité et supprimées (défilement) à l'autre extrémité. Vous pouvez maintenant, espérons-le, comprendre pourquoi les files d'attente suivent une méthodologie FIFO.

Une file d'attente contient de nombreuses applications de codage réelles. Il est plus couramment utilisé dans les applications où les données n'ont pas besoin d'être traitées immédiatement mais plutôt dans un ordre FIFO. La planification de disque, le transfert de données asynchrone, les sémaphores sont quelques applications typiques. Les tâches de planification du premier arrivé, premier servi, telles que la mise en file d'attente d'impression ou les tampons de périphérique d'entrée, utilisent également une file d'attente.

Qu'est-ce qu'une file d'attente prioritaire ?

Une file d'attente prioritaire est similaire à une file d'attente, mais elle possède des propriétés supplémentaires. Lorsqu'un élément de données est mis en file d'attente dans la file d'attente prioritaire, un numéro de priorité lui est attribué. Contrairement au retrait d'une file d'attente standard, les éléments de données avec une priorité élevée sont retirés de la file d'attente avant les éléments de données avec une priorité faible. La priorité remplace l'ordre d'arrivée dans une file d'attente prioritaire, c'est pourquoi les files d'attente prioritaires n'ont pas une nature FIFO cohérente.

En rapport: Algorithmes que tout programmeur devrait connaître

Les programmeurs peuvent implémenter une file d'attente prioritaire de plusieurs manières. Une implémentation simple consiste à utiliser un tableau avec un élément de données struct/class, et l'élément de données contiendra la priorité de chaque élément de données et les données elles-mêmes. Une autre mise en œuvre de file d'attente de priorité primitive consiste à utiliser une liste chaînée. Les files d'attente prioritaires mises en œuvre via des listes chaînées sont fonctionnelles mais pas idéales en raison de leurs performances.

Vous pouvez implémenter une meilleure file d'attente prioritaire avec un tas. Si vous vous en souvenez, les tas binaires donnent l'élément maximum ou minimum en 0 (1) temps, et l'insertion ne prend que 0 (logN) temps. À l'aide de tas, les files d'attente prioritaires offrent asymptotiquement de meilleures performances par rapport aux files d'attente ou aux tableaux.

Une file d'attente prioritaire a également une variété d'applications essentielles. Les files d'attente prioritaires sont cruciales dans les algorithmes de graphes tels que l'algorithme Minimum Spanning Tree de Prim et l'algorithme Shortest Path de Dijkstra. Ils sont également idéaux dans les algorithmes de planification de processus d'unité de traitement informatique (CPU).

Apprendre les structures de données

Les files d'attente et les files d'attente prioritaires sont des structures de données importantes pour tous les débutants. Il est essentiel que les étudiants soient à l'aise pour mettre en œuvre ces structures de données et les utiliser dans différents projets.

D'autres structures de données telles que les tas, les piles et les arbres sont tout aussi importantes pour les étudiants et les professionnels. Il est également très courant que les intervieweurs interrogent les candidats sur les structures de données.

Après avoir lu cet article, vous devriez maintenant avoir une bonne idée du fonctionnement des files d'attente et des files d'attente prioritaires. Si tout semble encore un peu flou, vous vous familiariserez avec ceux-ci au fur et à mesure que vous acquerrez plus d'expérience dans leur utilisation.

Tas vs. Piles: qu'est-ce qui les distingue ?

Vous avez entendu parler de Heaps and Stacks, mais quand devriez-vous utiliser l'un plutôt que l'autre ?

Lire la suite

A propos de l'auteur