Piles Et Files

1Types abstraits pile et file, et leurs implementations

Piles et files sont deux types abstraits qui ne different que par l'ordre de sortie des elements. Ce detail apparemment mineur change radicalement le comportement des algorithmes qui les utilisent : le meme parcours de graphe devient un parcours en profondeur avec une pile, en largeur avec une file.

Implementation d'une pile par une liste

La liste Python offre exactement les operations d'une pile en \(\Theta(1)\), a condition de travailler par la fin.

def pile_vide():
    """Cree une pile vide."""
    return []

def empiler(p, x):
    """Ajoute x au sommet. Theta(1) amorti."""
    p.append(x)

def depiler(p):
    """Retire et renvoie le sommet. Theta(1). Precondition : pile non vide."""
    return p.pop()

def sommet(p):
    """Consulte le sommet sans le retirer."""
    return p[-1]

def est_vide(p):
    return len(p) == 0

p = pile_vide()
for x in [1, 2, 3]:
    empiler(p, x)
assert depiler(p) == 3        # dernier entre, premier sorti
assert sommet(p) == 2

Implementation d'une file

Ici la liste ne convient pas : pop(0) est en \(\Theta(n)\). Deux solutions.

from collections import deque

f = deque()
f.append(1)          # enfiler en queue     Theta(1)
f.append(2)
x = f.popleft()      # defiler en tete      Theta(1)
assert x == 1

def file_vide():
    return ([], [])          # (entree, sortie)

def enfiler(f, x):
    """Theta(1)."""
    f[0].append(x)

def defiler(f):
    """Theta(1) amorti."""
    entree, sortie = f
    if not sortie:                    # la pile de sortie est vide : on transvase
        while entree:
            sortie.append(entree.pop())
    return sortie.pop()

f = file_vide()
for x in [1, 2, 3]:
    enfiler(f, x)
assert defiler(f) == 1 and defiler(f) == 2

Recapitulatif des couts

2Comparaison interactive et applications

Application 1 — expressions bien parenthesees

def bien_parenthesee(s):
    """L'expression est-elle correctement parenthesee ? Theta(n)."""
    correspond = {")": "(", "]": "[", "}": "{"}
    pile = []
    for c in s:
        if c in "([{":
            pile.append(c)
        elif c in correspond:
            if not pile or pile.pop() != correspond[c]:
                return False
    return not pile

assert bien_parenthesee("{[()]}")
assert not bien_parenthesee("([)]")

La pile memorise les delimiteurs ouverts non encore fermes ; sa discipline LIFO correspond exactement a la regle d'imbrication.

Application 2 — notation polonaise inverse

def evalue_postfixe(expression):
    """Evalue une expression postfixee donnee sous forme de chaine. Theta(n)."""
    pile = []
    for jeton in expression.split():
        if jeton in "+-*/":
            b = pile.pop()          # ATTENTION a l'ordre : b est depile en premier
            a = pile.pop()
            if jeton == "+": pile.append(a + b)
            elif jeton == "-": pile.append(a - b)
            elif jeton == "*": pile.append(a * b)
            else: pile.append(a / b)
        else:
            pile.append(float(jeton))
    if len(pile) != 1:
        raise ValueError("expression mal formee")
    return pile.pop()

assert evalue_postfixe("3 4 +") == 7
assert evalue_postfixe("3 4 + 2 *") == 14
assert evalue_postfixe("5 1 2 + 4 * + 3 -") == 14

Application 3 — parcours de graphe

Le meme algorithme, au conteneur pres, donne deux parcours de natures tres differentes.

from collections import deque

def parcours_profondeur(G, depart):
    """Parcours en profondeur (DFS) avec une PILE."""
    vus, ordre, a_traiter = {depart}, [], [depart]
    while a_traiter:
        s = a_traiter.pop()               # LIFO : on repart du dernier decouvert
        ordre.append(s)
        for v in sorted(G[s], reverse=True):
            if v not in vus:
                vus.add(v)
                a_traiter.append(v)
    return ordre

def parcours_largeur(G, depart):
    """Parcours en largeur (BFS) avec une FILE."""
    vus, ordre, a_traiter = {depart}, [], deque([depart])
    while a_traiter:
        s = a_traiter.popleft()           # FIFO : on explore par couches
        ordre.append(s)
        for v in sorted(G[s]):
            if v not in vus:
                vus.add(v)
                a_traiter.append(v)
    return ordre

G = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"],
     "D": [], "E": ["F"], "F": []}
print(parcours_profondeur(G, "A"))    # ['A', 'B', 'D', 'E', 'F', 'C']
print(parcours_largeur(G, "A"))       # ['A', 'B', 'C', 'D', 'E', 'F']

3Pile d'execution, derecursivation et files de priorite

Pile d'execution et recursivite

La pile n'est pas seulement une structure de donnees : c'est le mecanisme meme de l'appel de fonction. A chaque appel, un bloc d'activation (parametres, variables locales, adresse de retour) est empile ; au return, il est depile.

import sys
print(sys.getrecursionlimit())     # 1000 par defaut

def profondeur(n):
    if n == 0:
        return 0
    return 1 + profondeur(n - 1)

profondeur(10000)      # RecursionError: maximum recursion depth exceeded

La limite protege contre le debordement de la pile systeme. On peut la relever (sys.setrecursionlimit), mais c'est generalement le signe qu'il faut derecursiver.

def somme_recursive(t, i=0):
    if i == len(t):
        return 0
    return t[i] + somme_recursive(t, i + 1)

def parcours_arbre_recursif(a):
    """a = None ou (valeur, gauche, droite)."""
    if a is None:
        return []
    v, g, d = a
    return parcours_arbre_recursif(g) + [v] + parcours_arbre_recursif(d)

def parcours_arbre_iteratif(a):
    """Meme parcours infixe, avec une pile explicite. Pas de RecursionError."""
    resultat, pile, courant = [], [], a
    while pile or courant is not None:
        while courant is not None:        # descendre a gauche en empilant
            pile.append(courant)
            courant = courant[1]
        courant = pile.pop()              # remonter
        resultat.append(courant[0])
        courant = courant[2]              # partir a droite
    return resultat

arbre = (2, (1, None, None), (3, None, None))
assert parcours_arbre_recursif(arbre) == [1, 2, 3]
assert parcours_arbre_iteratif(arbre) == [1, 2, 3]

File de priorite (tas)

import heapq

tas = []
heapq.heappush(tas, (3, "reparer"))
heapq.heappush(tas, (1, "urgent"))
heapq.heappush(tas, (2, "important"))
assert heapq.heappop(tas) == (1, "urgent")     # priorite minimale d'abord

# transformer une liste en tas sur place, en Theta(n)
t = [5, 3, 8, 1]
heapq.heapify(t)
assert heapq.heappop(t) == 1

Cette structure est au coeur de l'algorithme de Dijkstra (plus court chemin pondere) et du tri par tas.