Structure de pile

Rappels et compléments

Listes

Exemples

Lire attentivement le code, observer les résultats et retenir !

Synthèse

Fonction len()

La fonction len(L) renvoie la longueur (length) de la liste (i.e. le nombre d'éléments qu'elle contient).

Méthodes

L.append(e) ajoute l'élément e à la fin de la liste L (équivalent à L += [e] mais plus rapide).
L.pop() renvoie le dernier élément de la liste et le supprime de la liste, L.pop(i) fait de même avec l'élément d'index i.
L.insert(i,e) insère l'élément e dans la liste L à l'index i.
L.copy() crée une copie de la liste L tandis que M=L crée un alias (un nouveau nom pour la même liste).

Structures de données

Structures de données déjà rencontrées :

Structure	n-uplet	liste	chaîne	ensemble	dictionnaire	tableau	fichier
Type python	tuple	list	string	set	dict	array	file

Sans oublier les bases de données.

Chaque structure de donnée est adapté à un certain type de problème.
Un algorithme est d'autant plus efficace qu'il manipule des données représentées par une structure adaptée.
Les dictionnaires sont des listes dont les éléments sont indexés par des clés et non par des entiers, les tableaux sont utiles pour traiter des vecteurs et des matrices (images par exemple), les bases de données permettent de mettre des données en relation mais il existe d'autres structures de données adaptées à d'autres problèmes particuliers : les piles, les files, les arbres...

Tableaux et temps d'accès

En informatique, un tableau est une structure de données de taille fixe (statique) définie par un temps d’accès à un élément en O(1) c'est-à-dire indépendant du nombre d’éléments du tableau (autrement dit, le temps d’accès est indépendant de la place de l’élément dans le tableau).
En python, les listes (type list) se comportent comme des tableaux du point de vue du temps d’accès qui est donc en O(1).
Noter que les listes sont néanmoins des structures de taille variable (dynamique). Les opérations d’ajout / suppression en fin de liste (cf. pop et append) sont donc rapides tandis que ces mêmes opérations en tête de liste (insert) sont lentes (décalage des éléments de la liste).

Piles et files

Caractéristiques

Pile (Stack)	File (Queue)
Principe

Spécifications
Dernier arrivé, premier sorti = LIFO (Last In First Out).	Dernier arrivé, dernier sorti = LILO (Last In Last Out).
Opérations fondamentales : Tester si la pile (file) est vide Ajouter un élément Retirer un élément Afficher le sommet de la pile (la tête de file) Ces opérations doivent se faire en temps O(1)
Applications
Structure de données utilisée par : - les processeurs ; - les langages (paramètres des fonctions, variables locales, fonctions récursives…) ; - les navigateurs web (page précédente) ; - les logiciels (fonction « Undo ») ; - certains éditeurs de texte pour la vérification des parenthèses (Spyder, Notepad++).	Structure de données utilisée par : - queue à la caisse ! - les mémoires tampons (buffers) ; - les systèmes d'exploitation multitâches qui répartissent le temps-machine entre différentes tâches ; - les serveurs d'impression qui traitent les requêtes dans l'ordre d’arrivée.
Dans les deux cas, ces structures sont destinées au stockage temporaire de données en cours de traitement (le stockage durable utilise des fichiers).

Implémentation des piles en python

Deux possibilités :
- à l'aide de listes - type list - (avantage : piles sans limite de taille, inconvénient : cette structure diffère d'un tableau au sens informatique) ;
- à l'aide de tableaux - type array - (avantage : tableaux donc temps d'accès rigoureusement en O(1), inconvénient : piles de taille finie donc il faut gérer le cas de la pile pleine).

Exemple : une liste de la forme [-4, 5, 2, -7, 0, 1] représentera une pile ayant pour fond -4 et pour sommet 1. Les entrées/sorties se font donc par « la droite » (i.e. en fin de liste).

But du chapitre

Il s'agit :

