Quelle est la différence entre un tableau et une pile?

Selon Wikipedia, une pile :

est un type de données abstrait de type dernier entré, premier sorti (LIFO) et une structure de données linéaire.

Alors qu'un tableau :

est une structure de données constituée d'une collection d'éléments (valeurs ou variables), chacun identifié par au moins un index ou une clé de tableau.

Pour autant que je comprends, ils sont assez similaires. Alors, quelles sont les principales différences? S'ils ne sont pas identiques, que peut faire un tableau qu'une pile ne peut pas et vice versa?

Eh bien, vous pouvez certainement implémenter une pile avec un tableau. La différence réside dans l'accès. Dans un tableau, vous avez une liste d'éléments et vous pouvez accéder à n'importe lequel d'entre eux à tout moment. (Pensez à un tas de blocs de bois tous disposés dans une rangée.)

Mais dans une pile, il n'y a pas d'opération d'accès aléatoire; il n'y en a que Push, Peeket Pop, qui traitent tous exclusivement de l'élément en haut de la pile. (Pensez maintenant aux blocs de bois empilés verticalement. Vous ne pouvez rien toucher sous le sommet de la tour, sinon il tombera.)

Dans une pile pure, les seules opérations autorisées sont Push, Popet Peekmais en termes pratiques, ce n'est pas exactement vrai. Ou plutôt, l' Peekopération vous permet souvent de regarder n'importe quelle position sur la pile, mais le hic est qu'elle est relative à une extrémité de la pile.

Ainsi, comme d'autres l'ont dit, un tableau est à accès aléatoire et tout est référencé au début du tableau .

Dans une pile, vous pouvez uniquement ajouter / supprimer à l'extrémité de travail de la pile, mais vous avez toujours un accès aléatoire en lecture, mais il est référencé à l'extrémité de travail . Voilà la différence fondamentale.

Par exemple, lorsque vous passez des paramètres sur une pile à une fonction, l'appelé n'a pas à supprimer les paramètres pour les consulter. Il pousse simplement les variables locales sur la pile et fait référence à toutes les variables et paramètres locaux en fonction d'un décalage par rapport au pointeur de la pile. Si vous utilisiez simplement un tableau, comment l'appelé pourrait-il savoir où chercher ses paramètres? Lorsque l'appelé a terminé, il supprime ses variables locales, envoie une valeur de retour, renvoie le contrôle à l'appelant, et l'appelant affiche la valeur de retour (le cas échéant), puis supprime les paramètres de la pile. La beauté est que cela fonctionne peu importe à quel point vous êtes imbriqué dans vos appels de fonction (en supposant que vous ne manquez pas d'espace de pile).

C'est une utilisation / implémentation particulière, mais cela illustre la différence: le tableau est toujours référencé depuis le début mais les piles sont toujours référencées à partir d'une position de fin de travail.

Une implémentation possible d'une pile est un tableau plus un index pour se rappeler où se trouve l'extrémité de travail.

Je pense que la plus grande confusion qui règne ici est la mise en œuvre par rapport aux structures de données de base.

