Les structures de données avancées

Introduction #

Une structure de données est une manière particulière de stocker et d'organiser des données dans un ordinateur de façon à pouvoir être utilisées efficacement.

Voici quelques structures de données standards :

• Liste : collection d'objets ordonnés hétérogènes accessible à partir de leur position.
• Tableau : collection d'objets ordonnés homogènes accessible à partir de leur position.
• Pile (en anglais STACK) : collection d'objets accessible selon une politique « dernier arrivé, premier sorti » (ou en anglais LIFO pour Last In, First Out). Ce qui veut dire que les derniers éléments ajoutés à la pile seront les premiers à être récupérés.
• File (en anglais QUEUE) : collection d'objets accessible selon une politique « premier arrivé, premier sorti » (ou en anglais FIFO pour First In, First Out). Les premiers éléments ajoutés à la file seront les premiers à être récupérés.
• File double (en anglais double-ended queue : abrégé dequeue et prononcé deck) : combine les accès LIFO et FIFO. C'est une structure de données qui implémente une file pour laquelle les éléments peuvent être ajoutés/récupérés au début et en fin.
• File à priorité (en anglais Priority Queue) : structure de données permettant de stocker des éléments et de retrouver efficacement celui qui a la plus haute priorité.

Les Piles #

Les Piles sont très utilisées en informatique, non seulement dans des applications utilisateurs mais également lors de l'exécution de programmes où elles sont utilisées pour stocker les contextes d'exécution des sous-programmes.

Les primitives

Voici les primitives communément utilisées pour manipuler une pile P :

• CreerPile : initialiser une pile vide.
• empiler (en anglais Push) : ajouter un élément au sommet de la pile.
• depiler (en anglais Pop) : enlève un élément de la pile et le renvoie.
• estVide (en anglais isEmpty) : renvoie vrai si la pile est vide, faux sinon.
• taille (en anglais size) : renvoie le nombre d'éléments dans la pile.
• sommet (en anglais top) : renvoie le dernier élément empilé dans la pile.

Les applications

• Dans un navigateur web, une pile sert à mémoriser les pages Web visitées. L'adresse de chaque nouvelle page visitée est empilée et l'utilisateur dépile l'adresse de la page précédente en cliquant le bouton « Afficher la page précédente ».
• Transformation d'une expression infixée en notation postfixée.
• L'évaluation des expressions mathématiques en notation post-fixée utilise une pile.
• La fonction « Annuler frappe » (Undo) d'un traitement de texte mémorise les modifications apportées au texte dans une pile.
• La fonction « Répéter frappe » (Redo) d'un traitement de texte permet de revenir à la dernière partie annulée d'un texte.
• Un algorithme de recherche en profondeur dans un arbre utilise une pile pour mémoriser les nœuds visités.
• Les algorithmes récursifs utilisent implicitement une pile d'appel.
• Transformer un algorithme récursif en itératif.
• Parseur d'expressions XML.
• Inverser un tableau ou une chaîne de caractères en utilisant une pile. Il suffit d'empiler les éléments sur une pile puis de reconstituer le tableau (ou la chaîne) inverse en dépilant les éléments.

Implémentations

À l'aide d'une liste, les opérations sur une pile P peuvent être réalisées comme suit :

• creerPile() : initialiser une liste vide
• estVide(P) : vrai si la liste est vide
• empiler(P, e) : ajouter un élément en tête de la liste
• depiler(P) : enlever un élément en tête de la liste et le renvoie
• taille(P) : renvoie la taille de la liste
• sommet(P) : renvoie l'élément en tête de la liste
• copier(P) : renvoie une copie de la pile

Module des piles avec des listes (Allocation dynamique) : modulePileListe.py

# créer et initialiser une pile
def creerPile():
    return []

# renvoie la taille de la pile
def taille(p):
    return len(p)

# vrai si la pile est vide, faux sinon
def estVide(p):
    return taille(p) == 0

# empiler un élément e dans la pile p
def empiler(p, e):
    p.append(e)

# supprime et renvoie l'élément en sommet de pile, ou None si la pile est vide
def depiler(p):
    if not estVide(p):
        return p.pop()
    else:
        return None

