{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Piles et files" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Dans ce notebook, vous allez implémenter les structures de données suivantes :\n", "- les piles;\n", "- les files.\n", "\n", "Pour ce faire, nous allons utiliser une autre structure de donnée : **les listes chaînées doubles**\n", "\n", "## Listes doublement chaînées.\n", "\n", "![Listes chaînées doubles](https://upload.wikimedia.org/wikipedia/commons/2/26/Liste_doublement_cha%C3%AEn%C3%A9e.png)\n", "\n", "Cette structure de donnée est une extension des listes chaînées déjà rencontrées. \n", "La différence avec une liste simplement chaînée est que, cette fois-ci, un pointeur vers l'élément précédent (ou prédécesseur) est ajouté. Ainsi l'accès peut se faire indifféremment dans les deux sens : de successeur en successeur, ou de prédécesseur en prédécesseur.\n", "\n", "Cette structure est plus coûteuse en mémoire (un pointeur supplémentaire par élément) et en nombre d'instructions pour la mise à jour : une insertion coûte quatre copies de pointeurs, contre deux dans le cas d'une liste simplement chaînée.\n", "\n", "En revanche, cela permet d'opérer une insertion avant ou après un élément, sans nécessairement disposer d'un pointeur sur un voisin, alors qu'une liste simplement chaînée n'autorise une insertion qu'à une seule position par rapport à un élément : en successeur ou (exclusivement) en prédécesseur.\n", "\n", " \n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " \n", "## Exercice 1\n", "1. Imaginons que l'on souhaite insérer un élément en fin de liste. Quel est la compléxité de calcul de cette opération ?\n", "\n", "**Votre réponse** \n", " \n", "2. Et maintenant, imaginons que l'on souhaite insérer un élément en début de liste. Quel est la compléxité de calcul de cette opération ?\n", " \n", "**Votre réponse** \n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Vous allez utiliser un module qui implémente ces listes qui se nomme `deque` (double ended queu) \n", "Voici un lien vers sa documentation : [Module dequeu](https://docs.python.org/fr/3/library/collections.html?highlight=deque#collections.deque)\n", "\n", "Dans un premier temps, familiarisons-nous avec ce module." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " \n", "## Exercice 2\n", "1. En vous servant de la documentation, créez une liste (doublement chaînée) nommée `liste1` qui sera vide pour l'instant. \n", " \n", "*Remarque* : Cette documentation peut être vue comme l'interface de ce module, vous ne connaissez pas l'implémentation de cette S.D.D (structure de donnée), ni comment sont codées ses fonction (P.O.O, impératif, fonctionnel...) mais vous avez toutes les informations necessaires pour utiliser le module.\n", " \n", "2. Insérez la chaîne de caractère 'Boujour' par la droite dans la liste `liste1`. Continuez de même avec les `str` suivants : 'tout', 'le', 'monde'.\n", " \n", "3. Affichez la chaîne.\n", " \n", "
" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "from collections import deque\n", "\n", "# Votre code ici." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " \n", "## Exercice 3\n", "1. Créez une seconde liste (doublement chaînée) nommée `liste2` qui contiendra l'entier 5. Affichez la liste.\n", " \n", "2. Insérez l'entier 4 par la gauche. Puis insérez les entiers jusqu'à 0 inclus par la gauche.\n", " \n", "3. Affichez la chaîne.\n", " \n", "
" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "# Votre code ici." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " \n", "## Exercice 4\n", "1. Exécutez la cellule ci-après\n", "2. Que fait la méthode `pop` ? La méthode retourne-t-elle une valeur ? \n", " **Votre réponse .** \n", "3. Que fait la méthode `popleft` ? La méthode retourne-t-elle une valeur ? \n", " **Votre réponse .** \n", "4. Que fait la méthode `reverse` ? La méthode retourne-t-elle une valeur ? \n", " **Votre réponse .** \n", "5. A votre avis, comment accéder à l'élément d'indice 3 de cette liste ? \n", " **Votre réponse ici.** \n", "
" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])\n", "liste3 après pop : deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])\n", "liste3 après pop : deque([0, 1, 2, 3, 4, 5, 6, 7, 8])\n", "liste3 après popleft : deque([1, 2, 3, 4, 5, 6, 7, 8])\n", "liste3 après popleft : deque([2, 3, 4, 5, 6, 7, 8])\n", "liste3 après reverse : deque([8, 7, 6, 5, 4, 3, 2])\n" ] } ], "source": [ "liste3 = deque([x for x in range(11)])\n", "print(liste3)\n", "\n", "liste3.pop()\n", "print(\"liste3 après pop :\",liste3)\n", "liste3.pop()\n", "print(\"liste3 après pop :\",liste3)\n", "\n", "liste3.popleft()\n", "print(\"liste3 après popleft :\",liste3)\n", "liste3.popleft()\n", "print(\"liste3 après popleft :\",liste3)\n", "\n", "liste3.reverse()\n", "print(\"liste3 après reverse :\",liste3)\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Implémentation des piles.\n", "\n", "En informatique, une pile (en anglais stack) est une structure de données fondée sur le principe « dernier arrivé, premier sorti » (en anglais LIFO pour last in, first out), ce qui veut dire, qu'en général, le dernier élément, ajouté à la pile, sera le premier à en sortir.\n", "\n", "Pour visualiser, pensez à la pile d'assiettes. La dernière empilée sera la première a être reprise (on dira dépilée).\n", "\n", "Par exemple, imaginons une pile de nombres entiers de type `int`. Si j'ajoute un élément (on parle d'empilage), il sera placé au-dessus, comme dans Tetris (fig. suivante). Le plus intéressant est sans conteste l'opération qui consiste à extraire les nombres de la pile. On parle de dépilage. On récupère les données une à une, en commençant par la dernière qui vient d'être posée tout en haut de la pile (fig. suivante). On enlève les données au fur et à mesure, jusqu'à la dernière tout en bas de la pile.\n", "\n", "
\"Empilage\"\n", "\"Dépilage\"
\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "À quoi est-ce que tout cela peut bien servir, concrètement ?\n", "\n", "Il y a des programmes où vous avez besoin de stocker des données temporairement pour les ressortir dans un ordre précis : le dernier élément que vous avez stocké doit être le premier à ressortir.\n", "\n", "Pour vous donner un exemple concret, votre système d'exploitation utilise ce type d'algorithme pour retenir l'ordre dans lequel les fonctions ont été appelées. Imaginez un exemple :\n", "\n", "- votre programme commence par la fonction main(comme toujours) ;\n", "- vous y appelez la fonction jouer;\n", "- cette fonction jouer fait appel à son tour à la fonction charger;\n", "- une fois que la fonction charger est terminée, on retourne à la fonction jouer;\n", "- une fois que la fonction jouer est terminée, on retourne au main;\n", "- enfin, une fois le main terminé, il n'y a plus de fonction à appeler, le programme s'achève.\n", "\n", "Pour « retenir » l'ordre dans lequel les fonctions ont été appelées, votre ordinateur crée une pile de ces fonctions au fur et à mesure (fig. suivante).\n", "\n", "\"Empilage\"\n", "\n", "Un autre exemple d'utilisation est une pile contenant les adresses visitées dans un onglet de navigateur internet. Chaque nouvelle adresse est empilée, un appui sur retour arrière dépile la dernière adresse de la pile." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Interface de pile #1\n", "\n", "Voici une première interface 'minimale' de la structure de pile \n", "On considèrera des piles qui contienent des éléments de type homogène (noté T par la suite)\n", "\n", "| Fonction | Description |\n", "|-------------------------------------|--------------------------------------------------|\n", "| `creer_pile() -> Pile ` | Créer une pile vide |\n", "| `est_vide(p : Pile[T]) -> bool ` | renvoie True si p est vide et False sinon |\n", "| `empiler(p : Pile[T], e : T) -> None` | Ajoute l'élément e au sommet de la pile p |\n", "| `depiler(p : Pile[T]) -> T` | Retire et renvoie l'élément au sommet de la pile et soulève une exception IndexError si la pile est vide|\n", "| `__str__(p : Pile) -> str ` | Affiche le contenu de la pile |\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " \n", "## Exercice 5\n", "Implémentez cette interface en utilsant la P.O.O et les listes doublement chaînées. \n", "Pour ce faire, complétez la classe `Pile` avec des méthodes employant le module `deque`.\n", "
" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "class Pile:\n", " def __init__(self):\n", " # Votre code ici.\n", " \n", " def est_vide(self):\n", " # Votre code ici.\n", " \n", " def ajouter(self,e):\n", " # Votre code ici.\n", " \n", " def enlever(self):\n", " # Votre code ici.\n", " \n", " def __str__(self):\n", " # Votre code ici.\n", " \n", " def __getitem__(self,i):\n", " # Votre code ici.\n", "\n", " \n", " \n", "def creer_pile():\n", " return Pile()\n", "\n", "def est_vide(pile):\n", " return pile.est_vide()\n", "\n", "def empiler(pile,e):\n", " pile.ajouter(e)\n", " \n", "def depiler(pile):\n", " valeur = pile.enlever()\n", " return valeur" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "# Faites vos tests et essais perso. ici:\n" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "['A']\n", "['A', 'B']\n", "['A', 'B', 'C']\n", "['A', 'B', 'C', 'D']\n", "['A', 'B', 'C']\n", "['A', 'B']\n" ] } ], "source": [ "# Tests de la classe Pile\n", "pile1 = creer_pile()\n", "assert isinstance(pile1,Pile)\n", "\n", "# est_vide\n", "assert est_vide(pile1) == True\n", "empiler(pile1,'A')\n", "assert est_vide(pile1) == False\n", "\n", "# empiler\n", "print(pile1)\n", "empiler(pile1,'B')\n", "print(pile1)\n", "empiler(pile1,'C')\n", "print(pile1)\n", "empiler(pile1,'D')\n", "print(pile1)\n", "\n", "assert str(pile1) == \"['A', 'B', 'C', 'D']\"\n", "\n", "# depiler\n", "retour_depile = depiler(pile1)\n", "assert retour_depile == 'D'\n", "assert str(pile1) == \"['A', 'B', 'C']\"\n", "print(pile1)\n", "retour_depile = depiler(pile1)\n", "assert retour_depile == 'C'\n", "assert str(pile1) == \"['A', 'B']\"\n", "print(pile1)\n", "depiler(pile1)\n", "depiler(pile1)\n", "# Pile vide\n", "assert est_vide(pile1) == True\n", "# Le code ci-après doit engendrer une exception 'IndexError'\n", "# depiler(pile1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Bonus\n", "Vous pouvez ajouter des méthodes spéciales :\n", "\n", "| Fonction | Description |\n", "|-------------------------------------|--------------------------------------------------|\n", "| `taille(p : Pile[T]) -> Int ` | Renvoie la taille de la pile, il est possible d'implémenter `__len__(self)` à votre classe Pile |\n", "| `vider(p : Pile[T]) -> None ` | Enlève tous les éléments de la pile |" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Les files.\n", "\n", "En informatique, une file dite aussi file d'attente est une structure de données basée sur le principe du premier entré, premier sorti ou PEPS, désigné en anglais par l'acronyme FIFO (« first in, first out ») : les premiers éléments ajoutés à la file seront les premiers à en être retirés.\n", "\n", "Vous pouvez penser aux files d'attente aux caisses des magasins. Voici, ci-dessous, une illustration qui compare piles et files.\n", "\n", "\"Files\n", "\n", "\n", "\n", "En programmation, les files sont utiles pour mettre en attente des informations dans l'ordre dans lequel elles sont arrivées. Par exemple, dans un logiciel de chat (type messagerie instantanée), si vous recevez trois messages à peu de temps d'intervalle, vous les enfilez les uns à la suite des autres en mémoire. Vous vous occupez alors du premier message arrivé pour l'afficher à l'écran, puis vous passez au second, et ainsi de suite." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Interface de file #1\n", "\n", "Voici une première interface 'minimale' de la structure de file \n", "On considèrera des files qui contienent des éléments de type homogène (noté T par la suite)\n", "\n", "| Fonction | Description |\n", "|-------------------------------------|--------------------------------------------------|\n", "| `creer_file() -> File ` | Créer une file vide |\n", "| `est_vide_file(f : File[T]) -> bool ` | renvoie True si f est vide et False sinon |\n", "| `ajouter(f : File[T], e : T) -> None` | Ajoute l'élément e à l'arrière de la file |\n", "| `retirer(f : File[T]) -> T` | Retire et renvoie l'élément à l'avant de la file et soulève une exception IndexError si la file est vide|\n", "| `__str__(f : File) -> str ` | Affiche le contenu de la file |\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " \n", "## Exercice 6\n", "Implémentez cette interface en utilsant la P.O.O et les listes doublement chaînées. \n", "Pour ce faire, complétez la classe `File` avec des méthodes employant le module `deque`.\n", "
" ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [], "source": [ "class File:\n", " def __init__(self):\n", " # Votre code ici.\n", " \n", " def est_vide(self):\n", " # Votre code ici.\n", " \n", " def ajouter(self,e):\n", " # Votre code ici.\n", " \n", " def retirer(self):\n", " # Votre code ici.\n", " \n", " def __str__(self):\n", " # Votre code ici.\n", " \n", " def __getitem__(self,i):\n", " # Votre code ici.\n", " \n", " \n", "# Votre code ici." ] }, { "cell_type": "code", "execution_count": 55, "metadata": {}, "outputs": [], "source": [ "# Faites vos tests et essais perso. ici:\n" ] }, { "cell_type": "code", "execution_count": 60, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "['A']\n", "['B', 'A']\n", "['C', 'B', 'A']\n", "['D', 'C', 'B', 'A']\n", "['D', 'C', 'B']\n", "['D', 'C']\n" ] } ], "source": [ "# Tests de la classe Pile\n", "file1 = creer_file()\n", "assert isinstance(file1,File)\n", "\n", "# est_vide\n", "assert est_vide(file1) == True\n", "ajouter(file1,'A')\n", "assert est_vide(file1) == False\n", "\n", "# ajouter\n", "print(file1)\n", "ajouter(file1,'B')\n", "print(file1)\n", "ajouter(file1,'C')\n", "print(file1)\n", "ajouter(file1,'D')\n", "print(file1)\n", "\n", "assert str(file1) == \"['D', 'C', 'B', 'A']\"\n", "\n", "# retirer\n", "retour_retirer = retirer(file1)\n", "assert retour_retirer == 'A'\n", "assert str(file1) == \"['D', 'C', 'B']\"\n", "print(file1)\n", "retour_retirer = retirer(file1)\n", "assert retour_retirer == 'B'\n", "assert str(file1) == \"['D', 'C']\"\n", "print(file1)\n", "retirer(file1)\n", "retirer(file1)\n", "# File vide\n", "assert est_vide(file1) == True\n", "# Le code ci-après doit engendrer une exception 'IndexError'\n", "# retirer(file1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Bonus\n", "Vous pouvez ajouter des méthodes spéciales :\n", "\n", "| Fonction | Description |\n", "|-------------------------------------|--------------------------------------------------|\n", "| `taille(f : File[T]) -> Int ` | Renvoie la taille de la file, il est possible d'implémenter `__len__(self)` à votre classe File |\n", "| `vider(f : File[T]) -> None ` | Enlève tous les éléments de la file |" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.3" } }, "nbformat": 4, "nbformat_minor": 4 }