Différence entre pile et file d'attente

Différence principale - pile vs file d'attente

En informatique, pile et file d'attente sont deux types de données abstraits qui sont de simples structures de données qui utilisent des pointeurs pour représenter des ensembles dynamiques. Cependant, une différence peut être notée entre eux en fonction de leurs implémentations. Les opérations de base d'insertion et de suppression d'éléments sont prises en charge à la fois par la pile et par la file d'attente. le différence principale entre Stack et Queue est qu'un empiler met en oeuvre Politique dernier entré premier sorti ou LIFO, alors qu'un queue met en oeuvre Premier entré, premier sorti ou politique FIFO.

Quelle est la pile

Une pile est un structure de données linéaire qui sert de collection d'éléments. Seule une extrémité de la structure est accessible pour effectuer des opérations sur les éléments, elle est communément appelée le Haut. Deux opérations principales peuvent être effectuées sur une pile; pousser et pop. Une opération 'insertion' effectuée sur une pile s'appelle pousser et une opération 'delete' effectuée sur une pile est appelée pop.

le pousser opération ajoute un élément en haut de la collection. Effectuer un pop opération supprime un élément qui se trouve en haut de la collection. Étant donné que les éléments retirés de la pile sont inversés par rapport à leur ajout, il est connu que la structure suit Last In First Out ou une approche LIFO. Compte tenu de cette implémentation, les éléments les plus bas sont sur la pile depuis le plus long.

Une pile est considérée comme un structure de données restreinte en raison du petit nombre d'opérations pouvant être effectuées sur une pile. En outre, un coup d'oeil operation peut être implémenté pour renvoyer la valeur de l'élément top sans modifier l'élément. De plus, les implémentations d’une pile ont souvent une Est vide fonction pour vérifier si la pile est vide. Dans les environnements fortement dépendants des piles, des fonctions telles que effacer, échange / échange et tourner peut également être fourni. Mais ceux-ci ne sont pas essentiels pour la fonctionnalité de base d'une pile.

Une pile a capacité limitée. Si la pile est pleine, elle déborde, ce qui signifie qu’il n’ya pas assez d’espace pour que plus d’éléments soient placés dans la pile. Si la pile est vide et qu'il n'y a aucun élément à afficher, la pile est dans un état de sous-flux..

Une pile peut être facilement implémentée à l'aide de tableaux ou de listes chaînées dans la plupart des langages de programmation de haut niveau..

Les piles sont applicables dans des domaines tels que l'évaluation des expressions arithmétiques, la gestion de la mémoire au moment de l'exécution, la traversée des arbres, l'analyse syntaxique, etc..

Quelle est la file d'attente

Une file d'attente est une structure de données linéaire qui sert également de collection d'éléments. Les deux extrémités d’une file sont accessibles pour effectuer des opérations sur des éléments et sont généralement appelées tête et queue. Deux opérations principales peuvent être effectuées sur une file d'attente; mettre en file d'attente et dequeue. En file d'attente est l'opération d'insertion alors que dequeue est l'opération de suppression effectuée sur une file d'attente.

Lorsqu'un élément est mis en file d'attente, il est ajouté à la queue de la file d'attente. Effectuer un dequeue opération supprimera un élément de la tête de la file d'attente. Etant donné que les éléments mis en file d'attente sont toujours retirés de la file d'attente dans le même ordre qu'ils ont été mis en file d'attente, la structure est supposée mettre en œuvre une approche premier entré premier sorti ou FIFO..

Semblable à une pile, une file d'attente est aussi un structure de données restreinte compte tenu du petit nombre d'opérations pouvant être effectuées. De plus coup d'oeil opération peut être implémentée dans une file d'attente, ce qui renverra la valeur de l'élément en tête de la file d'attente sans la retirer de la file d'attente. Les autres opérations primitives sur une file d'attente peuvent inclure Est vide, Est rempli, et afficher. le Est vide fonction vérifie si la file d'attente est vide et Est rempli vérifier si la file d'attente est pleine. le afficher Cette fonction peut être utilisée pour présenter le contenu de la file d'attente. Mais encore une fois, ces fonctions ne sont pas critiques pour l'implémentation d'une file d'attente.

 Contrairement à une pile, les files d'attente peuvent être implémentées pour avoir une capacité limitée ou sans capacité spécifique. Un état de dépassement de capacité d'une file d'attente se produit lorsqu'un élément est mis en file d'attente dans une file d'attente complète et un état de sous-dépassement se produit lorsqu'un élément est retiré de la file d'attente, mais que la file d'attente est vide..    

Le type de file d'attente peut différer selon la manière dont les opérations de mise en file d'attente et de retrait de la file d'attente sont effectuées sur des éléments. La file d'attente circulaire, la file d'attente prioritaire et la file d'attente à deux extrémités sont les types spéciaux de files d'attente.

À l'aide de tableaux et de listes chaînées, les files d'attente peuvent être efficacement implémentées dans des langages de programmation de haut niveau.

Les files d'attente sont applicables dans de nombreux domaines tels que les simulations, le traitement par lots dans les systèmes d'exploitation, les algorithmes de planification, les demandes de mise en mémoire tampon, les systèmes de plate-forme de multiprogrammation, etc..

Différence entre pile et file d'attente

Accessibilité aux éléments

 Dans un empiler, les opérations sur les données peuvent être effectuées uniquement en haut de la pile.

 Dans un queue, les deux extrémités de la file sont accessibles pour les opérations. Une insertion a lieu à la fin de la file d'attente et une suppression peut être effectuée en tête..

Comportement

UNE empiler est une structure de données LIFO, où l'élément qui a été ajouté en dernier à la pile est le premier élément à être supprimé. L'enlèvement est dans l'ordre inverse de l'ordre d'addition.

UNE queue est une structure de données FIFO, où l'élément qui a été ajouté en premier à la file d'attente sera le premier élément à être supprimé. L'ordre d'insertion et de retrait sont les mêmes.

Opérations de base

Dans un empiler, un élément est inséré au sommet de la pile et retiré du haut aussi.

Mais dans un queue, un élément est inséré à la fin d'une file d'attente et est retiré de l'avant.

Capacité

UNE empiler a une capacité limitée.

 UNE queue peut être de capacité limitée, mais est généralement mis en œuvre sans capacité spécifique.

Gaspillage d'espace mémoire

Depuis un empiler Un seul pointeur est nécessaire pour garder une trace du haut de la pile, il n’ya pas de gaspillage d’espace mémoire..

UNE queue a besoin de deux pointeurs "avant" et "arrière" pour garder une trace des deux extrémités de la file d'attente. Par conséquent, il y a un gaspillage d'espace mémoire.

Pile contre file d'attente - Résumé

La pile et la file d'attente sont utilisées dans le but de maintenir des listes ordonnées d'éléments. Alors qu'une pile est une structure de données LIFO, une file d'attente implémente une approche FIFO. Seule une extrémité d'une pile est accessible pour les opérations principales, mais les deux extrémités d'une file peuvent être utilisées.