d'écrire une bibliothèque de fonctions pour les piles simulées par des listes (cf. "Opérations fondamentales" dans le tableau ci-dessus) à l'aide des fonctions/méthodes len, append, pop et copy ;
d'écrire d'autres fonctions applicables à des piles en utilisant exclusivement la bibliothèque précédente à l'exclusion de toute autre fonction (en particulier, les fonctions dédiées aux listes).

Autrement dit, une fois écrite la bibliothèque destinée au traitement des piles, il n'est pas nécessaire de savoir que les piles sont en réalité représentées par des listes.
Cette bibliothèque pourrait être transmise à un programmeur qui ignorerait tout des listes python. Cette « ignorance » n'est pas nouvelle : pour utiliser des tableaux numpy il suffit de lire la documentation pour les manipuler, il n'est pas nécessaire de connaître les structures sous-jacentes.

Exercices

Sauvegardes

Il est impératif de sauvegarder régulièrement le code en le collant dans un fichier texte (Notepad++) ou dans l'éditeur de pyzo.

I - Structure de pile à base de listes

A - Bibliothèque de fonctions (primitives)

On écrit ici 7 fonctions, appelées primitives, qui permettent de réaliser les opérations fondamentales sur les piles :

creer_pile()
taille(p)
pile_vide(p)
empiler(p,e)
depiler(p)
sommet(p)
copier(p)

Ces 7 primitives, et elles seules, seront utilisées dans la suite.

Les piles sont représentées par des listes et on utilise uniquement len, append, pop et copy ou une méthode équivalente.
Bien lire les spécifications de chaque fonction pour savoir si elle retourne ou/et modifie quelque chose.
Si nécessaire, une fonction peut appeler une autre fonction de cette même bibliotèque.

Ecrire une fonction creer_pile() renvoyant une pile vide (i.e. une liste vide). Tester la fonction.
Ecrire une fonction taille(p) ayant pour paramètre une pile p et renvoyant la taille de la pile p. Tester la fonction.
Ecrire une fonction pile_vide(p) ayant pour paramètre une pile p et renvoyant un booléen (True ou False). Tester la fonction.
Ecrire une fonction empiler(p,e) ayant pour paramètre une pile p et un éléemnt e et modifiant la pile p en lui ajoutant l'élément e (ne renvoie rien). Tester la fonction.
Ecrire une fonction depiler(p) ayant pour paramètre une pile p et renvoyant l'élément dépilé (la pile p est modifiée). Tester la fonction.
Ecrire une fonction sommet(p) ayant pour paramètre une pile p et renvoyant le sommet de la pile sans le dépiler (i.e. la pile p n'est pas modifiée). Tester la fonction.
Ecrire une fonction copier(p) ayant pour paramètre une pile p et renvoyant une copie de la pile p. Tester la fonction.

B - Manipulations de piles

Seules les 7 primitives de la bibliothèque ci-dessus sont autorisées à l'exclusion de toute autre fonction. Les boucles, tests et autres instructions python sont autorisées (c'est un jeu intellectuel qui consiste à ignorer que les piles sont représentées par des listes).

Écrire une fonction inverser_pile(p) qui retourne une pile inversée sans modifier p (procéder à cette opération, à la main, avec quelques feuilles de papier : l’algorithme en découle !). Tester la fonction.
Écrire une fonction depilerK(p,k) qui désempile k éléments si la pile p en contient au moins k et désempile toute la pile sinon sans provoquer d’erreur. Tester la fonction.
Écrire une fonction depilerE(p, e) qui désempile la pile p tant que l’élément e (entier) n’est pas rencontré et que p n’est pas vide. Tester la fonction.

C - Vérification des expressions parenthésées

Dans un texte constitué uniquement de parenthèses, de nombres et de symboles des opérations usuelles (+, -, /, *) on souhaite vérifier que chaque parenthèse ouvrante est bien associée à une parenthèse fermante.

Exemples :

