{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Piles et files\n",
    "\n",
    "> Cours NSI Terminale - Thème 1.\n",
    "\n",
    "- toc: true \n",
    "- badges: true\n",
    "- comments: false\n",
    "- categories: [python, NSI, Terminale, Structure_donnees, TP]\n",
    "- image: images/nsi1.png"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "54acf2927df630f57ddbde70689f88d0",
     "grade": false,
     "grade_id": "cell-d0f1d6f1b1a69d1c",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "# Les listes chaînées, les piles et les files"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Les piles\n",
    "\n",
    "On va commencer ce TP par la manipulation des piles, plus faciles à appréhender, et on terminera par la manuipulation des listes chaînées. Rappelons tout d'abord la notion de **piles** répondant à la règle **LIFO** : dernier entré, premier sorti.\n",
    "\n",
    "![pile](my_icons/pile1.png)\n",
    "\n",
    "### Description de la structure\n",
    "\n",
    "Pour stocker les données dans notre pile, nous utiliserons un tableau python (objet list).\n",
    "Le dernier élément du tableau sera le sommet de la pile. Seul cet élément sera visible.\n",
    "\n",
    "**Exemple** : Si la pile est représentée en mémoire par le tableau `[2, 3, 5, 8]`, le sommet de la pile sera `8`. Si je dépile le 8, la pile deviendra `[2, 3, 5]` et le sommet de la pile sera 5. Une fois tous les éléments dépilés, la pile sera vide et représentée par `[]`.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "92b1ac9dc03510b244fbfde3dde32757",
     "grade": false,
     "grade_id": "cell-8c17c994b0bd5ea3",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "### A vous de jouer\n",
    "\n",
    "Vous allez devoir implémenter les fonctions\n",
    "- `p_valeur(pile)`\n",
    "    - prend en paramètre une pile `pile`\n",
    "    - renvoie le sommet de la pile ou `None` si la pile est vide\n",
    "- `p_depile(pile)`\n",
    "    - prend en paramètre une pile `pile`\n",
    "    - dépile le dernier élément saisi\n",
    "    - renvoie la valeur dépilée ou `None` si la pile est vide\n",
    "- `p_empile(pile, v)`\n",
    "    - prend en paramètre une pile `pile` et une valeur `v`\n",
    "    - empile la valeur `v`\n",
    "    - ne renvoie rien"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "b9833f317cc0f53e0337c6667cf3536f",
     "grade": false,
     "grade_id": "cell-f49fdbbc737964c6",
     "locked": false,
     "schema_version": 3,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def p_valeur(pile):\n",
    "    \"\"\"- prend en paramètre une pile pile\n",
    "    - renvoie le sommet de la pile\n",
    "    Exemple : \n",
    "    >>> p_valeur([2, 3, 5])\n",
    "    >>> 5\n",
    "    >>> p_valeur([])\n",
    "    >>> None\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ef37f1abed0487ee12542845cd679786",
     "grade": true,
     "grade_id": "cell-f1f58ee5889bcc38",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "assert p_valeur([]) is None\n",
    "assert p_valeur([2, 3, 5]) == 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "1a764b6f40ff561d2e12b3d2263a4824",
     "grade": false,
     "grade_id": "cell-a050d8f552935363",
     "locked": false,
     "schema_version": 3,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def p_depile(pile):\n",
    "    \"\"\"- prend en paramètre une pile pile\n",
    "    - dépile le dernier élément saisi\n",
    "    - renvoie le sommet de la pile\n",
    "    Exemple : \n",
    "    >>> p_valeur([2, 3, 5])\n",
    "    >>> 5\n",
    "    >>> p_valeur([])\n",
    "    >>> None\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "4a43eaccb88d5629242006b9062841d7",
     "grade": true,
     "grade_id": "cell-9d614672798fb6bb",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "p=[2, 3, 5]\n",
    "assert p_depile(p) == 5\n",
    "assert p == [2, 3]\n",
    "assert p_depile([]) is None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "53160233d32653a08e2245aa730f7a58",
     "grade": false,
     "grade_id": "cell-105c0d4b0d91a50f",
     "locked": false,
     "schema_version": 3,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def p_empile(pile, v):\n",
    "    \"\"\"- prend en paramètre une pile et une valeur v\n",
    "    - empile la valeur v\n",
    "    Exemple : \n",
    "    >>> pile = [2, 3]\n",
    "    >>> p_empile(pile, 5)\n",
    "    >>> pile\n",
    "    >>> [2, 3, 5]\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "809d84490c5973377a57484b2ab44e18",
     "grade": true,
     "grade_id": "cell-b2e4998e26a60320",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "pile = [2, 3]\n",
    "p_empile(pile, 5)\n",
    "assert pile == [2, 3, 5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Les files\n",
    "\n",
    "Rappelons la notion de **files** répondant à la règle **FIFO** : premier entré, premier sorti.\n",
    "\n",
    "![file](my_icons/file1.png)\n",
    "\n",
    "### Description de la structure\n",
    "\n",
    "Pour stocker les données dans notre file, nous utiliserons un tableau python (objet list).\n",
    "- le dernier élément du tableau sera l'avant de la file. Seul cet élément sera visible\n",
    "- le premier élément du tableau sera l'arrière de la file\n",
    "\n",
    "**Exemple** : Si la file est représentée en mémoire par le tableau `[2, 3, 5, 8]`, l'avant de la file sera `8` et l'arrière de la file sera 2. Si on ajoute 1 à l'arrière de la file, celle-ci contiendra `[1, 2, 3, 5, 8]`. Une fois tous les éléments dépilés, la file sera vide et représentée par `[]`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "3c98d6b77c9b24c9991196f65d6c2935",
     "grade": false,
     "grade_id": "cell-e504a27404a8488d",
     "locked": true,
     "schema_version": 3,
     "solution": false
    }
   },
   "source": [
    "### A vous de jouer\n",
    "\n",
    "Vous allez devoir implémenter les fonctions\n",
    "- `f_valeur(file)`\n",
    "    - prend en paramètre une file\n",
    "    - renvoie la valeur à l'avant de la file ou `None` si la file est vide\n",
    "- `f_defile(file)`\n",
    "    - prend en paramètre une file\n",
    "    - défile l'élément situé à l'avant de la file\n",
    "    - renvoie la valeur défilée ou `None` si la file est vide\n",
    "- `f_emfile(file, v)`\n",
    "    - prend en paramètre une file et une valeur `v`\n",
    "    - emfile la valeur `v` à l'arrière de la file\n",
    "    - ne renvoie rien"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "288c6c03791ed23de29a3b8d27dd2222",
     "grade": false,
     "grade_id": "cell-f6e4709b5e9adf4d",
     "locked": false,
     "schema_version": 3,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def f_valeur(file):\n",
    "    \"\"\"- prend en paramètre une file\n",
    "    - renvoie la valeur à l'avant de la file ou None si la file est vide\n",
    "    Exemple : \n",
    "    >>> f_valeur([2, 3, 5])\n",
    "    >>> 5\n",
    "    >>> f_valeur([])\n",
    "    >>> None\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "1d34f74f9bb88a2c992278df31121a35",
     "grade": true,
     "grade_id": "cell-cf2a4fa81751c03d",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "assert f_valeur([]) is None\n",
    "assert f_valeur([2, 3, 5]) == 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "aefaa0f4047cc574f0ba573dc9ec2258",
     "grade": false,
     "grade_id": "cell-06b9232b2cd93301",
     "locked": false,
     "schema_version": 3,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def f_defile(file):\n",
    "    \"\"\"- prend en paramètre une file\n",
    "    - défile l'élément situé à l'avant de la file\n",
    "    - renvoie la valeur défilée ou None si la file est vide\n",
    "    Exemple : \n",
    "    >>> file = [2, 3, 5, 8]\n",
    "    >>> f_defile(file)\n",
    "    >>> 8\n",
    "    >>> file\n",
    "    >>> [2, 3, 5]\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "6583125aa8ecf328d169c9384bc12aeb",
     "grade": true,
     "grade_id": "cell-b6c2cf3fc29a2b12",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "file = [2, 3, 5, 8]\n",
    "assert f_defile(file) == 8\n",
    "assert file == [2, 3, 5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "64ee42d621c5efdec02757ab1cb19187",
     "grade": false,
     "grade_id": "cell-2a71af167d61fa9b",
     "locked": false,
     "schema_version": 3,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def f_enfile(file, v):\n",
    "    \"\"\"- prend en paramètre une file et une valeur v\n",
    "    - enfile la valeur v à l'arrière de la file\n",
    "    Exemple :\n",
    "    >>> file = [2, 3, 5, 8]\n",
    "    >>> f_enfile(file, 1)\n",
    "    >>> file\n",
    "    >>> [1, 2, 3, 5, 8]\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "a9f6529feddfc35cd1ec3ff9b86f0e3e",
     "grade": true,
     "grade_id": "cell-1702ab9f5c717d14",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "file = [2, 3, 5, 8]\n",
    "f_enfile(file, 1)\n",
    "assert file == [1, 2, 3, 5, 8]"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Éditer les Méta-Données",
  "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}