Structure de pile

04-03-2023

Objectifs

• connaître la structure de données pile

• savoir en donner une implantation

• savoir l’utiliser

Motivation

Structure de données importante en informatique :

• pile des appels de fonctions

• utile pour parcours de graphes (trouver un chemin)

• exemple de l’évaluation d’expressions postfixées

Opérations primitives sur les piles

Les piles sont des structures de données linéaires admettant les opérations primitives suivantes :

• création d’une pile ;

• empilement d’un élément sur une pile ;

• dépilement d’une pile ;

• consultation du sommet d’une pile ;

• test de vacuité d’une pile.

Note

Les piles peuvent contenir en principe autant d’éléments qu’on veut (cependant en réalité elles sont en général limitées par la mémoire disponible). Mais il n’est pas possible d’accéder directement à n’importe lequel de ces éléments : seul l’élément qui y a été placé en dernier est accessible, les autres ne l’étant pas tant que ce dernier élément n’a pas été sorti de la pile. C’est le principe du dernier entré, premier sorti ou Last In First Out (LIFO en abrégé).

Constructeurs

La construction d’une nouvelle pile ne nécessite aucun paramètre :

ApStack.__init__()

Build

a new empty stack

UC

none

::

>>> st = ApStack()
>>> st
<apstack.ApStack at 0x7f543814f3d0>

Sélecteurs

Seul sélecteur sur les piles la méthode de consultation du sommet d’une pile :

ApStack.top()

Renvoie

element on top of self without removing it

UC

self must be non empty

Modificateurs

La structure de pile est une structure de données mutable. Cela signifie que sa valeur ou son état peut changer au cours du temps.

Deux opérations primitives permettent cette mutabilité :

• l’empilement ;

• et le dépilement.

La méthode d’empilement :

ApStack.push(x)

Paramètres

x (any) – a value

Renvoie

None

Type renvoyé

Nonetype

Side effect

stack self contains a new value : x

UC

none

::

>>> st.push(42)
>>> st.push(3)
>>> st.push(14)

et celle de dépilement :

ApStack.pop()

Renvoie

element on top of self

Side effect

self contains an element less

UC

self must be non empty

::

>>> st.top()
14
>>> st.pop()
14
>>> st.pop()
3

Prédicat

Un prédicat permettant de tester la vacuité d’une pile :

ApStack.is_empty()

Renvoie

• True if s is empty

• False otherwise

Type renvoyé

bool

UC

none

::

>>> st.isempty()
False
>>> st.pop()
42
>>> st.is_empty()
True

Une nouvelle exception

Le sélecteur top et le modificateur pop sont soumis à une contrainte de non vacuité de la pile à laquelle ils s’appliquent. Le non respect de cette contrainte déclenche une exception définie par le

class apstack.ApStackEmptyError(msg)

Exception for empty stacks

::

>>> st.pop()
ApStackEmptyError: empty stack, nothing to pop

Remarque

Note

À l’aide de ces fonctions primitives, le principe du dernier entré premier sorti peut être formalisé par le fait qu’à l’issue des deux instructions

::

>>> st = ApStack()
>>> st.push(x)
>>> y = st.pop()
>>> x == y
    True

la variable y a la même valeur que la variable x et que l’état de la pile st est exactement le même qu’avant la première des deux instructions. Et de même, en supposant que st n’est pas vide, après les deux instructions

>>> y = st.pop()
>>> st.push(y)

la pile st est inchangée.