L’analyse par le script du « texte » 74*(1-9/(7+1.2)) ne doit générer aucune erreur.
L’analyse de )74*(1-9/(7+1.2)), de 74*(1-9/7+1.2)) ou de 74*(1-9/(7+1.2) doit provoquer un message d’erreur.

Ecrire une fonction parentheses(s) ayant pour paramètre une chaîne s (le texte à analyser) et renvoyant le booléen True si le parenthésage est correct et False sinon.
L'algorithme devra utiliser la structure de pile et les primitives associées (à l'exclusion de toute autre fonction dédiée aux listes). Les boucles, tests et autres instructions python sont autorisées.
Tester cette fonction avec les 4 exemples proposés ci-dessus, en imaginer d'autres. Effectuer les corrections nécessaires (vérifier avec la totalité des tests).
Facultatif : écrire une version améliorée de cette fonction permettant de vérifier la correction d'une experssion comportant des parenthèses, des crochets et des accolades.
Rq : vérifier que la fonction subit avec succès le second test proposé ci-dessous.

D - Notation post-fixée ou polonaise inversée

La notation polonaise inversée ou notation post-fixée permet de représenter sans parenthèses, de façon non ambigüe, les expressions algébriques (habituelles ou infixées). Ces expressions deviennent des suites d’opérandes et d’opérateurs, les opérateurs étant placés après leurs opérandes (cf. exemples ci-dessous).

Exemples :

Notation infixée	Notation post-fixée
a+b	a, b, +
a+b*c	a, b, c, *, +
(a+b)*c	a, b, +, c, *
a*(b+c)	a, b, c, +, *

Principe : l’évaluation de l’expression post-fixée utilise une pile. L’expression est lue de gauche à droite :
- si le terme lu est un opérande (nombre), il est empilé ;
- si le terme est un opérateur, les deux termes du haut de la pile sont dépilés, le calcul est effectué et empilé.

Ecrire une fonction NPI(e) qui donne la valeur d’une expression e en notation post-fixée. Dans un premier temps, on restreindra le problème à des expressions composées d’entiers pour les seules opérations d’addition et de multiplication ( , +, *)
L’expression e sera fournie sous la forme d’un tuple de la forme (1, 2, 3, '+', '*') (noter les guillemets qui transforment les symboles des opérateurs en chaînes).
Facultatif : écrire une version améliorée de cette fonction permettant de gérer davantage d'opérations.

II - Structure de pile à base de tableaux

Facultatif - Implémenter une bibliothèque de primitives analogues aux précédentes en utilisant la structure array de numpy pour des piles de taille finie.
Comme le tableau est de dimension fixe, la taille de la pile doit être stockée dans le tableau et actualisée à chaque empilage/dépilage, on utilise la première case du tableau pour mémoriser cette taille. Il est possible d'utiliser numpy.
Exemple : le tableau [4,0,1,2,3,0,0,0,0,0] représente une pile de taille 4 constituée des 4 éléments 0,1,2,3 et la taille maximum de cette pile est 9 (5 zéros après les 4 éléments).

La fonction creer_pile(dim) renvoie un tableau rempli de zéros de taille égale à dim+1 (car la première case sert à stocker la taille de la pile).
Il est également nécessaire de créer une fonction pile_pleine(p) permettant de tester si une une pile est pleine ou non (avant d'empiler par exemple).
Il peut être souhaitable (en vue des tests) de créer une fonction affiche(p) qui affiche la pile (i.e. les élements d'index 1 à taille(p) c'est à dire pas le premier qui est la taille et pas les zéros qui complètent le tableau au delà de la taille).
Tester les fonctions.

III - Structure de file à base de listes

Facultatif - Implémenter une bibliothèque de primitives analogues aux précédentes pour les files (en utilisant des listes), sans limite de taille : creer_file, taille, file_vide, enfiler, defiler, queue.
Une file est représentée par une liste [queue,..., tête] : le premier élément de la liste représente la queue (il faudra donc ajouter un élément à la file en l'insérant au début de la liste associée) et le dernier élément de la liste représente la tête de file (c'est donc cet élément qu'il faudra enlever pour 'défiler').
Il est nécessaire de remplacer la fonction "sommet" dédiée aux piles par une fonction "queue" adaptée aux files et renvoyant le dernier élément de la file.
Tester les fonctions.