Blog

Nov 14, 2023

FIFO vs LIFO : 4 différences

FIFO et LIFO sont deux types de structures de données couramment utilisées en programmation.

FIFO et LIFO sont deux types de structures de données couramment utilisées en programmation.

LIFO vs FIFO dans la programmation

Source : LinkedInOuvre une nouvelle fenêtre

LIFO signifie "dernier entré, premier sorti" et utilise une structure de données en pile. Dans une structure de données LIFO, le dernier élément ajouté à la pile est traité en premier. D'autre part, FIFO signifie "premier entré, premier sorti" et utilise une structure de données de file d'attente. Dans une structure de données FIFO, le premier élément ajouté à la file d'attente est traité en premier.

La structure de données premier entré, premier sorti est couramment utilisée en programmation comme méthode de gestion et de manipulation d'éléments de données dans un système informatique. Comme son nom l'indique, FIFO donne la priorité aux processus qui sont "premiers entrés", ce qui signifie qu'il traitera d'abord l'élément qui est entré dans le système avant tout autre.

FIFO exploite une structure de données de type file d'attente dans laquelle l'élément le plus ancien reste au premier plan, en attente d'un traitement préférentiel. Considérez le FIFO comme « premier arrivé, premier servi » pour les éléments de programmation, comme une file d'attente à la caisse au supermarché où la première personne en ligne est servie en premier.

La structure de données de type file d'attente utilisée par FIFO est une méthode simple et intuitive de traitement des données et est utilisée dans de nombreuses applications. Il est adapté aux cas d'utilisation où le traitement d'un grand nombre de demandes est requis, car il permet de traiter ces demandes dans l'ordre dans lequel elles ont été reçues et évite les perturbations du flux de travail. Comme la requête la plus ancienne est traitée en premier, le FIFO est considéré comme une méthode « équitable » de traitement des données.

Dans FIFO, les éléments sont ajoutés à la fin de la file d'attente à l'aide de l'opération « mettre en file d'attente », et le premier élément est supprimé pour être traité à l'aide de l'opération « retirer de la file d'attente ». La mise en file d'attente et la sortie de file d'attente dans FIFO peuvent être visualisées comme un tapis roulant où les éléments sont ajoutés à une extrémité et retirés de l'extrémité opposée.

Un avantage significatif de l'utilisation de FIFO est sa simplicité. Il s'agit d'une structure de données simple et facile à comprendre utilisée dans de nombreux langages de programmation. Un autre avantage de FIFO est sa pertinence pour les applications où les éléments de données doivent être traités dans un ordre strict. Par exemple, dans une file d'attente d'impression, vous voudriez traiter les demandes d'impression dans l'ordre dans lequel elles ont été reçues. FIFO garantit que la demande d'impression la plus ancienne est traitée en premier.

En savoir plus : Qu'est-ce que l'analyse des causes profondes ? Travail, modèles et exemples

La méthode de traitement des données dernier entré, premier sorti est également couramment utilisée en programmation. Dans cette méthode, le système traite d'abord l'entrée la plus récente, ou « la plus récente ». LIFO est courant dans les cas où la saisie de données la plus récente est la plus importante - pensez aux opérations d'annulation-rétablissement ou à une liste d'historique Internet.

Le principe de base de LIFO est que le dernier élément à être stocké sera le premier à être traité. Les éléments les plus récents sont placés au-dessus des plus anciens, et les "plus récents" sont retirés du haut pour être traités. L'entrée et la sortie des données étant identiques, l'élément le plus ancien, qui a été le premier à rencontrer l'opération, est le dernier à être traité car il reste en bas de la pile.

Considérez la pile LIFO comme une pile d'assiettes où les assiettes ajoutées en dernier sont également sélectionnées en premier. Cela contraste fortement avec la structure de données de type file d'attente utilisée dans FIFO, où le premier élément entrant dans la file d'attente est également le premier à être traité. Les éléments LIFO sont ajoutés à la fin de la pile à l'aide d'une opération push. L'élément le plus récent est traité avec une opération pop.

