{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1> Implémentations d'une Pile : avec une liste ou avec une classe </h1>\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> 1.  Avec une liste </h3> <br>\n",
    "La fonction de création de pile devient donc :\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialisation d'une pile vide :\n",
    "def creer_pile():\n",
    "    \"Renvoie une pile vide.\"\n",
    "    return []\n",
    "\n",
    "# On créera ainsi une pile, initialement vide par p = creer_pile()\n",
    "# Compléter l'implémentation avec les fonctions suivantes ci-dessous\n",
    "def est_vide(p):\n",
    "    \"teste si p est vide et renvoie le booléen obtenu.\"\n",
    "    pass\n",
    "\n",
    "def empiler(p, x):\n",
    "    \"empile l'élément x sur la pile p.\"\n",
    "    pass\n",
    "\n",
    "def depiler(p):\n",
    "    \"dépile et renvoie l'élément au sommet de la pile p.\"\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# tests\n",
    "p=creer_pile()\n",
    "assert est_vide(p)==True\n",
    "empiler(p,\"bob\")\n",
    "empiler(p,\"Alice\")\n",
    "assert depiler(p)==\"Alice\"\n",
    "assert est_vide(p)==False\n",
    "depiler(p)\n",
    "assert est_vide(p)==True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Complèter le code des fonctions suivantes en utilisant uniquement les 4 fonctions de bases définies ci-dessus : ( ne pas utiliser len pour taille(p))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sommet(p):\n",
    "    \"renvoie le sommet de pile p ou un message d'erreur si la pile st vide\"\n",
    "    pass\n",
    "\n",
    "def taille(p):\n",
    "    \"renvoie la taille de pile p. attention la pile doit etre conservée ds son état initial \"\n",
    "    pass\n"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Prévoir l'affichage du code suivant puis l'éxécuter pour tester vos fonctions précédentes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p1=creer_pile()\n",
    "for i in range(5):\n",
    "    empiler(p1,2*i)\n",
    "print(p1)\n",
    "print(sommet(p1))\n",
    "depiler(p1)\n",
    "depiler(p1)\n",
    "print(est_vide(p1))\n",
    "print(sommet(p1))\n",
    "print(taille(p1))\n",
    "print(sommet(p1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> 2. Avec une classe pour l'implémentation d'une Pile </h3>\n",
    "Voici une définition de la classe pile  avec une méthode d'affichage. <br> \n",
    "Compléter-la "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Pile:\n",
    "    \"classe pile non bornée\"\n",
    "    def __init__(self):\n",
    "        \"\"\"initialisation d'une pile vide\"\"\"\n",
    "        self.L = []\n",
    "        \n",
    "    def est_vide(self):\n",
    "        \"\"\"teste si la pile est vide\"\"\"\n",
    "        pass\n",
    "    \n",
    "    def depiler(self):\n",
    "        assert not self.est_vide(), 'Pile vide'\n",
    "        pass\n",
    "\n",
    "    def empiler(self, x):\n",
    "        \"empile x sur la pile\"\n",
    "        \n",
    "    def __str__(self):\n",
    "        \"\"\" affichage de la pile sous la forme > 2 3 1]  avec 2 le sommet et 1 le bas de la pile\"\"\"\n",
    "        mot=\"]\"\n",
    "        for e in self.L: \n",
    "            mot=\" \"+str(e)+\" \"+mot\n",
    "        mot=\">\"+mot\n",
    "        return mot \n",
    "        "
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Prévoir l'affichage de l'éxécution du code suivant, puis vérifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p3=Pile()\n",
    "for i in range(9):\n",
    "    p3.empiler(i)\n",
    "print(p3)\n",
    "\n",
    "for i in range(2):\n",
    "    p3.depiler()\n",
    "print(p3.depiler())\n",
    "print(p3)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ecrire les fonctions ( et non les méthodes !) taille et sommet en utilisant la classe Pile"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def taille(p):\n",
    "    \"renvoie la taille de pile p. la pile doit etre conservée\"\n",
    "    pass\n",
    "def sommet(p):\n",
    "    \"renvoie le sommet de pile p ou un message d'erreur si la pile st vide\"\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p4=Pile()\n",
    "for i in range(5,10):\n",
    "    p4.empiler(i)\n",
    "print(p4)\n",
    "assert sommet(p4)==9\n",
    "assert taille(p4)==5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3>3. cas particulier : Pile à capacité finie </h3>\n",
    "Les fonctions de bases sont définies ci-dessous.<br>\n",
    "les valeurs du tableau sont initialisés à None sauf la 1ere valeur qui est le nombre d'élements dans la pile <br>\n",
    "Compléter par les fonctions taille(p), est_pleine(P), sommet(P)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def creer_pile_vide(N):\n",
    "    \"Renvoie une pile vide de capacité N.\"\n",
    "    T = [None for i in range(N + 1)]\n",
    "    T[0] = 0\n",
    "    return T\n",
    "\n",
    "\n",
    "def empiler(p, x):\n",
    "    \"empile l'élément x sur la pile p.\"\n",
    "    N = len(p) - 1\n",
    "    assert p[0] < N, 'Pile pleine'\n",
    "    p[0] += 1\n",
    "    p[p[0]] = x # on empile\n",
    "\n",
    "def est_vide(p):\n",
    "    \"teste si p est vide et renvoie le booléen obtenu.\"\n",
    "    return p[0] == 0\n",
    "\n",
    "def depiler(p):\n",
    "    \"dépile et renvoie l'élément x au sommet de la pile p.\"\n",
    "    assert not est_vide(p), \"Pile vide\"\n",
    "    x=p[p[0]]\n",
    "    p[p[0]] = None\n",
    "    p[0] -= 1 # on dépile\n",
    "    return x\n",
    "\n",
    "def taille(p):\n",
    "    \"renvoie la taille de pile p.\"\n",
    "     \n",
    "\n",
    "def est_pleine(p):\n",
    "    \"teste si p est pleine et renvoie le booléen obtenu.\"\n",
    "\n",
    "def sommet(p):\n",
    "    \"renvoie le sommet de pile p.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p5=creer_pile_vide(5)\n",
    "print(p5)\n",
    "empiler(p5,8)\n",
    "empiler(p5,22)\n",
    "empiler(p5,2022)\n",
    "print(p5)\n",
    "depiler(p5)\n",
    "print(p5)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(sommet(p5))\n",
    "print(taille(p5))\n",
    "empiler(p5,-5)\n",
    "empiler(p5,3)\n",
    "empiler(p5,100)\n",
    "print(p5)\n",
    "print(est_pleine(p5))\n",
    "print(depiler(p5))\n",
    "print(est_pleine(p5))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  },
  "vscode": {
   "interpreter": {
    "hash": "970a2a4939579a4c22872227820a264ec023ee5692739211cbaca24386397975"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}