Dans la plupart des langues (plus basiques), un tableau représente un ensemble d'éléments de longueur fixe auxquels vous pouvez accéder à tout moment. Le fait que vous ayez un tas d'éléments comme celui-ci ne vous dit rien sur la façon dont il est censé être utilisé (et franchement, un ordinateur ne saura pas / ne se souciera pas de la façon dont vous l'utilisez, tant que vous n'en violez pas l'utilisation).

Une pile est une abstraction utilisée pour représenter des données qui doivent être traitées d'une certaine manière. Il s'agit d'un concept abstrait car il dit simplement qu'il doit avoir un sous-programme / une méthode / une fonction qui peut s'ajouter en haut ou supprimer du haut, tandis que les données en dessous du haut ne sont pas touchées. Purement votre choix d'utiliser un tableau de cette façon.

Vous pouvez créer une pile à partir de différents types de structures de données: des tableaux (avec une taille maximale), des tableaux dynamiques (qui peuvent augmenter lorsqu'ils manquent d'espace) ou des listes liées. Personnellement, je pense qu'une liste chaînée représente le mieux les restrictions d'une pile, car vous devez faire un peu d'effort pour voir les choses au-delà du premier élément et il est très facile d'ajouter à l'avant et de supprimer de l'avant.

Vous pouvez donc utiliser un tableau pour créer une pile, mais ils ne sont pas équivalents

Leurs responsabilités sont différentes:

• La pile doit être capable de faire sauter des éléments sur la pile et de pousser des éléments de la pile, d'où la raison pour laquelle elle a normalement des méthodes Pop()etPush()

• La responsabilité du tableau est d'obtenir l'élément / set à un index spécifié

Vous pouvez récupérer un élément à partir de n'importe quel index d'un tableau A \.

Avec une pile, vous pouvez récupérer un élément au milieu de la pile A, en utilisant une autre pile: B.

Vous continuez à retirer l'élément supérieur de A et à le placer dans B jusqu'à ce que vous soyez à l'élément souhaité de A, puis vous remettez les éléments de B au-dessus de la pile A.

Ainsi, pour les données qui nécessitent la possibilité de récupérer un index arbitraire, la pile est plus difficile à utiliser.

Dans le cas où vous souhaitez un comportement «dernier entré, premier sorti», une pile vous donnera moins de surcharge qu'un tableau.

Je n'irais pas jusqu'à dire qu'ils sont "très similaires".

Un tableau est utilisé pour contenir des éléments qui seront ultérieurement accessibles séquentiellement ou via l'index. La structure des données n'implique aucune sorte de méthode d'accès (FIFO, LIFO, FILO, etc ...) mais elle peut être utilisée de cette façon si vous le souhaitez.

Une pile est un moyen de suivre les choses lorsqu'elles sont générées. Une méthode d'accès est implicite / requise selon le type de pile créé. Une pile de trames serait un exemple LIFO. Clause de non-responsabilité - Je mélange peut-être ma taxonomie de structure de données ici et une pile peut vraiment n'autoriser que LIFO. Sinon, ce serait un type de file d'attente différent.

Donc je pourrais utiliser un tableau comme pile (bien que je ne le veuille pas) mais je ne peux pas utiliser une pile comme tableau (à moins que je ne travaille vraiment dur dessus).

Les données d'un tableau sont accessibles par une clé ou un index. Les données d'une pile sont accessibles lorsqu'elles sont extraites du haut de la pile. Cela signifie que l'accès aux données à partir d'un tableau est facile si vous connaissez son index. L'accès aux données à partir d'une pile signifie que vous devez continuer à afficher des éléments jusqu'à ce que vous trouviez celui que vous cherchiez, ce qui signifie que l'accès aux données peut prendre plus de temps.

Un tableau est du point de vue des programmeurs, fixe en place et en taille, vous savez où vous en êtes et où tout est. Vous avez accès à tout cela.

Avec une pile, vous vous asseyez à une extrémité, mais vous n'avez aucune idée de sa taille ou de la distance que vous pouvez parcourir en toute sécurité. Votre accès à celui-ci est limité au montant que vous avez alloué, vous ne savez souvent même pas si lors de l'allocation du montant que vous vouliez si vous venez de claquer dans le tas ou l'espace de programme. Votre vue d'une pile est un petit tableau que vous vous êtes alloué, la taille que vous vouliez, que vous avez le contrôle et que vous pouvez voir. Votre portion n'est pas différente d'un tableau. La différence réside dans le fait que votre tableau est collé à une extrémité d'un autre tableau pour des raisons d'argument et de terminologie, dont vous n'avez aucune visibilité, aucune idée de la taille ou de la taille, et vous ne pouvez pas le toucher sans causer de dommages. Un tableau, sauf global, est souvent implémenté sur la pile de toute façon, de sorte que le tableau et la pile partagent le même espace pendant la durée de cette fonction.

Si vous voulez entrer dans le côté matériel, alors il est spécifique au processeur bien sûr, mais généralement le tableau est basé sur un point de départ / adresse connu, la taille est connue par le compilateur / programmeur et les adresses y sont calculées, utilisant parfois l'adressage de décalage de registre (charge une valeur à partir de l'adresse définie par cette valeur de registre de base plus cette valeur de registre de décalage, de même lors de la compilation, il pourrait s'agir d'un décalage immédiat pas nécessairement basé sur un registre, dépend du processeur bien sûr) qui, en assemblage, est très ressemble à l'accès à un tableau en code de haut niveau. De même avec la pile, si disponible, vous pouvez utiliser un registre ou un adressage d'offset immédiat, souvent même s'il utilise un registre spécial, soit le pointeur de pile lui-même, soit un registre réservé par le compilateur / programmeur à utiliser pour accéder au cadre de pile pour cela. une fonction. Et pour certains processeurs, des fonctions spéciales d'accès à la pile sont utilisées et / ou requises pour accéder à la pile. Vous avez des instructions push et pop, mais elles ne sont pas utilisées aussi souvent que vous le pensez et ne s'appliquent pas vraiment à cette question. Pour certains processeurs, push et pop sont des alias pour des instructions qui peuvent être utilisées avec n'importe quel registre, n'importe où, pas seulement le pointeur de pile sur la pile, ce qui supprime davantage le push et pop d'être lié à cette question.