# renvoie l'élément en sommet de pile, ou None si la pile est vide
def sommet(p):
    if not estVide(p):
        return p[-1]
    else:
        return None

# copier une pile
def copier(p):
    return p[:]

Le programme suivant définit un menu et un programme principal permettant d'initialiser une pile, de tester si la pile est vide, d'ajouter ou de retirer des éléments en sommet de pile et de lister pour vérification le contenu de la pile. Le module modulePileListe.py peut être utilisé pour n'importe quel objet à empiler (entier, réel, personne, etc.).

from modulePileListe import *

def menu():
    print("\n\nGESTION D'UNE PILE D'ENTIERS\n\n")
    print("0 - Fin")
    print("1 - Initialisation de la pile")
    print("2 - La pile est-elle vide ?")
    print("3 - Insertion dans la pile")
    print("4 - Retrait de la pile")
    print("5 - Sommet de la pile")
    print("6 - Taille de la pile")
    print()
    return int(input('Votre choix ? '))

def main():
    p = creerPile()
    while True:
        c = menu()
        if c == 0:
            return
        elif c == 1:
            p = creerPile()
        elif c == 2:
            if estVide(p):
                print("Pile vide")
            else:
                print("Pile non vide")
        elif c == 3:
            valeur = int(input("Valeur à empiler ? "))
            empiler(p, valeur)
        elif c == 4:
            x = depiler(p)
            print(x)
        elif c == 5:
            x = sommet(p)
            print('Le sommet de la pile est :', x)
        elif c == 6:
            t = taille(p)
            print('La taille de la pile est :', t)

main()

Module des piles avec des tableaux (Allocation contiguë) : modulePileTab.py

Les piles peuvent être également gérées à l'aide d'un tableau alloué sur des cases contiguës et de taille a priori connue et donc limitée. Les éléments sont consécutifs en mémoire. Chaque élément du tableau contient un élément de la pile. La première case du tableau est réservée pour stocker la taille courante de la pile.

import numpy as np

# initialiser un tableau de taille = tailleMax + 1
# la première case est réservée pour la taille de la pile
def creerPile(tailleMax):
    return np.zeros(tailleMax + 1)

# ajouter un élément au sommet de la pile
def empiler(p, e):
    if not estPleine(p):
        p[0] += 1
        p[p[0]] = e

# renvoie vrai si la pile est pleine, et faux sinon
def estPleine(p):
    return p[0] == p.size - 1

# renvoie la taille de la pile
def taille(p):
    return int(p[0])

# renvoie vrai si la pile est vide, et faux sinon
def estVide(p):
    return p[0] == 0

# supprime et renvoie le sommet de la pile
def depiler(p):
    if not estVide(p):
        p[0] -= 1
        return p[int(p[0]) + 1]
    else:
        return None

# renvoie le sommet de la pile
def sommet(p):
    if not estVide(p):
        return p[int(p[0])]
    else:
        return None

# copier une pile
def copier(p):
    return p.copy()

Les Files #

En informatique, les files sont utiles pour mettre en attente des informations dans l'ordre dans lequel elles sont arrivées.

Les primitives

Voici les primitives communément utilisées pour manipuler une file F :

• CreerFile : initialiser une file vide.
• enfiler (en anglais enqueue) : ajouter un élément en fin de la file.
• defiler (en anglais dequeue) : enlève un élément en tête de la file et le renvoie.
• estVide (en anglais isEmpty) : renvoie vrai si la file est vide, faux sinon.
• taille (en anglais size) : renvoie le nombre d'éléments dans la file.
• tete (en anglais front) : renvoie l'élément en tête de la file.

Les applications

• Gestion d'une file de tâches d'impression sur l'imprimante d'un serveur d'impression.
• Messages en attente dans un commutateur de réseau.
• Demande d'accès à des ressources partagées.
• Dans un logiciel de chat, il est possible d'enfiler les messages reçus les uns à la suite des autres en mémoire. Par la suite, il devient possible de lire le premier message arrivé, puis le second, et ainsi de suite.
• Création de toutes sortes de mémoires tampons (en anglais buffers).
• Transformation d'une expression arithmétique infixée et parenthésée en expression postfixée.
• Parcours en largeur d'un graphe ou d'un arbre.