LIFO est mieux adapté aux applications qui ne se concentrent pas sur l'ordre de traitement des données et accordent plutôt plus d'importance à la récence des données. Par exemple, les navigateurs Web permettent aux utilisateurs de naviguer entre les pages Web visitées à l'aide des boutons « Précédent » et « Suivant ». Cette fonctionnalité utilise une structure de données LIFO pour stocker l'historique des pages Web visitées. Une fois que le bouton "Retour" est enfoncé, le navigateur récupère la dernière page Web visitée à partir du haut de la pile de données et redirige l'utilisateur vers celle-ci.

En savoir plus : Qu'est-ce qu'ETL (Extraire, Transformer, Charger) ? Signification, processus et outils

Comprenons plus en détail les principales différences entre les méthodes FIFO et LIFO.

Cette structure de données suit le principe FIFO, ce qui signifie que de nouvelles entités sont ajoutées à l'arrière de la file d'attente et que les entités au début de la file d'attente sont traitées en premier.

Comme une file d'attente régulière de personnes à la billetterie d'un cinéma ou à la caisse d'un supermarché, la structure de données de type file d'attente a deux extrémités. Une extrémité est l'avant, où les entités sont supprimées pour le traitement. L'autre extrémité est le dos, où de nouvelles entités sont ajoutées.

Lorsqu'une nouvelle entité doit être ajoutée à l'arrière de la file d'attente, le processus de « mise en file d'attente » est exécuté. D'un autre côté, lorsqu'une entité doit être retirée du début de la file d'attente pour être traitée, le processus de « retrait de la file d'attente » est exécuté.

Une autre opération effectuée dans les structures de données de type file d'attente est connue sous le nom de "peek", où l'entité au début de la file d'attente est affichée sans sa suppression.

Cette structure de données est utilisée dans de nombreux systèmes informatiques pour stocker et traiter des données. Par exemple, les commutateurs réseau, les ponts et les routeurs utilisent FIFO pour conserver les paquets de données pendant qu'ils sont transportés vers leur destination.

La mise en œuvre de la file d'attente s'effectue à l'aide de différentes structures de données, notamment des tableaux et des listes chaînées. Une file d'attente n'a pas de limite de capacité théorique ; cependant, dans la pratique, les « files d'attente délimitées » peuvent présenter une capacité fixe.

Il existe de nombreuses implémentations efficaces des files d'attente FIFO. Ils peuvent effectuer des processus d'ajout et de suppression d'entités en temps constant (O(1)). Certains langages de programmation fournissent une prise en charge intégrée des files d'attente ; par exemple, l'interface 'queue' dans la bibliothèque Java et la classe modélisée 'queue' dans la bibliothèque de modèles standard C++.

Alors que la première opération ajoute un élément à la collection, la seconde supprime l'élément le plus récemment ajouté qui n'a pas encore été supprimé. L'ordre LIFO des éléments est suivi dans une pile.

Tout comme une pile réelle d'éléments physiques placés les uns sur les autres (comme une pile d'assiettes), les éléments de données du dessus doivent être supprimés avant ceux situés plus profondément dans la pile.

Comme une structure de données de type file d'attente, une pile est également linéaire. Plus abstraitement, il peut être vu comme une collection séquentielle dans laquelle les opérations push et pop ne se produisent qu'à une extrémité de la structure - le «sommet» de la pile.

Cette structure de données permet d'implémenter une pile sous la forme d'une liste chaînée et d'un pointeur vers l'élément supérieur.

Dans plusieurs implémentations, les piles ont plus d'opérations que les simples "push" et "pop". Par exemple, l'opération 'top of stack', similaire à l'opération 'peek' dans une file d'attente, permet d'observer l'élément du haut sans le retirer de la pile.

