#Piles et filesCopier le lien

Prérequis: représentations tableau et liste chaînée (chapitre précédent), notion de coût amorti.

Objectifs:

• Énoncer les invariants LIFO et FIFO et reconnaître leurs cas d'usage.
• Connaître les coûts exacts de chaque opération selon la structure de support.
• Programmer un algorithme à pile (appariement de parenthèses) et le vérifier.

#Les invariantsCopier le lien

Pile (stack), LIFO. Last In, First Out: le dernier élément ajouté est le premier retiré. Tout ajout et tout retrait se font au même endroit, le sommet. C'est la discipline de la pile d'assiettes et de la pile d'appels du programme.

File (queue), FIFO. First In, First Out: le premier arrivé est le premier servi. Les ajouts se font à l'arrière, les retraits à l'avant. C'est la discipline des files d'attente.

Ces deux invariants sont plus forts qu'ils n'y paraît: ils garantissent à eux seuls l'ordre de sortie en fonction de l'ordre d'entrée, quelle que soit l'implémentation en dessous.

#PilesCopier le lien

#Opérations et coûtsCopier le lien

• push(x): ajouter au sommet, O(1)
• pop(): retirer et renvoyer le sommet, O(1)
• peek(): consulter le sommet sans le retirer, O(1)
• is_empty(): O(1)

Avec un tableau dynamique en support, push est O(1) amorti (doublement occasionnel du tableau); pop reste O(1), et la bonne implémentation réduit aussi la capacité quand la pile devient très creuse.

#La pile sur tableau, telle que le cours la décritCopier le lien

Une pile d'au plus n éléments se représente par un tableau S[1..n] plus un attribut top qui indexe l'élément le plus récemment inséré. La pile occupe exactement S[1..top]: S[1] est le fond, S[top] le sommet.

1STACK-EMPTY(S)21  si S.top == 0 alors renvoyer VRAI32  sinon renvoyer FAUX4 5PUSH(S, x)61  si S.top == S.size72      erreur « débordement de pile »83  sinon94      S.top = S.top + 1105      S[S.top] = x11 12POP(S)131  si STACK-EMPTY(S)142      erreur « pile vide »

Deux conditions de bord, deux comportements distincts: quand top = 0 la pile est vide et un pop provoque un sous-débordement; quand top dépasse la taille du tableau, un push provoque un débordement. Les deux sont des erreurs d'appelant, pas des erreurs d'implémentation: le code ci-dessus les signale au lieu de les absorber. Un pop qui renvoie silencieusement une valeur indéfinie sur pile vide est la source de bugs la plus coûteuse à traquer.

Détail à observer: après un pop, la case S[top+1] contient toujours l'ancienne valeur. Elle n'appartient plus à la pile, mais elle traîne en mémoire — un pop correct n'a rien à effacer, et un push ultérieur l'écrasera. C'est le comportement voulu, en O(1); c'est aussi ce qui fait qu'une pile conserve des références à des objets retirés, ce que le ramasse-miettes ne peut pas récupérer tant que la case n'est pas réécrite.

Exercice. Sur une pile vide stockée dans S[1..6], déroulez la séquence PUSH(S,4), PUSH(S,1), PUSH(S,3), POP(S), PUSH(S,8), POP(S). Donnez l'état du tableau et la valeur de top à chaque étape.

Correction:

À la fin, la pile contient les éléments 4 puis 1, avec top = 2; la case S[3] contient encore 8 mais n'appartient plus à la pile. Vérifiez le LIFO sur cet exemple: le 3 poussé en troisième est le premier sorti, puis le 8 poussé après le premier pop sort avant 1 et 4.

#Animation interactiveCopier le lien

Empilez et dépilez des valeurs: le message rappelle à chaque étape quel bout de la structure est touché, et le bouton de retour en arrière permet de rejouer une trace.

À retenir en manipulant: peu importe l'ordre exact de vos manipulations, un pop ne renvoie jamais que le dernier push encore présent. C'est l'invariant, pas le code, qui l'impose.

#Implémentation en PythonCopier le lien

