Pile (type de données abstrait) - Stack (abstract data type)

Semblable à une pile d'assiettes, l'ajout ou le retrait n'est possible qu'en haut.
Représentation simple d'un runtime de pile avec des opérations push et pop .

En informatique , une pile est un type de données abstrait qui sert de collection d'éléments, avec deux opérations principales :

  • Push , qui ajoute un élément à la collection, et
  • Pop , qui supprime l'élément le plus récemment ajouté qui n'a pas encore été supprimé.

L'ordre dans lequel les éléments sortent d'une pile donne lieu à son nom alternatif, LIFO ( dernier entré , premier sorti ). De plus, une opération de lecture peut donner accès au sommet sans modifier la pile. Le nom "pile" pour ce type de structure vient de l'analogie avec un ensemble d'éléments physiques empilés les uns sur les autres. Cette structure permet de retirer facilement un élément du haut de la pile, tandis que pour accéder à un élément plus profond dans la pile, il peut être nécessaire de retirer d'abord plusieurs autres éléments.

Considérée comme une structure de données linéaire , ou plus abstraitement une collection séquentielle, les opérations push et pop se produisent uniquement à une extrémité de la structure, appelée le sommet de la pile. Cette structure de données permet d'implémenter une pile sous la forme d'une liste chaînée simple et d'un pointeur vers l'élément supérieur. Une pile peut être implémentée pour avoir une capacité limitée. Si la pile est pleine et ne contient pas assez d'espace pour accepter une entité à pousser, la pile est alors considérée comme étant en état de débordement . L'opération pop supprime un élément du haut de la pile.

Une pile est nécessaire pour implémenter la recherche en profondeur d'abord .

Histoire

Stacks est entré dans la littérature informatique en 1946, lorsqu'Alan M. Turing a utilisé les termes « enterrer » et « désenterrer » comme moyen d'appeler et de revenir des sous-programmes. Des sous-programmes avaient déjà été implémentés dans le Z4 de Konrad Zuse en 1945.

Klaus Samelson et Friedrich L. Bauer de l'Université technique de Munich ont proposé l'idée d'une pile en 1955 et ont déposé un brevet en 1957. En mars 1988, date du décès de Samelson, Bauer a reçu le IEEE Computer Pioneer Award pour l'invention de la pile. principe. Des concepts similaires ont été développés, indépendamment, par Charles Leonard Hamblin dans la première moitié de 1954 et par Wilhelm Kämmerer  [ de ] en 1958.

Les piles sont souvent décrites en utilisant l'analogie d'une pile d'assiettes à ressort dans une cafétéria. Des assiettes propres sont placées sur le dessus de la pile, en repoussant celles qui s'y trouvent déjà. Lorsqu'une plaque est retirée de la pile, celle en dessous apparaît pour devenir la nouvelle plaque supérieure.

Opérations non essentielles

Dans de nombreuses implémentations, une pile a plus d'opérations que les opérations essentielles "push" et "pop". Un exemple d'opération non essentielle est "top of stack", ou "peek", qui observe l'élément supérieur sans le retirer de la pile. Cela pourrait être fait avec un "pop" suivi d'un "push" pour renvoyer les mêmes données à la pile, ce n'est donc pas considéré comme une opération essentielle. Si la pile est vide, une condition de débordement se produira lors de l'exécution des opérations "stack top" ou "pop". De plus, de nombreuses implémentations fournissent une vérification si la pile est vide et une vérification qui renvoie sa taille.

Piles de logiciels

Mise en œuvre

Une pile peut être facilement implémentée via un tableau ou une liste chaînée . Ce qui identifie la structure de données comme une pile, dans les deux cas, ce n'est pas l'implémentation mais l'interface : l'utilisateur n'est autorisé qu'à faire apparaître ou pousser des éléments sur le tableau ou la liste chaînée, avec peu d'autres opérations d'assistance. Ce qui suit démontrera les deux implémentations, en utilisant le pseudocode .

Déployer

