La pile n'a qu'une extrémité ouverte pour pousser et extraire les éléments de données, tandis que Queue est ouverte pour la mise en file d'attente et la mise en file d'attente des éléments de données.
La pile et la file d'attente sont les structures de données utilisées pour stocker les éléments de données et sont basées sur un équivalent du monde réel. Par exemple, la pile est une pile de CD où vous pouvez extraire et insérer un CD en haut de la pile de CD. De même, la file d'attente est une file d'attente de billets de théâtre dans laquelle la personne qui se trouve en premier lieu, c'est-à-dire devant la file d'attente, sera servie en premier et la nouvelle personne qui arrive apparaîtra à l'arrière de la file d'attente (arrière de la file d'attente).
Tableau de comparaison
| Base de comparaison | Empiler | Queue |
|---|---|---|
| Principe de fonctionnement | LIFO (dernier entré, premier sorti) | FIFO (premier entré premier sorti) |
| Structure | Même fin est utilisé pour insérer et supprimer des éléments. | Une extrémité est utilisée pour l'insertion, c'est-à-dire l'arrière et une autre extrémité est utilisée pour la suppression d'éléments, c'est-à-dire l'avant. |
| Nombre de pointeurs utilisés | Un | Deux (dans le cas d'une simple file d'attente) |
| Opérations effectuées | Push et Pop | En file d'attente et dequeue |
| Examen de l'état vide | Haut == -1 | Avant == -1 || Avant == Arrière + 1 |
| Examen de l'état complet | Top == Max - 1 | Arrière == Max - 1 |
| Des variantes | Il n'a pas de variantes. | Il a des variantes comme la file d'attente circulaire, la file d'attente prioritaire, la file d'attente doublée. |
| la mise en oeuvre | Plus simple | Comparativement complexe |
Définition de pile
Une pile est une structure de données linéaire non primitive. Il s'agit d'une liste ordonnée dans laquelle le nouvel élément est ajouté et l'élément existant est supprimé d'une seule extrémité, appelée en haut de la pile (TOS). Comme toute la suppression et l’insertion dans une pile se font à partir du haut de la pile, le dernier élément ajouté sera le premier à être retiré de la pile. C’est la raison pour laquelle la pile est appelée type de liste LIFO (Last-in-First-Out).
Notez que l'élément souvent accédé dans la pile est l'élément le plus haut, alors que le dernier élément disponible est au bas de la pile.
Exemple
Certains d'entre vous peuvent manger des biscuits (ou des pavots). Si vous présumez, un seul côté de la couverture est déchiré et les biscuits sont sortis un à un. C’est ce que l’on appelle le «popping». De même, si vous souhaitez conserver quelques biscuits plus tard, vous les replacerez dans l’emballage par la même extrémité déchirée appelée poussée.
Définition de la file d'attente
Une file d'attente est une structure de données linéaire entrant dans la catégorie du type non primitif. C'est une collection d'éléments similaires. L'ajout de nouveaux éléments a lieu à une extrémité appelée extrémité arrière. De la même manière, la suppression des éléments existants a lieu à l’autre extrémité, appelée Front-end, et il s’agit logiquement d’un type de liste FIFO (First In First Out).
Exemple
Dans notre vie quotidienne, nous rencontrons de nombreuses situations dans lesquelles nous attendons le service souhaité, nous devons donc nous mettre en file d'attente pour que notre tour soit réparé. Cette file d'attente peut être considérée comme une file d'attente.
Différences clés entre pile et file d'attente
- Par contre, Stack suit le mécanisme LIFO. Queue suit le mécanisme FIFO pour ajouter et supprimer des éléments.
- Dans une pile, la même fin est utilisée pour insérer et supprimer les éléments. Au contraire, deux extrémités différentes sont utilisées dans la file d'attente pour insérer et supprimer les éléments.
- Comme Stack n'a qu'une extrémité ouverte, c'est la raison pour laquelle un seul pointeur est utilisé pour faire référence au haut de la pile. Mais la file d'attente utilise deux pointeurs pour faire référence aux parties avant et arrière de la file d'attente.
- Stack effectue deux opérations appelées push et pop, tandis que dans Queue, elle est appelée en file d'attente et en file d'attente.
- L'implémentation en pile est plus facile que l'implémentation en file d'attente est délicate.
- La file d'attente comporte des variantes telles que la file d'attente circulaire, la file d'attente prioritaire, la file d'attente à double extrémité, etc. En revanche, la pile n'a pas de variante.
Mise en oeuvre de pile
La pile peut être appliquée de deux manières:
- L'implémentation statique utilise des tableaux pour créer une pile. La mise en œuvre statique est certes une technique sans effort, mais elle n’est pas une méthode de création flexible, car la déclaration de la taille de la pile doit être faite lors de la conception du programme, après quoi la taille ne peut pas être modifiée. De plus, l'implémentation statique n'est pas très efficace en ce qui concerne l'utilisation de la mémoire. Puisqu'un tableau (pour implémenter la pile) est déclaré avant le début de l'opération (au moment de la conception du programme). Maintenant, si le nombre d'éléments à trier est très inférieur à la pile, la mémoire allouée de manière statique sera gaspillée. D'autre part, s'il y a plus d'éléments à stocker dans la pile, nous ne pouvons pas modifier la taille du tableau pour augmenter sa capacité, afin qu'il puisse accueillir de nouveaux éléments.
- L'implémentation dynamique est également appelée représentation de liste liée et utilise des pointeurs pour implémenter le type de pile de structure de données.
Mise en oeuvre de la file d'attente
La file d'attente peut être implémentée de deux manières:
- Implémentation statique : si une file d'attente est implémentée à l'aide de tableaux, le nombre exact d'éléments que nous souhaitons stocker dans la file d'attente doit être garanti avant, car la taille du tableau doit être déclarée au moment de la conception ou avant le début du traitement. Dans ce cas, le début du tableau deviendra l'avant de la file d'attente et le dernier emplacement du tableau agira à l'arrière de la file d'attente. La relation suivante indique que tous les éléments existent dans la file d'attente lors de l'implémentation à l'aide de tableaux:
avant - arrière + 1
Si «arrière <avant», il n'y aura aucun élément dans la file d'attente ou la file d'attente sera toujours vide. - Implémentation dynamique : lors de l'implémentation de files d'attente à l'aide de pointeurs, le principal inconvénient est qu'un nœud d'une représentation liée consomme plus d'espace mémoire qu'un élément correspondant de la représentation de tableau. Puisqu'il y a au moins deux champs dans chaque nœud, l'un pour le champ de données et l'autre pour stocker l'adresse du nœud suivant, alors que dans la représentation liée, seul le champ de données est présent. Le mérite d'utiliser la représentation liée devient évident lorsqu'il est nécessaire d'insérer ou de supprimer un élément au milieu d'un groupe d'autres éléments.
Opérations sur pile
Les opérations de base pouvant être effectuées sur la pile sont les suivantes:
- PUSH : lorsqu'un nouvel élément est ajouté en haut de la pile est appelé opération PUSH. Le fait de pousser un élément dans la pile entraîne l'ajout de l'élément, car le nouvel élément sera inséré en haut. Après chaque opération de poussée, le sommet est augmenté de un. Si le tableau est plein et qu'aucun nouvel élément ne peut être ajouté, il est appelé condition STACK-FULL ou STACK OVERFLOW. OPÉRATION DE POUSSÉE - fonction en C:
Considérant que la pile est déclarée commeint stack [5], top = -1;void push(){int item;if (top < 4){printf ("Enter the number") ;scan ("%d", & item) ;top = top + 1;stack [top] = item;}else{printf (" Stack is full");}} - POP : Lorsqu'un élément est supprimé du haut de la pile, il est appelé opération POP. La pile est diminuée de un, après chaque opération de pop. S'il ne reste aucun élément sur la pile et que le pop-up est effectué, la condition STACK UNDERFLOW apparaîtra, ce qui signifie que votre pile est vide. POP OPERATION - fonctions en C:
Considérant que la pile est déclarée commeint stack [5], top = -1;void pop(){int item;if (top >= 4){item = stack [top];top = top - 1;printf ("Number deleted is = %d", item) ;}else{printf (" Stack is empty");}}
Opérations sur une file d'attente
Les opérations de base pouvant être effectuées sur la file d'attente sont les suivantes:
- Enqueue : Pour insérer un élément dans une file d'attente. Fonction d'opération de mise en file d'attente dans C:
La file d'attente est déclarée commeint queue [5], Front = -1 and rear = -1;void add (){int item;if ( rear < 4){printf ("Enter the number") ;scan ("%d", & item) ;if (front == -1){front =0 ;rear =0 ;}else{rear = rear + 1;}queue [rear] = item ;}else{printf ("Queue is full") ;}} - Dequeue : Pour supprimer un élément de la file d'attente. Fonction d'opération de mise en attente dans C:
La file d'attente est déclarée commeint queue [5], Front = -1 and rear = -1;void delete (){int item;if ( front ! = -1){item = queue [ front ] ;if (front == rear){front =-1 ;rear =-1 ;}else{front = front + 1;printf ("Number deleted is = %d", item) ;}}else{printf ("Queue is empty") ;}}
Applications de la pile
- Analyser dans un compilateur.
- Machine virtuelle Java.
- Annuler dans un traitement de texte.
- Bouton Précédent dans un navigateur Web.
- Langage PostScript pour les imprimantes.
- Implémentation d'appels de fonction dans un compilateur.
Applications de file d'attente
- Tampons de données
- Transfert de données asynchrone (fichier IO, pipes, sockets).
- Attribution de requêtes sur une ressource partagée (imprimante, processeur).
- Analyse du trafic.
- Déterminez le nombre de caissiers à avoir dans un supermarché.
Conclusion
Stack et Queue sont des structures de données linéaires qui diffèrent de certaines manières comme le mécanisme de travail, la structure, la mise en oeuvre, les variantes, mais les deux sont utilisées pour stocker les éléments dans la liste et effectuer des opérations sur la liste, comme l'ajout et la suppression d'éléments. Bien qu'il existe certaines limitations de la file d'attente simple qui est récupérée à l'aide d'autres types de file d'attente.