Si une pile vide est rencontrée, une condition de sous-dépassement se produira lors de l'exécution des opérations 'top of stack' ou 'pop'. De plus, des implémentations existent pour permettre de vérifier si la pile est vide et la taille de la pile.

L'implémentation de la pile peut avoir lieu via une liste chaînée ou un tableau. Les piles peuvent être considérées comme des cas particuliers de listes et ne sont pas identifiées par l'implémentation mais par l'interface - l'utilisateur ne peut pousser ou faire apparaître des éléments sur la liste liée ou le tableau qu'avec quelques autres opérations d'assistance.

Une application clé du FIFO est dansalgorithmes de planification de disqueoù les contrôleurs de disque utilisent FIFO pour définir l'ordre d'exécution des processus.

De plus, de nombreuses structures de données utilisent FIFO pour le traitement des données. La structure principale qui utilise FIFO est lafile d'attente ; cependant, d'autres variantes utilisent également la technique FIFO.

FIFO est également utilisé danscommunication et mise en réseau , où les paquets de données restent entre les routeurs dans l'ordre requis en exploitant FIFO. Cette technique permet au routeur de spécifier l'ordre dans lequel les paquets doivent être transférés.

Enfin, FIFO est utilisé dansalgorithmes du système d'exploitation . Les processus sont sélectionnés pour le temps CPU dans l'ordre d'arrivée. Par exemple, lorsque plusieurs processus attendent l'accès au processeur, les processus arrivés plus tôt sont priorisés par le système d'exploitation. Cela garantit que tous les processus reçoivent le temps CPU de manière équitable.

Une utilisation courante de LIFO est dans les structures de données. Leempiler est la structure de données principale suivant l'approche LIFO. Il est utilisé dans plusieurs langages de programmation pour le stockage et la gestion des données. La structure de données de la pile a plusieurs applications, notamment l'évaluation d'expressions, la gestion de la mémoire et les appels de fonctions.

LIFO voit également l'utilisation dansgestion de la mémoire . Par exemple, l'algorithme d'allocation de mémoire de pile exploite LIFO. Ici, l'allocation et la désallocation de mémoire ont lieu dans une structure semblable à une pile. Lors de l'appel, les données de la fonction sont stockées dans la pile et sont supprimées lors du retour.

Une application courante de LIFO est dans le'Histoire' fonctionnalité des navigateurs Web. Lorsqu'un utilisateur visite une page Web, son URL est capturée et ajoutée au « sommet » de la pile, avec les autres URL visitées. Une fois que le bouton "Retour" est enfoncé, la page Web la plus récemment visitée est supprimée du haut de la pile et affichée à l'utilisateur.

Un autre exemple de LIFO estannuler et rétablir les opérations en informatique. Par exemple, si vous utilisez un traitement de texte et que vous souhaitez annuler une modification de mise en forme, vous utilisez les touches Contrôle (ou Commande) et Z ensemble. L'état de formatage précédent est ensuite récupéré et réappliqué par le logiciel de traitement de texte à l'aide d'une structure de données LIFO. De même, si un utilisateur vient d'envoyer un fichier à la corbeille sur son appareil et souhaite annuler la suppression, il appuie simplement sur le bouton "Annuler", et l'application récupère et restaure le fichier le plus récemment supprimé à partir du haut de la pile de données des fichiers supprimés.

Enfin, les réseaux informatiques utilisent LIFO dans la « file d'attente dernier entré, premier sorti ». Cela aide les routeurs à spécifier l'ordre dans lequel les paquets de données doivent être transmis entre les systèmes. Ici, LIFO aide à garantir que les paquets de données atteignent le destinataire prévu dans un ordre logique.

Un autre avantage de la méthode FIFO est saapproche équitable à travers les processus . Le premier processus reçu sera le premier exécuté, selon le principe du premier arrivé, premier servi (FCFS). Cela garantit une opportunité égale d'utilisation du processeur pour tous les processus et minimise la possibilité d'une interruption intempestive ou d'un dysfonctionnement.

