TP-ImplementPileFile.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implémentation de la pile en Python\n",
    "On peut voir dans la documentation officielle de python qu'il est facile d'implémenter une structure de pile avec les listes : \n",
    "\n",
    "https://docs.python.org/fr/3/tutorial/datastructures.html#using-lists-as-stacks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implémentation directe\n",
    "Exécutez le code suivant et modifiez le pour bien comprendre les mécanismes de pile :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pile de départ :  [1, 2, 3]\n",
      "après ajout de 4 :  [1, 2, 3, 4]\n",
      "après suppression de deux éléments :  [1, 2]\n",
      "[]\n"
     ]
    }
   ],
   "source": [
    "pile=[1,2,3]\n",
    "print(\"pile de départ : \",pile)\n",
    "pile.append(4)\n",
    "print(\"après ajout de 4 : \",pile)\n",
    "pile.pop()\n",
    "pile.pop()\n",
    "print(\"après suppression de deux éléments : \",pile)\n",
    "pile.pop()\n",
    "pile.pop()\n",
    "print(pile)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut au passage noter que Python permet d'évaluer si une liste est vide  :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3] Cette liste n'est pas vide\n",
      "[] Cette liste est vide\n"
     ]
    }
   ],
   "source": [
    "maliste=[1,2,3]\n",
    "if maliste:   #derrière le if, maliste est évalué comme un booleen qui est vrai si la liste contient des éléments\n",
    "    print(maliste, \"Cette liste n'est pas vide\")\n",
    "maliste=[]\n",
    "if not maliste:\n",
    "    print(maliste, \"Cette liste est vide\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Observez ce qui se passe quand on retire un élément d'une liste vide.\n",
    "Regardez s'il est possible d'empiler des données de différents types sur la pile (chaines, dictionnaires, tuples...)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implémentation de files en Python\n",
    "En lisant le cours sur la structure de donnée liste (voir https://pixees.fr/informatiquelycee/n_site/nsi_term_structDo_liste.html), vous avez compris que la structure de donnée file (queue en anglais) est de type \"premier arrivé premier sorti\" (first in first out FIFO en anglais). Il ne faut pas la confondre avec les listes python (list en anglais)\n",
    "\n",
    "On rappelle aussi que les fonctions suivantes y sont implémentées :\n",
    "* on peut savoir si une file est vide (file_vide?)\n",
    "* on peut enfiler un nouvel élément à la file (enfile)\n",
    "* on peut récupérer l'élément situé en bout de file tout en le supprimant (defile)\n",
    "* on peut accéder à l'élément situé en bout de file sans le supprimer de la file (premier)\n",
    "* on peut connaitre le nombre d'éléments présents dans la file (taille)\n",
    "\n",
    "### Exercice 1\n",
    "Complétez le code suivant pour implémenter une file en Python avec ses différentes caractéristiques.\n",
    "\n",
    "Observez bien les commentaires qui vous guideront dans ce qu'on attend de vous"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "[1, 2, 3, 4]\n",
      "1 [1, 2, 3, 4]\n",
      "1 [1, 2, 3, 4]\n",
      "100\n"
     ]
    }
   ],
   "source": [
    "################################\n",
    "# Fonctions à implémenter\n",
    "################################\n",
    "def file_vide(file):\n",
    "#renvoie un booleen indiquant si la file est vide\n",
    "    return True #à modifier bien sûr\n",
    "\n",
    "def enfile(file, element):\n",
    "#renvoie une file à laquelle on a ajouté element à la fin\n",
    "    return file #à modifier bien sûr\n",
    "\n",
    "def defile(file):\n",
    "#renvoie un tuple (elementSorti,fileTronquee) \n",
    "# elementsorti est l'élément qui est sorti de la file\n",
    "# fileTronquee est la nouvelle file sans cet element\n",
    "    return (1,file) #à modifier bien sûr\n",
    "\n",
    "def premier(file):\n",
    "#renvoie element qui est le premier élément de la file\n",
    "    return 1 #à modifier bien sûr\n",
    "\n",
    "def taille(file):\n",
    "#renvoie taille qui est la longueur de la file\n",
    "    return 100 #à modifier bien sûr\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "################################\n",
    "# Partie principale de test\n",
    "# aucun changement à apporter\n",
    "################################\n",
    "mafile=[1,2,3,4]\n",
    "print(file_vide(mafile))  #renvoie faux car la file n'est pas vide\n",
    "mafile=enfile(mafile, 5)  \n",
    "print(mafile) #renvoie [1,2,3,4,5]\n",
    "first,mafile = defile(mafile)\n",
    "print(first,mafile)  #renvoie 1 [2,3,4,5]\n",
    "first = premier((mafile))\n",
    "print(first,mafile) #renvoie 2 [2,3,4,5]\n",
    "print(taille(mafile)) #renvoie 4\n",
    "###################################\n",
    "# vous pouvez ajouter vos propres tests ici\n",
    "####################################"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 2\n",
    "Il est possible d'implémenter les files d'une autre façon que précedement en utilisant deux piles.\n",
    "Regardez la vidéo suivante pour comprendre le principe algorithmique et le mettre en oeuvre en Python:\n",
    "https://web.microsoftstream.com/video/9aa2bacf-9fa0-46a8-aee8-58f861b476d4\n",
    "\n",
    "Complétez le code pour mettre en place une file à l'aide de deux piles\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "[[], []]\n",
      "1\n",
      "1\n",
      "1\n",
      "1\n",
      "1\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "################################\n",
    "# Fonctions à implémenter\n",
    "################################\n",
    "def file_vide(file):\n",
    "#renvoie un booleen indiquant si la file est vide\n",
    "    #A FAIRE\n",
    "    return True #à modifier bien sûr\n",
    "\n",
    "def enfile(file, element): # déjà implémenté\n",
    "#renvoie une file à laquelle on a ajouté element à la fin\n",
    "    pilegauche,piledroite=file[0],file[1]  #on accède aux deux piles\n",
    "    #A FAIRE\n",
    "    return [pilegauche,piledroite] #on renvoie la file constituée des deux piles\n",
    "\n",
    "def defile(file):\n",
    "#renvoie un tuple (elementSorti,fileTronquee) \n",
    "# elementsorti est l'élément qui est sorti de la file\n",
    "# fileTronquee est la nouvelle file sans cet element\n",
    "# principe de l'algorithme vu en video :\n",
    "# si la pile de droite n'est pas vide, alors on a juste à dépiler la pile de droite d'un élément\n",
    "# sinon, on dépile un à un tous les éléments de la pile de gauche vers la droite puis on dépile la pile de droite\n",
    "    pilegauche,piledroite=file[0],file[1]  #on accède aux deux piles\n",
    "    #A FAIRE\n",
    "    return (1,[pilegauche,piledroite]) #on renvoie elementsorti et la file constituée des deux piles...à modifier bien sûr\n",
    "\n",
    "\n",
    "################################\n",
    "# Partie principale de test\n",
    "# aucun changement à apporter\n",
    "################################\n",
    "\n",
    "#on crée la file avec les deux piles\n",
    "pilegauche=[]\n",
    "piledroite=[]\n",
    "mafile=[pilegauche,piledroite] #une file est constituée de deux piles\n",
    "print(file_vide(mafile))  #renvoie vrai car la file est vide (aucun élément ni dans la pile gauche ni dans la pile droite)\n",
    "\n",
    "#on enfile 1,2,3,4,5\n",
    "mafile=enfile(mafile, 1)\n",
    "mafile=enfile(mafile, 2)\n",
    "mafile=enfile(mafile, 3)\n",
    "mafile=enfile(mafile, 4)\n",
    "mafile=enfile(mafile, 5)\n",
    "print(mafile) #renvoie [[1,2,3,4,5],[]\n",
    "\n",
    "#on defile au fur et à mesure et on observe le résultat\n",
    "first,mafile = defile(mafile)\n",
    "print(first)  #renvoie 1\n",
    "first,mafile = defile(mafile)\n",
    "print(first)  #renvoie 2\n",
    "mafile=enfile(mafile, 6)\n",
    "mafile=enfile(mafile, 7)\n",
    "first,mafile = defile(mafile)\n",
    "print(first)  #renvoie 3\n",
    "first,mafile = defile(mafile)\n",
    "print(first)  #renvoie 4\n",
    "first,mafile = defile(mafile)\n",
    "print(first)  #renvoie 5\n",
    "first,mafile = defile(mafile)\n",
    "print(first)  #renvoie 6\n",
    "###################################\n",
    "# vous pouvez ajouter vos propres tests ici\n",
    "####################################"
   ]
  },
  {
   "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.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}