Implémentations

À l'aide d'une liste, les opérations sur une file F peuvent être réalisées comme suit :

• creerFile() : initialiser une liste vide
• estVide(F) : vrai si la liste est vide
• enfiler(F, e) : ajouter un élément en fin de la liste
• defiler(F) : enlever un élément au début de la liste et le renvoie
• taille(F) : renvoie la taille de la liste
• tete(F) : renvoie l'élément en tête de la liste
• copier(F) : renvoie une copie de la file

Module des files avec des listes (Allocation dynamique) : moduleFileListe.py

# créer et initialiser une file
def creerFile():
    return []

# renvoie la taille de la file
def taille(f):
    return len(f)

# vrai si la file est vide, faux sinon
def estVide(f):
    return taille(f) == 0

# enfiler un élément e dans la file f
def enfiler(f, e):
    f.append(e)

# supprime et renvoie l'élément en tête de la file, ou None si vide
def defiler(f):
    if not estVide(f):
        return f.pop(0)
    else:
        return None

# renvoie l'élément en tête de la file, ou None si vide
def tete(f):
    if not estVide(f):
        return f[0]
    else:
        return None

# copier une file
def copier(f):
    return f[:]

Le programme suivant définit un menu et un programme principal permettant d'initialiser une file, de tester si la file est vide, d'ajouter ou de retirer des éléments de la file. Le module moduleFileListe.py peut être utilisé pour n'importe quel objet à enfiler (entier, réel, personne, etc.).

from moduleFileListe import *

def menu():
    print("\n\nGESTION D'UNE FILE D'ENTIERS\n\n")
    print("0 - Fin")
    print("1 - Initialisation de la file")
    print("2 - La file est-elle vide ?")
    print("3 - Insertion dans la file")
    print("4 - Retrait de la file")
    print("5 - Tête de la file")
    print("6 - Taille de la file")
    print()
    return int(input('Votre choix ? '))

def main():
    f = creerFile()
    while True:
        c = menu()
        if c == 0:
            return
        elif c == 1:
            f = creerFile()
        elif c == 2:
            if estVide(f):
                print("File vide")
            else:
                print("File non vide")
        elif c == 3:
            valeur = int(input("Valeur à enfiler ? "))
            enfiler(f, valeur)
        elif c == 4:
            x = defiler(f)
            print(x)
        elif c == 5:
            x = tete(f)
            print('La tête de la file est :', x)
        elif c == 6:
            t = taille(f)
            print('La taille de la file est :', t)

main()

Module des files avec des tableaux (Allocation contiguë) : moduleFileTab.py

Les files peuvent être également gérées à l'aide d'un tableau alloué sur des cases contiguës et de taille a priori connue et donc limitée. Pour manipuler des files à l'aide d'un tableau de taille fixe, il faut utiliser deux variables supplémentaires : debut et fin. La variable debut correspond à l'indice du premier élément de la file. fin est une variable correspondant à l'indice du prochain élément à insérer. La file est vide si debut == fin. La file est pleine si fin == taille du tableau. Cette méthode est beaucoup moins coûteuse que le retrait du premier élément par décalage de tous les autres.

Version 1 — indices globaux :

import numpy as np

debut = fin = 0

def creerFile(tailleMax):
    return np.zeros(tailleMax)

def estPleine(f):
    global fin
    return fin == f.size

def taille(f):
    return f.size

def estVide():
    global fin, debut
    return debut == fin

def enfiler(f, e):
    global fin
    if not estPleine(f):
        f[fin] = e
        fin += 1
    else:
        print('File Pleine')

def defiler(f):
    global debut
    if not estVide():
        x = f[debut]
        debut += 1
        return x
    else:
        print('File Vide')

def tete(f):
    if not estVide():
        return f[debut]
    else:
        print('File Vide')

def afficher(f):
    global debut, fin
    if not estVide():
        for i in range(debut, fin):
            print(f[i])
    else:
        print('File Vide')

Version 2 — indices encapsulés dans la structure :

import numpy as np

# f[0] = indice debut, f[1] = indice fin, f[2] = tableau des valeurs
def creerFile(tailleMax):
    return [0, 0, np.zeros(tailleMax)]