Sur le plan dechronologie , FIFO garantit que l'élément le plus ancien de la file d'attente reçoit un traitement préférentiel. Ceci est réalisé en gardant l'élément le plus ancien au début de la file d'attente et en permettant un accès rapide.

Comme il n'est plus nécessaire de trouver l'élément le plus ancien, leprocessus de récupération devient plus efficace. La méthode FIFO élimine également les critères « d'attente et de maintien », ce qui réduit le temps de traitement des données.

Enfin, l'approche FIFO comporteconsommation de mémoire fixe . C'est un avantage notable car cela permet à l'utilisation de la mémoire de rester constante quel que soit le nombre d'opérations exécutées. Cet avantage est un sous-produit du fait que FIFO n'a pas besoin de structures de données supplémentaires pour gérer ses éléments.

L'approche LIFO donne un traitement préférentiel au dernier élément à entrer. Ceci est particulièrement utile lorsque lela plupart des éléments nouvellement ajoutés doivent être traités rapidementsans que le reste de l'opération doive être complété.

Enfin, LIFO est bénéfique pour les applications dans lesquelles les utilisateurs ont besoin d'accéder aux informations les plus récentes en termes dechronologie, comme le suivi des marchés boursiers ou l'analyse des données financières.

De plus, le FIFOne permet pas d'accéder aux éléments de manière aléatoire . Cela empêche le processeur d'accéder à tout élément mis en file d'attente à l'exception du premier et peut entraîner une inefficacité dans certains processus où le processeur peut avoir besoin d'accéder à un élément particulier au milieu de la file d'attente.

Enfin, alors que FIFO est connu pour son équité lors de l'exécution du processus, ilne peut pas prendre en charge la hiérarchisation des processus . Cela peut amener les processus critiques à attendre que les processus réguliers ou de moindre priorité soient terminés, ce qui affecte l'efficacité du système.

Un autre inconvénient de LIFO est sonrigidité ; ce n'est peut-être pas un choix efficace pour les applications nécessitant un algorithme plus sophistiqué.

Enfin, LIFO estpas efficace dans la gestion de la mémoire . En effet, contrairement à FIFO (où la consommation de mémoire est fixe), l'utilisation de la mémoire dans LIFO change à chaque opération et une taille fixe ne peut pas être fournie pour la mémoire consommée. Étant donné que la consommation de mémoire pour LIFO n'est pas prédéterminée, il est difficile d'assurer une allocation efficace des ressources.

En savoir plus : Qu'est-ce que le BDD (Behavior Driven Development) ? Signification, processus et exemples

La principale différence entre premier entré, premier sorti (FIFO) et dernier entré, premier sorti (LIFO) dans la programmation réside dans l'ordre des éléments traités. FIFO traite le premier élément dans l'ordre du premier sorti, tandis que LIFO traite le dernier élément dans l'ordre du premier sorti.

La FIFO est préférable pour les applications où l'ordre d'arrivée est important et où les données chronologiquement les plus anciennes, telles que le transfert de paquets de données, sont plus importantes. À l'inverse, LIFO est préféré pour les applications où l'ordre d'arrivée est moins significatif et où les données chronologiquement plus récentes sont d'une importance clé, telles que les appels de fonction et les opérations d'annulation-rétablissement.

En termes de structures de données, FIFO est implémenté comme une file d'attente, tandis que LIFO est implémenté comme une pile. Les deux méthodes ont des avantages et des inconvénients, et le choix entre elles dépend en fin de compte des exigences particulières de l'application de programmation en cours de développement.

Cet article vous a-t-il aidé à comprendre les principales différences entre FIFO et LIFO en programmation ? Partagez vos impressions avec nous sur FacebookOpens a new window , TwitterOpens a new window , ou LinkedInOpens a new window !

Source de l'image : Shutterstock

Rédacteur technique