Ordre de stockage des données de pile

Question

Lorsque nous parlons d'une pile dans l'informatique ou dans la «vraie» vie, nous supposons généralement une fonctionnalité de type «premier on, dernier désactivé». Parce que l'idée d'une pile est basée sur quelque chose dans le monde physique, est-ce que la façon dont les données de la pile sont stockées a son importance?

Je remarque dans de nombreux exemples que le stockage des données de la pile est souvent effectué à l'aide d'un tableau et que l'élément le plus récent ajouté à la pile est placé au bas du tableau. (comme ajouter une nouvelle plaque à une pile de plaques existante, sauf la mettre sous les autres plaques plutôt que sur le dessus).

En tant que paradigme, est-il important de savoir dans quel ordre les données sont stockées dans la pile tant que le fonctionnement de la pile fonctionne comme prévu?

Answer 1

Peu importe comment stocker vos données dans la mémoire tant que la fonctionnalité et la performance sont comme prévu.

Souvent, les piles sont implémentées en tant que matrice avec une taille et une capacité où la taille est le nombre d'éléments actuellement dans la pile et la capacité est le nombre maximal pouvant être stocké sans nécessiter une réallocation de mémoire relativement coûteuse.

La capacité double généralement lorsque cela est nécessaire pour donner une performance O (1) amortie pour l'insertion. Il est généralement plus facile d'implémenter la pile avec l'espace vide à l'extrémité haute de l'ensemble, c'est ce qui est généralement fait.

Pour donner un exemple spécifique, le sommet actuel de la pile peut être stocké en tant qu'index dans le tableau de l'élément supérieur. Si les éléments ont été ajoutés à l'index le plus élevé du tableau vers le bas, alors lorsque le tableau est augmenté pour faire de la place pour plus d'éléments, l'index du haut du tableau changera également. Lors du remplissage à partir du bas, l'index de l'élément supérieur ne change pas lorsque le tableau doit être redimensionné.

Si vous souhaitez implémenter votre pile différemment, vous pouvez le faire, assurez-vous simplement que les fonctionnalités et les performances de votre implémentation sont documentées.

Answer 2

Pas vraiment. Cependant, comme il n'y a pas d'avantage de calcul (en général) pour déplacer les éléments poussés vers n'importe quelle autre position, une structure linéaire (qui peut fournir un accès rapide au "sommet" actuel de la pile) fonctionne aussi bien que n'importe quoi. Une matrice répond aux besoins d'une structure de pile en termes de performance et de compacité, c'est donc le meilleur choix.

Answer 3

En tant que paradigme, non, pas vraiment. En tant que détail d'implémentation de bas niveau, une pile qui se développe vers le bas présente le léger avantage que les éléments déjà sur la pile peuvent être adressés à partir du pointeur de pile courant en utilisant un décalage positif (par exemple cela peut être utile pour certaines architectures CPU).