Différence Entre Pile Et Tas

2024 Auteur: Mildred Bawerman | [email protected]. Dernière modifié: 2023-12-16 08:38

Pile vs tas

La pile est une liste ordonnée dans laquelle l'insertion et la suppression d'éléments de liste ne peuvent être effectuées qu'à une extrémité appelée le haut. Pour cette raison, la pile est considérée comme une structure de données dernier entré, premier sorti (LIFO). Le tas est une structure de données spéciale qui est basée sur des arbres et qui satisfait une propriété spéciale appelée propriété du tas. De plus, un tas est un arbre complet, ce qui signifie qu'il n'y a pas d'espace entre les feuilles de l'arbre, c'est-à-dire que dans un arbre complet, chaque niveau est rempli avant d'ajouter un nouveau niveau à l'arbre et que les nœuds d'un niveau donné sont remplis à partir de de gauche à droite.

Qu'est-ce que Stack?

Comme mentionné précédemment, stack est une structure de données dans laquelle des éléments sont ajoutés et supprimés d'une seule extrémité appelée le haut. Les piles ne permettent que deux opérations fondamentales appelées push et pop. L'opération push ajoute un nouvel élément au sommet de la pile. L'opération pop supprime un élément du haut de la pile. Si la pile est déjà pleine, lorsqu'une opération push est effectuée, elle est considérée comme un débordement de pile. Si une opération pop est effectuée sur une pile déjà vide, elle est considérée comme un dépassement de la pile. En raison du petit nombre d'opérations pouvant être effectuées sur une pile, celle-ci est considérée comme une structure de données restreinte. De plus, selon la façon dont les opérations push et pop sont définies, il est clair que les éléments ajoutés en dernier à la pile sortent en premier de la pile. Par conséquent, la pile est considérée comme une structure de données LIFO.

Qu'est-ce que Heap?

Comme mentionné précédemment, le tas est une arborescence complète qui satisfait la propriété du tas. La propriété Heap indique que, si y est un nœud enfant de x, alors la valeur stockée dans le nœud x doit être supérieure ou égale à la valeur stockée dans le nœud y (c'est-à-dire valeur (x) ≥ valeur (y)). Cette propriété implique que le nœud avec la plus grande valeur serait toujours placé à la racine. Un tas construit à l'aide de cette propriété est appelé un tas max. Il existe une autre variante de la propriété de tas qui indique le contraire. (c'est-à-dire valeur (x) ≤ valeur (y)). Cela implique que le nœud avec la plus petite valeur serait toujours placé à la racine, ainsi appelé un tas min. Il existe un large éventail d'opérations effectuées sur les tas telles que la recherche de minimum (en min-tas) ou maximum (en max-tas), la suppression de minimum (en min-tas) ou maximum (en max-tas),touche croissante (en tas max) ou décroissante (en tas min), etc.

Quelle est la différence entre Stack et Heap?

La principale différence entre les piles et les tas réside dans le fait que si la pile est une structure de données linéaire, le tas est une structure de données non linéaire. La pile est une liste ordonnée qui suit la propriété LIFO, tandis que le tas est une arborescence complète qui suit la propriété du tas. De plus, stack est une structure de données restreinte qui ne prend en charge qu'un nombre limité d'opérations comme push et pop, tandis que heap prend en charge un large éventail d'opérations telles que la recherche et la suppression du minimum ou du maximum, l'augmentation ou la diminution de la clé et la fusion.