1class Pile:2    def __init__(self):3        self.elements = []        # sommet = fin du tableau4 5    def push(self, element):6        self.elements.append(element)      # O(1) amorti7 8    def pop(self):9        if self.is_empty():10            raise IndexError("Pile vide")11        return self.elements.pop()         # O(1)12 13    def peek(self):14        if self.is_empty():

Lever une exception sur pile vide fait partie du contrat: un pop silencieux qui renvoie None masque les bugs de l'appelant.

#FilesCopier le lien

#Opérations et coûtsCopier le lien

• enqueue(x): ajouter à l'arrière, O(1)
• dequeue(): retirer l'avant, O(1) amorti
• front(): consulter l'avant, O(1)
• is_empty(): O(1)

Le piège classique: vouloir utiliser une list Python, où l'avant serait l'indice 0. Chaque dequeue décalerait alors n−1 éléments, O(n), et une boucle de n opérations monterait à O(n²).

#La file circulaire sur tableau, telle que le cours la décritCopier le lien

Une file d'au plus n − 1 éléments se représente par un tableau Q[1..n] avec deux attributs: head indexe la tête (le prochain élément à sortir) et tail indexe la case où sera écrit le prochain élément entrant. Les éléments occupent Q[head..tail−1] avec retour circulaire: la case 1 suit immédiatement la case n.

1ENQUEUE(Q, x)21  Q[Q.tail] = x32  si Q.tail == Q.size43      Q.tail = 1                    // retour au début du tableau54  sinon65      Q.tail = Q.tail + 17 8DEQUEUE(Q)91  x = Q[Q.head]102  si Q.head == Q.size113      Q.head = 1124  sinon135      Q.head = Q.head + 1146  renvoyer x

Invariants et cas limites:

• La file est vide quand head == tail. Initialement head = tail = 1.
• La file est pleine quand tail + 1 == head, ou quand head == 1 et tail == Q.size. C'est pourquoi un tableau de taille n ne stocke que n − 1 éléments: une case reste libre pour distinguer « pleine » de « vide ». Sans cette case perdue, head == tail serait ambigu entre les deux états.
• Le retour circulaire (lignes 2–3) est ce qui rend ENQUEUE et DEQUEUE en O(1) dans tous les cas, et non en O(1) amorti: on ne décale jamais rien. C'est l'avantage décisif de la file circulaire sur la file « tableau + décalage ».

Exercice. Sur une file vide stockée dans Q[1..12], déroulez ENQUEUE(Q,4), ENQUEUE(Q,1), ENQUEUE(Q,3), DEQUEUE(Q), ENQUEUE(Q,8), DEQUEUE(Q). Donnez l'état du tableau et les valeurs de head et tail à chaque étape.

Correction:

À la fin, la file contient 3 puis 8, avec head = 3 et tail = 5. Les cases 1 et 2 ne sont pas « perdues »: un ENQUEUE ultérieur y reviendra par le retour circulaire dès que tail atteindra 12. C'est là que le débogage d'une file circulaire se joue: un oubli du modulo sur une seule des deux opérations désynchronise head et tail, et la file finit par écraser ses propres éléments sans jamais paraître pleine.

#Animation interactiveCopier le lien

Saisissez une valeur et appuyez sur Enqueue pour l'ajouter à l'arrière; Dequeue retire l'avant. Les flèches Précédent/Suivant rejouent l'historique des états.

Observez l'invariant: si vous enfilez A, B, C puis défilez trois fois, l'ordre de sortie est exactement A, B, C. Aucune manipulation ne peut produire un autre ordre.

#Implémentation en PythonCopier le lien

1from collections import deque2 3class File:4    def __init__(self):5        self.elements = deque()   # O(1) aux deux bouts6 7    def enqueue(self, element):8        self.elements.append(element)      # O(1)9 10    def dequeue(self):11        if self.is_empty():12            raise IndexError("File vide")13        return self.elements.popleft()     # O(1)14 

#Exemple tracé: parenthèses équilibréesCopier le lien

La pile résout l'appariement de délimiteurs: la dernière parenthèse ouverte est toujours la première à devoir se fermer. LIFO exact.

