• 4 heures
  • Facile

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 20/05/2019

Découvrez les piles et les files

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Dans le chapitre précédent, nous avons vu trois structures de données qui permettent de regrouper des informations et de les retrouver.

Mais que se passe-t-il si vous voulez accéder à vos données selon leur ordre d’arrivée ? Par exemple, si vous voulez trouver en premier la toute dernière information ajoutée ?

Laissez-moi vous présenter les piles et les files !

Qu’est-ce qu’une pile ?

Présentation

Il s’agit d’une structure de données qui donne accès en priorité aux dernières données ajoutées. Ainsi, la dernière information ajoutée sera la première à en sortir.

Les piles sont ce que l’on appelle un traitement des données LIFO (Last In First Out, ou dans la langue de Molière : dernier ajouté premier parti), très pratique lorsque nous aurons à utiliser en premier les dernières données ajoutées.

Les piles sont très utilisées sur les plateformes de streaming musical. Lorsque vous demandez à la plateforme de lire une chanson à la suite, elle va ajouter cette dernière tout en haut de la liste "en attente de lecture".

Mais que se passe-t-il si nous avons besoin d’accéder non pas aux dernières données ajoutées, mais aux premières ? C’est exactement ce qui se passe lorsque vous constituez une liste de musique. Vous ajoutez peu à peu les chansons qui seront lues dans le même ordre : les premières chansons ajoutées sont les premières lues. Impossible de réaliser cela avec une pile. C’est pourquoi les files existent !

Implémentation

En C et en Python, vous pouvez utiliser des tableaux pour créer des piles. En effet, vous pouvez ajouter très facilement un élément au début d’un tableau et le retrouver.

Qu’est-ce qu’une file ?

Présentation

Une file (queue en anglais) est une structure de données dans laquelle on accède aux éléments suivant la règle du premier arrivé premier sorti, ou encore FIFO (First In First Out).

Elle suit la même logique que les files d’attente (au McDrive, à Pôle Emploi...) : plus vous arrivez tôt et plus vous partez tôt ! ;-)

Prenons un exemple de notre vie courante. Vous vous rendez à la Poste, car vous avez reçu un colis. Vous prenez un ticket qui vous indique votre ordre dans la file d’attente. Vous comparez alors ce numéro avec celui qui s’affiche et vous avez une idée du nombre de personnes avant vous. Vous râlez : si seulement vous étiez arrivé·e plus tôt, vous auriez moins attendu ! Premier arrivé, premier servi (et premier parti !)...

Implémentation

En C, une file peut être implémentée par une liste chaînée ou par un tableau avec une gestion circulaire.

En Python, vous préférerez utiliser le type Deque.

Les programmeurs l’utilisent dans des services de commande en ligne (commande de pizza sur Internet) ou dans les plateformes de gestion de la clientèle (le premier à avoir posé une question est le premier servi).

En résumé

Les piles (de type LIFO) s’utilisent lorsque vous devez traiter en priorité les dernières données arrivées. Nous retrouvons ce système dans les placards de notre cuisine ou dans notre frigo : ce qui est mis en avant est ce que l’on va consommer le plus vite ! C’est également le cas dans le flux d’actualité de Facebook ou de Twitter (la dernière information arrivée est la première que vous voyez).

Les files (de type FIFO) s’utilisent lorsque vous devez traiter un flux de données par ordre d’arrivée. C’est le cas lorsque vous faites une todo list (votre première action est celle qui vous devez réaliser en priorité) ou que vous listez les bugs en attente de traitement.

Opérations courantes

Les opérations courantes de ces deux structures sont appelées primitives de gestion des piles ou des files. Les noms sont assez parlants ! :)

Piles :

  • Initialiser

  • EstVide

  • EstPleine

  • AccederSommet

  • Empiler

  • Depiler

  • Vider

  • Détruire

Files :

  • Initialiser

  • EstVide

  • EstPleine

  • AccederTete

  • Enfiler

  • Defiler

  • Vider

  • Detruire

Dans le chapitre suivant, nous nous intéresserons à deux structures de données bien utiles pour retrouver des données selon les liens qu’elles entretiennent les unes avec les autres. À tout de suite !

Exemple de certificat de réussite
Exemple de certificat de réussite