def estPleine(f):
    return f[1] == f[2].size

def taille(f):
    return f[2].size

def estVide(f):
    return f[0] == f[1]

def enfiler(f, e):
    if not estPleine(f):
        f[2][f[1]] = e
        f[1] += 1
    else:
        print('File Pleine')

def defiler(f):
    if not estVide(f):
        x = f[2][f[0]]
        f[0] += 1
        return x
    else:
        print('File Vide')

def tete(f):
    if not estVide(f):
        return f[2][f[0]]
    else:
        print('File Vide')

def afficher(f):
    if not estVide(f):
        for i in range(int(f[0]), int(f[1])):
            print(f[2][i])
    else:
        print('File Vide')

Exercices avec corrigés #

Énoncés

Corrigés

from modulePileListe import *

def inverserPile(p):
    h = copier(p)
    l = creerPile()
    for i in range(taille(h)):
        x = depiler(h)
        empiler(l, x)
    return l

def depilerK(p, k):
    i = 1
    while (i <= k) and not estVide(p):
        depiler(p)
        i += 1

def depilerE(p, e):
    while not estVide(p) and sommet(p) != e:
        depiler(p)

def concatenerPile(p, q):
    x = inverserPile(q)
    for i in range(taille(q)):
        empiler(p, depiler(x))

from modulePileListe import *

def decode(s):
    a = creerPile()
    b = creerPile()
    for i in s:
        if i == '-' and not estVide(a):
            depiler(a)
        elif i == '>' and not estVide(b):
            empiler(a, b[-1])
            depiler(b)
        elif i == '<' and not estVide(a):
            empiler(b, a[-1])
            depiler(a)
        elif i.isalpha():
            empiler(a, i)
    ch1 = ""
    while not estVide(a):
        ch1 = depiler(a) + ch1
    ch2 = ""
    while not estVide(b):
        ch2 = depiler(b) + ch2
    ret = ch1
    for i in range(len(ch2) - 1, -1, -1):
        ret += ch2[i]
    return ret

n = int(input('Le nombre de fichiers ? '))
x = 0
ans = ''
for i in range(n):
    f = open('jour-' + str(i + 1) + '.txt')
    s = decode(f.read())
    f.close()
    ans += s[-1 * x] if x != 0 else s[0]
    x = (x + 1) % 2
print(ans)

from modulePileListe import *

def estValide(ch):
    p = creerPile()
    premiereMoitie = True
    for x in ch:
        if x == "*":
            premiereMoitie = False
            continue  # passer à l'itération suivante
        if premiereMoitie:
            empiler(p, x)
        else:
            if estVide(p):
                return False
            elif sommet(p) == x:
                depiler(p)
            else:
                return False
    return estVide(p)

# Exemples de test
print(estValide("abc*cba"))   # True
print(estValide("abc*cb"))    # False
print(estValide("ab*ba"))     # True

from modulePileListe import *

def infixe2postfixe(ch):
    p = creerPile()
    postfixee = ""
    priorite = {'*': 1, '/': 1, '+': 0, '-': 0}
    L = ch.split(" ")
    operateurs = ['+', '-', '*', '/']
    for x in L:
        if x not in operateurs:
            postfixee = postfixee + x + " "
        else:
            while not estVide(p) and priorite[sommet(p)] >= priorite[x]:
                postfixee = postfixee + depiler(p) + " "
            empiler(p, x)
    while not estVide(p):
        postfixee = postfixee + depiler(p) + " "
    return postfixee

print(infixe2postfixe("a * b - c"))     # a b * c -
print(infixe2postfixe("a - b * c * d")) # a b c * d * -

from modulePileListe import *

def evaluerPostfixee(ch):
    L = ch.split(" ")
    p = creerPile()
    for x in L:
        if x == "+":
            x1 = depiler(p); x2 = depiler(p)
            empiler(p, x1 + x2)
        elif x == "*":
            x1 = depiler(p); x2 = depiler(p)
            empiler(p, x1 * x2)
        elif x == "-":
            x1 = depiler(p); x2 = depiler(p)
            empiler(p, x2 - x1)
        elif x == "/":
            x1 = depiler(p); x2 = depiler(p)
            empiler(p, x2 / x1)
        elif x != "":
            empiler(p, int(x))
    return depiler(p)