1def parentheses_equilibrees(expression):2    pile = []3    paires = {')': '(', '}': '{', ']': '['}4    for c in expression:5        if c in '({[':6            pile.append(c)                  # ouvrante: empiler7        elif c in ')}]':8            if not pile or pile.pop() != paires[c]:9                return False                # rien à fermer, ou mauvaise paire10    return not pile                         # pile vide: tout est fermé11 12for expr in ["([{}])", "((())", "([)]", "{[()()]}", ""]:13    print(repr(expr), parentheses_equilibrees(expr))

Sortie attendue, à comparer à la vôtre: '([{}])' True, '((())' False, '([)]' False, '{[()()]}' True, '' True.

Trace de "([)]":

Coût: chaque caractère provoque au plus un empilement et un dépilement, O(n) temps, O(n) espace au pire (toutes ouvrantes).

Trois échecs distincts, trois causes distinctes: fermante sans ouvrante (pile vide au pop), mauvaise paire (sommet ne correspond pas), ouvrante jamais fermée (pile non vide à la fin). Un test complet couvre les trois.

#Cas d'usage canoniquesCopier le lien

Piles: pile d'appels du programme, évaluation et conversion d'expressions, détection de cycles en DFS, retour en arrière (backtracking), annuler/rétablir.

Files: parcours en largeur (BFS), ordonnancement équitable par arrivée, tampons entre producteur et consommateur, spools d'impression.

#Exercice: une file avec deux pilesCopier le lien

Implémentez une file FIFO avec deux piles inbox et outbox uniquement:

• enqueue(x): pousser x sur inbox.
• dequeue(): si outbox est vide, dépiler tout inbox dans outbox (l'ordre s'inverse une bonne fois), puis dépiler outbox.

Correction et analyse: chaque élément est poussé une fois sur inbox, transféré au plus une fois vers outbox, dépilé une fois de outbox: trois opérations O(1) par élément sur une suite de n opérations, donc O(1) amorti par opération, même si un dequeue isolé peut coûter O(n) (le transfert massif). La correction tient à l'inversion: le premier entré dans inbox ressort en dernier de la pile, donc en premier de outbox après transfert, exactement le FIFO.

Vérification: enfilez 1, 2, 3, défilez (doit rendre 1), enfilez 4, défilez deux fois (doit rendre 2 puis 4). Vérifiez aussi le cas délimité: dequeue sur les deux piles vides doit signaler l'erreur, pas renvoyer None.

L'exercice symétrique est plus retors: implémenter une pile avec deux files. Il faut maintenir une file « pleine » et une file « vide »; à chaque push, on enfile le nouvel élément dans la file vide, puis on y transfère toute la file pleine, et on échange les rôles. Le sommet est alors toujours en tête de la file pleine, donc pop se réduit à un dequeue en O(1), mais push coûte O(n) dans tous les cas — aucune analyse amortie ne le sauve, le transfert est intégral à chaque insertion. Comparer les deux exercices est instructif: la même technique (deux structures, un transfert d'inversion) donne O(1) amorti dans un sens et O(n) systématique dans l'autre.

#Deux structures dans un seul tableauCopier le lien

Un tableau de taille n peut héberger deux piles, l'une poussée depuis l'indice 1 vers la droite, l'autre depuis l'indice n vers la gauche. Chaque pile a son propre attribut de sommet; la condition de débordement est commune: sommet_gauche + 1 == sommet_droit. Aucune des deux ne déborde tant que le nombre total d'éléments n'atteint pas n, et push comme pop restent en O(1). C'est la réponse à « comment faire tenir deux piles dans un tableau sans gaspiller la moitié de la place? » — et c'est exactement le schéma utilisé par les allocateurs de mémoire qui gèrent une pile d'appels et un tas croissant l'un vers l'autre.

Un deque (double-ended queue, « file à deux bouts ») généralise la pile et la file: insertion et suppression possibles aux deux extrémités. Quatre procédures suffisent, toutes en O(1):

Une pile est un deque utilisé d'un seul côté (push_back/pop_back); une file est un deque utilisé des deux côtés (push_back/pop_front). En Python, collections.deque implémente exactement ce contrat, avec en plus un accès indexé O(1) au voisinage des extrémités et O(n) au milieu.