Un tableau peut être utilisé pour implémenter une pile (limitée), comme suit. Le premier élément, généralement au décalage de zéro , est le bas, ce qui en array[0]fait le premier élément poussé sur la pile et le dernier élément ressorti. Le programme doit garder une trace de la taille (longueur) de la pile, en utilisant une variable top qui enregistre le nombre d'éléments poussés jusqu'à présent, pointant ainsi vers l'endroit dans le tableau où le prochain élément doit être inséré (en supposant un zéro- convention d'indexation). Ainsi, la pile elle-même peut être efficacement implémentée sous la forme d'une structure à trois éléments :

structure stack:
    maxsize : integer
    top : integer
    items : array of item
procedure initialize(stk : stack, size : integer):
    stk.items ← new array of size items, initially empty
    stk.maxsize ← size
    stk.top ← 0

L' opération push ajoute un élément et incrémente l' index supérieur , après avoir vérifié le débordement :

procedure push(stk : stack, x : item):
    if stk.top = stk.maxsize:
        report overflow error
    else:
        stk.items[stk.top] ← x
        stk.top ← stk.top + 1

De même, pop décrémente l' index supérieur après avoir vérifié le dépassement insuffisant et renvoie l'élément qui était auparavant le premier :

procedure pop(stk : stack):
    if stk.top = 0:
        report underflow error
    else:
        stk.top ← stk.top − 1
        r ← stk.items[stk.top]
        return r

En utilisant un tableau dynamique , il est possible d'implémenter une pile qui peut augmenter ou diminuer autant que nécessaire. La taille de la pile est simplement la taille du tableau dynamique, ce qui est une implémentation très efficace d'une pile puisque l'ajout ou la suppression d'éléments à la fin d'un tableau dynamique nécessite un temps O(1) amorti.

Liste liée

Une autre option pour implémenter des piles est d'utiliser une liste à chaînage unique . Une pile est alors un pointeur vers la "tête" de la liste, avec peut-être un compteur pour suivre la taille de la liste :

structure frame:
    data : item
    next : frame or nil
structure stack:
    head : frame or nil
    size : integer
procedure initialize(stk : stack):
    stk.head ← nil
    stk.size ← 0

Les éléments poussés et éclatés se produisent en tête de liste; le débordement n'est pas possible dans cette implémentation (sauf si la mémoire est épuisée) :

procedure push(stk : stack, x : item):
    newhead ← new frame
    newhead.data ← x
    newhead.next ← stk.head
    stk.head ← newhead
    stk.size ← stk.size + 1
procedure pop(stk : stack):
    if stk.head = nil:
        report underflow error
    r ← stk.head.data
    stk.head ← stk.head.next
    stk.size ← stk.size - 1
    return r

Piles et langages de programmation

Certains langages, tels que Perl , LISP , JavaScript et Python , rendent les opérations de pile push et pop disponibles sur leurs types de liste/tableau standard. Certains langages, notamment ceux de la famille Forth (y compris PostScript ), sont conçus autour de piles définies par le langage qui sont directement visibles et manipulées par le programmeur.

Ce qui suit est un exemple de manipulation d'une pile dans Common Lisp (" > " est l'invite de l'interpréteur Lisp ; les lignes ne commençant pas par " > " sont les réponses de l'interpréteur aux expressions) :

