Pile (informatique)
La pile est l'une des structures de données les plus importantes en informatique. Pour comprendre le fonctionnement d'une pile, pensez à un jeu de cartes à jouer face cachée. On ne peut accéder facilement qu'à la carte qui se trouve au-dessus. Lorsque nous voulons regarder la carte du dessus, il y a deux choses que nous pouvons faire : nous pouvons la regarder, mais la laisser sur la pile, ou nous pouvons l'enlever. Lorsque nous enlevons l'objet du dessus, nous le retirons de la pile. Si nous voulons ajouter une autre carte au sommet de la pile, nous poussons.
Une pile est appelée une collection "last-in-first-out" (LIFO). Cela signifie que la dernière chose que nous avons ajoutée (poussée) est la première chose qui est retirée (tirée). Si la dernière carte que nous avons mise sur notre pile de cartes était un as, alors la première carte que nous avons tirée du haut est ce même as.
Deux actions sur une pile : pousser et faire sauter.
Histoire
La pile a été proposée pour la première fois en 1955, puis brevetée en 1957, par l'Allemand Friedrich L. Bauer. Le même concept a été développé indépendamment, à peu près à la même époque, par l'Australien Charles Leonard Hamblin.
Autres opérations
Dans les langages informatiques modernes, la pile est généralement mise en œuvre avec plus d'opérations que les simples "push" et "pop". Certaines implémentations ont une fonction qui renvoie la longueur actuelle de la pile. Une autre opération d'aide typique est "top" (également connu sous le nom de "peek"), qui peut renvoyer l'élément supérieur actuel de la pile sans le supprimer. Une autre opération courante est "dup", qui fait une copie de l'élément du haut de la pile.
Pages connexes
- Machine à empiler
