Aller au contenu

Implémentation avec tableau circulaire

Le cadre

On propose ici, en Python, une implémentation qui utilise en arrière-plan une structure de type list de Python, mais en limitant volontairement l'usage, comme un tableau, sans méthode dynamique. Ainsi l'implémentation pourrait être réalisée dans de nombreux langages de programmation avec de rares ajustements.

On montre ci-dessous des exemples d'une file modélisée par un tableau circulaire :

  • [_, _, _, _, _, _, _] : une file vide à 7 éléments au maximum
  • [1, 2, 3, 4, _, _, _] : une file avec 4 éléments enfilés
  • [_, _, 3, 4, _, _, _] : on a défilé 2 éléments
  • [8, _, 3, 4, 5, 6, 7] : on a enfilé 4 éléments
  • [8, _, _, _, _, 6, 7] : on a défilé 3 éléments
  • [_, _, _, _, _, _, _] : on a défilé 3 éléments ; la file est vide

Deux/trois variables utiles

On peut maintenir deux variables qui indiquent :

  • i : l'indice où enfiler le prochain élément
  • j : l'indice où défiler le prochain élément

Schématisons les 4 dernières étapes de l'exemple précédent

On va défiler le 6 à l'indice 6, il restera alors 2 éléments.

(Si on voulait enfiler, ce serait à l'indice 1)

graph TB
    classDef Nil stroke:none,fill:none,color:none;

    A["8"]

    B["None"]

    C["None"]

    D["None"]

    E["None"]

    F["None"]

    G["6"]

    H["7"]

    eA[" "]:::Nil ~~~ A
    eB@{ shape: braces, label: "i = 1" } --> B
    eC[" "]:::Nil ~~~ C
    eD[" "]:::Nil ~~~ D
    eE[" "]:::Nil ~~~ E
    eF[" "]:::Nil ~~~ F
    eG@{ shape: braces, label: "j = 6" } --> G
    eH[" "]:::Nil ~~~ H

    T@{ shape: braces, label: "taille = 3" }

On va défiler le 7 à l'indice 7, il restera alors 1 élément.

(Si on voulait enfiler, ce serait à l'indice 1)

graph TB
    classDef Nil stroke:none,fill:none,color:none;

    A["8"]

    B["None"]

    C["None"]

    D["None"]

    E["None"]

    F["None"]

    G["None"]

    H["7"]

    eA[" "]:::Nil ~~~ A
    eB@{ shape: braces, label: "i = 1" } --> B
    eC[" "]:::Nil ~~~ C
    eD[" "]:::Nil ~~~ D
    eE[" "]:::Nil ~~~ E
    eF[" "]:::Nil ~~~ F
    eG[" "]:::Nil ~~~ G
    eH@{ shape: braces, label: "j = 7" } --> H

    T@{ shape: braces, label: "taille = 2" }

On va défiler le 8 à l'indice 0, il restera alors aucun élément.

(Si on voulait enfiler, ce serait à l'indice 1)

graph TB
    classDef Nil stroke:none,fill:none,color:none;

    A["8"]

    B["None"]

    C["None"]

    D["None"]

    E["None"]

    F["None"]

    G["None"]

    H["None"]

    eA@{ shape: braces, label: "j = 0" } --> A
    eB@{ shape: braces, label: "i = 1" } --> B
    eC[" "]:::Nil ~~~ C
    eD[" "]:::Nil ~~~ D
    eE[" "]:::Nil ~~~ E
    eF[" "]:::Nil ~~~ F
    eG[" "]:::Nil ~~~ G
    eH[" "]:::Nil ~~~ H

    T@{ shape: braces, label: "taille = 1" }

La file est vide ; prête pour enfiler à l'indice 1.

graph TB
    classDef Nil stroke:none,fill:none,color:none;

    A["None"]

    B["None"]

    C["None"]

    D["None"]

    E["None"]

    F["None"]

    G["None"]

    H["None"]

    eA[" "]:::Nil ~~~ A
    eB@{ shape: braces, label: "i = j = 1" } --> B
    eC[" "]:::Nil ~~~ C
    eD[" "]:::Nil ~~~ D
    eE[" "]:::Nil ~~~ E
    eF[" "]:::Nil ~~~ F
    eG[" "]:::Nil ~~~ G
    eH[" "]:::Nil ~~~ H

    T@{ shape: braces, label: "taille = 0" }

Une autre variable est utile, la taille qui permet de savoir si la pile est vide ou pleine, car dans les deux cas, on a i == j.

Il y aurait une autre possibilité, ce serait interdire de remplir la dernière case libre... Dans ce cas, il faut initialiser un tableau avec une case de plus.

Exercice

On donne le début d'une classe File :

🐍 Script Python
class File():
    """Classe File avec tableaux Python"""

    def __init__(self, taille_max: int):
        self.taille_max = taille_max
        self.données = [None] * taille_max  # un tableau
        self.i = 0  # l'indice où on va enfiler un élément
        self.j = 0  # l'indice d'où on va défiler un élément
        self.taille = 0

Compléter la classe File (est_vide, enfile et défile) :

  • L'initialiseur prend taille_max en paramètre, et crée une file vide.
    • qui s'appuie sur un tableau de données, initialement rempli de None.
  • On peut enfiler jusqu'à atteindre la taille_max,
  • mais tenter d'enfiler un élément de plus provoquera raise ValueError("File pleine !")
  • Si on défile, on remplacera la donnée dans le tableau par None.
  • Tenter de défiler alors que la file est vide provoquera raise ValueError("File vide !")
  • L'attribut self.i indique :
    • l'indice du tableau où on va enfiler le prochain élément,
  • L'attribut self.j indique :
    • l'indice du tableau où on va défiler le prochain élément,
  • L'attribut self.taille indique la taille réelle de la file.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : ∞/∞
.128013x/.rnbylaeu)dV63Am(P+02è-],59f!78 N_o=pcwgv4F1`kRéhtsSàj[i:E050n0k0!0j0*0i0#0I0O0i0j0#0#0M010!0*0N010406050#0l0s0s0j0e0h040$0L0i0l100L0f050c17191b1d150N04051t1m1w0c1t150n0*0R0^0`0|0~0Z0*0Q0Z0i1K0Z0!13050:0g0i0k1F0{0}011J1L1N1L0!1T1V1R0!0e1u0!0Z1X1H010E0=0k0f0j0s0k010^1g0#0N0j0f0~0x1R22241=1Z1^1V1{1}130a0I0u0e0L0N0L0#0*1j0f0I0.200e0e0k0O2r1m290f1u0c1:2E1-1/1.1S0n2b0~1N0f1`2o1R1C1E0_1Y2O0*2Q0f0L2U1R0N2x1u2C2E2,16232s2W1?2#0e1a0i130I0U2B2:142/2a2=1Z2@2_2{0x2~24302C2N01350j2`040I0q392D153c330~3f3h0I0S3l3b2:3d3r2{0C3v3n3x3p3e0L2^3g2{0p3C312;1G343H363i0G3M3o3P3q3R3J3i0H3V3E3X3G3I3s0D3%323)3z040U0w3.3O2X3*3S0U2}1n2 3D3/3`3;0U383 3a413_2?3Z3h0U3k473m3N3y4c130U3u4g3w424b3+4l3B4o494j4s3=3L4v4i3F443U4B3W434k3=3$4G3(4I4y0U3-4M4q3Q4y0x3@4S4a4U3S0x3~2,4w4D4J0x464(4C3:4+4f4.4H4r4#4n4?4N4^3!0x4u4{4T3Y4V4A514Z534#4F2.1z2*1m2U2H0n1/2M3F0O2$1~1u5f1v5d5b2.5l0.2+4|1Z0W130.0E3v4/3`0P2{5D4@340E130k0#0!0K0R0*0.5I5x0~12040t5U52010g5X0#0k0i5C4o5E1?5X0m0+3C0I5@0I5.1Z0#2704010X1`0R0L0*1W0l2s0g0L1g0Y1`015?5^5`0~5z042x0!0l0e1l4o5_5J0~5%135)5+5!57010L130d6x3y130:0=1V3v6q5V6z130M0M6J6g010s0*134X4(4)3)6i5B6D3F5G3i6$3:5L041`2d0k6*3`5X5Z5-6r5$5(5*5,2.6_5X0B6Q6_0f130Y0i0Y1}0f0!6;5/135;6e5@6R5|13010r0(0L1i1W0V76781`0!0V0I0%0I0`0I0N1_6d4v5^6K5#6i0*6}2 7H6y6t046v7L3a6R6A046C6^6L74046G0i6I6p7U6N6P7)6_7P7R7c1Z7V7X6~7Z6F0;7%0k0K1a0b7;5W135=7F7G6f6_6i0e0;5)727Z5n0o3g0l0k0,2w3H81016?8n7j5~0T1_7B1V2Z1W0F7E7^5#5:7g7N3d6i5*8c7Y8C838E7G6R7/6|8n7?8n7!0n1k0f6b0#8n5X0)8n8Q6w8K6y8T8+6E040*8#130A8d5#7V7,2,8F4D7577797b85868}3)8)7S2D7*7W8U7`6H6:7-6L7V0v8{7M6R6T4l8N876L978S6B9c8:8^8,139j9x3d9n3=9p7h88137K9B3F9s8.3F8-8B6y7!8;9g8_7+9K966{8*9Q3d9P2 6R7!7$1V7~0j809N3)5X844(94948P9Z985w9V9b9:439I9X3`8`a31?9D6W406Y3`6!0k9|6R6(5_a02?6,0n0Y6/8=5Y8(9{ap7f93953`8r010,0f0i0y0R1W0/0I2x0f62647z000I7r907u7w1V8v0l0@240O642s2u7A6/8A408O9H8:9|aw1?9M9#9O9uaj349d7|a67=9W9U6ya8ap9?a)9^6R898b9f8|9)8f8h8j8l0eap6@a;3)ay8taT5R2u8zat8Eb55M0?b89(6 8Mava*7_047s91a{0~a5a~3da:bw9ha?bia1048W0f8Y5Nap8%a@6sasbX6M9 bO2?130(ap8@bz9q5#bK7T6_9%b;bBbRbT8!b!8$ar6u8Rb!b?9973b)b+bFb#9k3aa.5y0O130J1kbv489^cbbYb 9!bL9~7@co9Ra_7(b9b=130zc92Dck6S6U9Eb-9G9rbZb%a|b$cr8/b*bIa=049AcP3)9D4%b39_a+9JcT3`b:c3bMcLb@5#7!cOcvc)6Oc7c%9}9yc*c(c,ct7}7 b19F869`cmafcwc_c@cNc7bHc/5#b0cFcB890/6m6odbcsbCaQ7a3M0c5u0k2E2)ds5e1D5g2H2K2F0j1Udv0c5f15dF0/7{0#04.