> (setf stack (list 'a 'b 'c))  ;; set the variable "stack"
(A B C)
> (pop stack)  ;; get top (leftmost) element, should modify the stack
A
> stack        ;; check the value of stack
(B C)
> (push 'new stack)  ;; push a new top onto the stack
(NEW B C)

Plusieurs types de conteneurs de la bibliothèque standard C++ ont des opérations push_back et pop_back avec la sémantique LIFO ; De plus, la classe de modèle de pile adapte les conteneurs existants pour fournir une API restreinte avec uniquement des opérations push/pop. PHP a une classe SplStack . La bibliothèque de Java contient une Stackclasse qui est une spécialisation de Vector. Voici un exemple de programme en langage Java , utilisant cette classe.

import java.util.Stack;

class StackDemo {
    public static void main(String[]args) {
        Stack<String> stack = new Stack<String>();
        stack.push("A");    // Insert "A" in the stack
        stack.push("B");    // Insert "B" in the stack
        stack.push("C");    // Insert "C" in the stack
        stack.push("D");    // Insert "D" in the stack
        System.out.println(stack.peek());    // Prints the top of the stack ("D")
        stack.pop();    // removing the top ("D")
        stack.pop();    // removing the next top ("C")
    }
}

Pile matérielle

Une utilisation courante des piles au niveau de l'architecture est comme moyen d'allouer et d'accéder à la mémoire.

Architecture de base d'une pile

Une pile typique, stockant des données locales et des informations d'appel pour les appels de procédures imbriquées (pas nécessairement des procédures imbriquées ). Cette pile croît vers le bas depuis son origine. Le pointeur de pile pointe vers la donnée actuelle la plus élevée de la pile. Une opération push décrémente le pointeur et copie les données dans la pile ; une opération pop copie les données de la pile, puis incrémente le pointeur. Chaque procédure appelée dans le programme stocke les informations de retour de procédure (en jaune) et les données locales (dans d'autres couleurs) en les poussant sur la pile. Ce type d'implémentation de pile est extrêmement courant, mais il est vulnérable aux attaques par débordement de tampon (voir le texte).

Une pile typique est une zone de mémoire informatique avec une origine fixe et une taille variable. Initialement, la taille de la pile est de zéro. Un pointeur de pile, généralement sous la forme d'un registre matériel, pointe vers l'emplacement le plus récemment référencé sur la pile ; lorsque la pile a une taille de zéro, le pointeur de pile pointe vers l'origine de la pile.

Les deux opérations applicables à toutes les piles sont :

  • une opération de poussée , dans laquelle un élément de données est placé à l'emplacement pointé par le pointeur de pile, et l'adresse dans le pointeur de pile est ajustée par la taille de l'élément de données ;
  • une opération pop ou pull : un élément de données à l'emplacement actuel pointé par le pointeur de pile est supprimé et le pointeur de pile est ajusté par la taille de l'élément de données.

Il existe de nombreuses variantes du principe de base des opérations de pile. Chaque pile a un emplacement fixe, en mémoire, auquel elle commence. Au fur et à mesure que des éléments de données sont ajoutés à la pile, le pointeur de pile est déplacé pour indiquer l'étendue actuelle de la pile, qui s'étend à partir de l'origine.

Les pointeurs de pile peuvent pointer vers l'origine d'une pile ou vers une plage limitée d'adresses au-dessus ou au-dessous de l'origine (selon la direction dans laquelle la pile grandit) ; cependant, le pointeur de pile ne peut pas traverser l'origine de la pile. Autrement dit, si l'origine de la pile est à l'adresse 1000 et que la pile croît vers le bas (vers les adresses 999, 998, etc.), le pointeur de pile ne doit jamais être incrémenté au-delà de 1000 (jusqu'à 1001, 1002, etc.). Si une opération pop sur la pile provoque le déplacement du pointeur de pile au-delà de l'origine de la pile, un débordement de pile se produit. Si une opération push provoque l'incrémentation ou la décrémentation du pointeur de pile au-delà de l'étendue maximale de la pile, un débordement de pile se produit.

Certains environnements qui dépendent fortement des piles peuvent fournir des opérations supplémentaires, par exemple :

  • Dupliquer : l'élément du haut est sauté, puis poussé à nouveau (deux fois), de sorte qu'une copie supplémentaire de l'ancien élément du haut est maintenant au-dessus, avec l'original en dessous.
  • Peek : l'élément le plus haut est inspecté (ou renvoyé), mais le pointeur de pile et la taille de la pile ne changent pas (ce qui signifie que l'élément reste sur la pile). Ceci est également appelé opération supérieure dans de nombreux articles.
  • Échanger ou échanger : les deux éléments les plus hauts de la pile échangent leurs places.
  • Rotation (ou Roll) : les n éléments les plus hauts sont déplacés sur la pile de manière rotative. Par exemple, si n =3, les éléments 1, 2 et 3 de la pile sont respectivement déplacés vers les positions 2, 3 et 1 de la pile. De nombreuses variantes de cette opération sont possibles, les plus courantes étant appelées rotation à gauche et rotation à droite.