print(evaluerPostfixee("3 2 + 4 *"))  # (3+2)*4 = 20
print(evaluerPostfixee("5 1 2 + 4 * + 3 -"))  # 14

from modulePileListe import *
from moduleFileListe import *

def infixeeToPostfixee(ch):
    p = creerPile()
    f = creerFile()
    pileparenthese = creerPile()
    priorite = {'*': 1, '/': 1, '+': 0, '-': 0}
    listeoperateurs = ['+', '-', '*', '/']
    listechiffres = [str(x) for x in range(10)]
    i = 0
    while i < len(ch):
        if ch[i] in listechiffres:
            s = ch[i]
            i += 1
            while i < len(ch) and ch[i] in listechiffres:
                s += ch[i]
                i += 1
            enfiler(f, int(s))
            enfiler(f, ' ')
        elif ch[i] in listeoperateurs:
            if not estVide(p):
                if estVide(pileparenthese):
                    if priorite[ch[i]] > priorite[sommet(p)]:
                        empiler(p, ch[i])
                    else:
                        while not estVide(p) and priorite[ch[i]] <= priorite[sommet(p)]:
                            enfiler(f, depiler(p))
                            enfiler(f, ' ')
                        empiler(p, ch[i])
                else:
                    empiler(p, ch[i])
            else:
                empiler(p, ch[i])
            i += 1
        elif ch[i] == ')':
            depiler(pileparenthese)
            enfiler(f, depiler(p))
            enfiler(f, ' ')
            i += 1
        elif ch[i] == '(':
            empiler(pileparenthese, '(')
            i += 1
    while not estVide(p):
        enfiler(f, depiler(p))
        enfiler(f, ' ')
    return f

def evaluerDepuisFile(f):
    p = creerPile()
    while not estVide(f):
        x = defiler(f)
        if x != ' ':
            if x in ['+', '-', '*', '/']:
                x1 = depiler(p); x2 = depiler(p)
                if x == '+':   empiler(p, x1 + x2)
                elif x == '-': empiler(p, x2 - x1)
                elif x == '*': empiler(p, x1 * x2)
                else:          empiler(p, x2 / x1)
            else:
                empiler(p, x)
    return sommet(p)

f = infixeeToPostfixee('3*(((12-3)/3)-1)')
print(evaluerDepuisFile(f))  # Affiche 6.0

from modulePileListe import *

def bienParenthesee(expr):
    p = creerPile()
    for x in expr:
        if x == '(':
            empiler(p, x)
        else:
            if estVide(p):
                return False
            else:
                depiler(p)
    return estVide(p)

def facteurs(expr):
    p = creerPile()
    L = []
    ch = ''
    for x in expr:
        if x == '(':
            empiler(p, x)
            ch += '('
        else:
            depiler(p)
            ch += ')'
            if estVide(p):
                L.append(ch)
                ch = ''
                p = creerPile()
    return '.'.join(L)

# Tests
print(bienParenthesee("(()())"))   # True
print(bienParenthesee("(()()"))    # False
print(bienParenthesee("(()))("))   # False

print(facteurs("(()())"))          # (()())
print(facteurs("()(()())"))        # ().(()())
print(facteurs("(())()(()())"))    # (()).(). (()())

from modulePileListe import *

def permutationCirculairePile(P, n):
    q = creerPile()
    r = creerPile()
    n = n % taille(P)
    i = 1
    # empiler les n premiers éléments de P dans q
    while i <= n:
        empiler(q, depiler(P))
        i += 1
    # inverser q dans r
    while not estVide(q):
        empiler(r, depiler(q))
    # vider le reste de P dans q
    while not estVide(P):
        empiler(q, depiler(P))
    # vider q dans r (les éléments restants de P, inversés)
    while not estVide(q):
        empiler(r, depiler(q))
    return r

# Test
P = creerPile()
for i in range(7, 0, -1):
    empiler(P, i)
print(P)  # [7, 6, 5, 4, 3, 2, 1]
P = permutationCirculairePile(P, 2)
print(P)  # [2, 1, 7, 6, 5, 4, 3]