Les piles sont souvent visualisées en croissance de bas en haut (comme les piles du monde réel). Ils peuvent également être visualisés en croissance de gauche à droite, de sorte que "le plus haut" devienne "le plus à droite", ou même en train de croître de haut en bas. La caractéristique importante est que le bas de la pile est dans une position fixe. L'illustration de cette section est un exemple de visualisation de la croissance de haut en bas : le haut (28) est la pile "en bas", puisque la pile "en haut" (9) est l'endroit où les éléments sont poussés ou sortis.

Une rotation à droite déplacera le premier élément vers la troisième position, le deuxième vers le premier et le troisième vers le second. Voici deux visualisations équivalentes de ce processus :

apple                         banana
banana    ===right rotate==>  cucumber
cucumber                      apple
cucumber                      apple
banana    ===left rotate==>   cucumber
apple                         banana

Une pile est généralement représentée dans les ordinateurs par un bloc de cellules de mémoire, avec le "bas" à un emplacement fixe, et le pointeur de pile contenant l'adresse de la cellule "supérieure" actuelle dans la pile. La terminologie supérieure et inférieure est utilisée indépendamment du fait que la pile croît réellement vers des adresses mémoire inférieures ou vers des adresses mémoire supérieures.

Le fait de pousser un élément sur la pile ajuste le pointeur de pile en fonction de la taille de l'élément (soit en décrémentant, soit en incrémentant, selon la direction dans laquelle la pile se développe en mémoire), en le pointant vers la cellule suivante et copie le nouvel élément du haut vers la zone de la pile. En fonction encore une fois de l'implémentation exacte, à la fin d'une opération push, le pointeur de pile peut pointer vers le prochain emplacement inutilisé dans la pile, ou il peut pointer vers l'élément le plus haut de la pile. Si la pile pointe vers l'élément actuel le plus haut, le pointeur de pile sera mis à jour avant qu'un nouvel élément ne soit poussé sur la pile ; s'il pointe vers le prochain emplacement disponible dans la pile, il sera mis à jour une fois que le nouvel élément est poussé sur la pile.

Faire éclater la pile est tout simplement l'inverse de pousser. L'élément le plus haut de la pile est supprimé et le pointeur de pile est mis à jour, dans l'ordre inverse de celui utilisé dans l'opération push.

Empiler dans la mémoire principale

De nombreuses conceptions de processeurs de type CISC , y compris les x86 , Z80 et 6502 , ont un registre dédié à utiliser comme pointeur de pile d' appels avec des instructions d'appel, de retour, de poussée et de suppression dédiées qui mettent implicitement à jour le registre dédié, augmentant ainsi la densité de code . Certains processeurs CISC, comme le PDP-11 et le 68000 , ont également des modes d'adressage spéciaux pour la mise en œuvre des piles , généralement avec un pointeur de pile semi-dédié (comme A7 dans le 68000). En revanche, la plupart des conceptions de processeurs RISC n'ont pas d'instructions de pile dédiées et donc la plupart sinon tous les registres peuvent être utilisés comme pointeurs de pile selon les besoins.

Empilement dans des registres ou mémoire dédiée

L' architecture à virgule flottante x87 est un exemple d'ensemble de registres organisés en pile où l'accès direct à des registres individuels (par rapport au sommet actuel) est également possible. Comme pour les machines basées sur la pile en général, avoir le sommet de la pile comme argument implicite permet une petite empreinte de code machine avec une bonne utilisation de la bande passante du bus et des caches de code , mais cela empêche également certains types d'optimisations possibles sur les processeurs le permettant accès aléatoire au fichier registre pour tous (deux ou trois) opérandes. Une structure de pile rend également les implémentations superscalaires avec renommage des registres (pour l' exécution spéculative ) un peu plus complexes à implémenter, bien que cela soit toujours faisable, comme l'illustrent les implémentations x87 modernes .

Sun SPARC , AMD Am29000 et Intel i960 sont tous des exemples d'architectures utilisant des fenêtres de registre dans une pile de registres comme autre stratégie pour éviter l'utilisation d'une mémoire principale lente pour les arguments de fonction et les valeurs de retour.

Il existe également un certain nombre de petits microprocesseurs qui implémentent une pile directement dans le matériel et certains microcontrôleurs ont une pile à profondeur fixe qui n'est pas directement accessible. Les exemples sont les microcontrôleurs PIC , les Computer Cowboys MuP21 , la gamme Harris RTX et le Novix NC4016 . De nombreux microprocesseurs basés sur des piles ont été utilisés pour implémenter le langage de programmation Forth au niveau du microcode . Les piles ont également été utilisées comme base pour un certain nombre d' ordinateurs centraux et de mini-ordinateurs . De telles machines étaient appelées machines à empiler , la plus connue étant la Burroughs B5000 .

Applications des piles

Évaluation des expressions et analyse syntaxique

Les calculatrices utilisant la notation polonaise inversée utilisent une structure de pile pour conserver les valeurs. Les expressions peuvent être représentées en notations préfixe, suffixe ou infixe et la conversion d'une forme à une autre peut être effectuée à l'aide d'une pile. De nombreux compilateurs utilisent une pile pour analyser la syntaxe des expressions, des blocs de programme, etc. avant de les traduire en code de bas niveau. La plupart des langages de programmation sont des langages sans contexte , ce qui leur permet d'être analysés avec des machines basées sur des piles.

Retour en arrière

Une autre application importante des piles est le retour en arrière . Prenons un exemple simple pour trouver le bon chemin dans un labyrinthe. Il y a une série de points, du point de départ à la destination. Nous partons d'un point. Pour atteindre la destination finale, il existe plusieurs chemins. Supposons que nous choisissions un chemin aléatoire. Après avoir suivi un certain chemin, nous nous rendons compte que le chemin que nous avons choisi est mauvais. Nous devons donc trouver un moyen par lequel nous pouvons revenir au début de ce chemin. Cela peut être fait avec l'utilisation de piles. À l'aide de piles, nous nous souvenons du point où nous avons atteint. Cela se fait en poussant ce point dans la pile. Au cas où nous nous retrouvions sur le mauvais chemin, nous pouvons extraire le dernier point de la pile et ainsi revenir au dernier point et continuer notre quête pour trouver le bon chemin. C'est ce qu'on appelle le retour en arrière.

L'exemple prototype d'un algorithme de retour en arrière est la recherche en profondeur d'abord , qui trouve tous les sommets d'un graphe qui peuvent être atteints à partir d'un sommet de départ spécifié. D'autres applications du backtracking impliquent la recherche dans des espaces qui représentent des solutions potentielles à un problème d'optimisation. Branch and bound est une technique permettant d'effectuer de telles recherches de retour en arrière sans rechercher de manière exhaustive toutes les solutions potentielles dans un tel espace.

Gestion de la mémoire du temps de compilation

Un certain nombre de langages de programmation sont orientés pile , ce qui signifie qu'ils définissent la plupart des opérations de base (ajouter deux nombres, imprimer un caractère) comme prendre leurs arguments de la pile et remettre les valeurs de retour sur la pile. Par exemple, PostScript a une pile de retour et une pile d'opérandes, ainsi qu'une pile d'états graphiques et une pile de dictionnaires. De nombreuses machines virtuelles sont également orientées pile, notamment la machine p-code et la machine virtuelle Java .

Presque toutes les conventions d'appel ‍—‌la manière dont les sous-routines reçoivent leurs paramètres et renvoient les résultats‍—‌utilisent une pile spéciale (la " pile d'appels ") pour contenir des informations sur l'appel et l'imbrication de procédure/fonction afin de basculer dans le contexte de la fonction appelée et restaurer la fonction d'appelant lorsque l'appel se termine. Les fonctions suivent un protocole d'exécution entre l'appelant et l'appelé pour enregistrer les arguments et renvoyer la valeur sur la pile. Les piles sont un moyen important de prendre en charge les appels de fonction imbriqués ou récursifs . Ce type de pile est utilisé implicitement par le compilateur pour prendre en charge les instructions CALL et RETURN (ou leurs équivalents) et n'est pas manipulé directement par le programmeur.

Certains langages de programmation utilisent la pile pour stocker des données locales à une procédure. L'espace pour les éléments de données locaux est alloué à partir de la pile lorsque la procédure est entrée et est désalloué lorsque la procédure se termine. Le langage de programmation C est généralement implémenté de cette manière. L'utilisation de la même pile pour les appels de données et de procédure a des implications de sécurité importantes (voir ci-dessous) dont un programmeur doit être conscient afin d'éviter d'introduire de graves bogues de sécurité dans un programme.

Algorithmes efficaces

Plusieurs algorithmes utilisent une pile (séparée de la pile d'appels de fonction habituelle de la plupart des langages de programmation) comme principale structure de données avec laquelle ils organisent leurs informations. Ceux-ci inclus:

  • Graham scan , un algorithme pour l' enveloppe convexe d'un système de points à deux dimensions. Une enveloppe convexe d'un sous-ensemble de l'entrée est conservée dans une pile, qui est utilisée pour rechercher et supprimer des concavités dans la frontière lorsqu'un nouveau point est ajouté à l'enveloppe.
  • Une partie de l' algorithme SMAWK pour trouver les minima de ligne d'une matrice monotone utilise des piles d'une manière similaire au balayage de Graham.
  • Toutes les plus petites valeurs les plus proches , le problème de trouver, pour chaque nombre dans un tableau, le nombre précédent le plus proche qui est plus petit que lui. Un algorithme pour ce problème utilise une pile pour maintenir une collection de candidats pour la plus petite valeur la plus proche. Pour chaque position dans le tableau, la pile est éclatée jusqu'à ce qu'une valeur plus petite soit trouvée en son sommet, puis la valeur de la nouvelle position est poussée sur la pile.
  • L' algorithme de chaîne du plus proche voisin , une méthode de clustering hiérarchique agglomérant basée sur le maintien d'une pile de clusters, dont chacun est le voisin le plus proche de son prédécesseur sur la pile. Lorsque cette méthode trouve une paire de clusters qui sont des voisins mutuels les plus proches, ils sont extraits et fusionnés.

Sécurité

Certains environnements informatiques utilisent des piles de manière à les rendre vulnérables aux atteintes à la sécurité et aux attaques. Les programmeurs travaillant dans de tels environnements doivent prendre des précautions particulières pour éviter les pièges de ces implémentations.

Par exemple, certains langages de programmation utilisent une pile commune pour stocker à la fois les données locales d'une procédure appelée et les informations de liaison qui permettent à la procédure de retourner à son appelant. Cela signifie que le programme déplace les données dans et hors de la même pile qui contient les adresses de retour critiques pour les appels de procédure. Si les données sont déplacées vers le mauvais emplacement sur la pile ou si un élément de données surdimensionné est déplacé vers un emplacement de pile qui n'est pas assez grand pour le contenir, les informations de retour pour les appels de procédure peuvent être corrompues, provoquant l'échec du programme.

Des parties malveillantes peuvent tenter une attaque par écrasement de pile qui tire parti de ce type de mise en œuvre en fournissant une entrée de données surdimensionnée à un programme qui ne vérifie pas la longueur de l'entrée. Un tel programme peut copier les données dans leur intégralité vers un emplacement de la pile et, ce faisant, il peut modifier les adresses de retour des procédures qui l'ont appelé. Un attaquant peut expérimenter pour trouver un type spécifique de données qui peuvent être fournies à un tel programme de telle sorte que l'adresse de retour de la procédure en cours soit réinitialisée pour pointer vers une zone au sein de la pile elle-même (et dans les données fournies par l'attaquant), qui à son tour contient des instructions qui effectuent des opérations non autorisées.

Ce type d'attaque est une variante de l' attaque par débordement de tampon et est une source extrêmement fréquente de failles de sécurité dans les logiciels, principalement parce que certains des compilateurs les plus populaires utilisent une pile partagée pour les appels de données et de procédure, et ne vérifient pas la longueur des éléments de données. Souvent, les programmeurs n'écrivent pas non plus de code pour vérifier la taille des éléments de données, et lorsqu'un élément de données surdimensionné ou sous-dimensionné est copié dans la pile, une faille de sécurité peut se produire.

Voir également

Les références

Lectures complémentaires

Liens externes