Utilisation de piles

Structures de données et algorithmes en Python

Miriam Antona

Software Engineer

Piles

  • LIFO: Last-In First-Out
    • Dernier élément inséré sera le premier à être supprimé

Une image d'une pile de livres.

Structures de données et algorithmes en Python

Piles

  • LIFO: Last-In First-Out
    • Dernier élément inséré sera toujours le premier à être supprimé
  • Uniquement ajouter en haut
    • Empiler sur la pile

Une image d’une pile de livres avec un nouveau livre ajouté au sommet de la pile.

Structures de données et algorithmes en Python

Piles

  • LIFO: Last-In First-Out
    • Dernier élément inséré sera toujours le premier à être supprimé
  • Uniquement ajouter en haut
    • Empiler sur la pile
  • Ne peut retirer que par le haut
    • Retirer de la pile

Une image d’une pile de livres avec un livre retiré du dessus de la pile.

Structures de données et algorithmes en Python

Piles

  • LIFO: Last-In First-Out
    • Dernier élément inséré sera toujours le premier à être supprimé
  • Uniquement ajouter en haut
    • Empiler sur la pile
  • Uniquement retirer en haut
    • Retirer de la pile
  • Uniquement lire le dernier élément
    • Aperçu depuis la pile

Une image d’une pile de livres avec une flèche pointant vers la couverture du livre situé en haut de la pile.

Structures de données et algorithmes en Python

Piles - cas réels

  • Fonction d’annulation

Une pile avec un élément.

Structures de données et algorithmes en Python

Piles - cas réels

  • Fonction d’annulation
    • empiler chaque touche

Une pile avec un nouvel élément ajouté en haut de la pile.

Structures de données et algorithmes en Python

Piles - cas réels

  • Fonction d’annulation
    • empiler chaque touche

Une pile avec un nouvel élément ajouté en haut de la pile.

Structures de données et algorithmes en Python

Piles - cas réels

  • Fonction d’annulation
    • empiler chaque touche

Une pile avec un nouvel élément ajouté en haut de la pile.

Structures de données et algorithmes en Python

Piles - cas réels

  • Fonction d’annulation
    • empiler chaque touche

Une pile avec un nouvel élément ajouté en haut de la pile.

Structures de données et algorithmes en Python

Piles - cas réels

  • Fonction d’annulation
    • empiler chaque touche
    • retirer dernière touche

Une pile dont un élément a été retiré du sommet de la pile.

Structures de données et algorithmes en Python

Piles - cas réels

  • Vérificateur symboles : ( [ { } ] )
    • empiler symboles d’ouverture

Une pile avec un symbole d’ouverture.

Structures de données et algorithmes en Python

Piles - cas réels

  • Vérificateur symboles : ( [ { } ] )
    • empiler symboles d’ouverture

Une pile avec un nouveau symbole d’ouverture ajouté en haut de la pile.

Structures de données et algorithmes en Python

Piles - cas réels

  • Vérificateur symboles : ( [ { } ] )
    • empiler symboles d’ouverture

Une pile avec un nouveau symbole d’ouverture ajouté en haut de la pile.

Structures de données et algorithmes en Python

Piles - cas réels

  • Vérificateur symboles : ( [ { } ] )
    • empiler symboles d’ouverture
    • vérifier symbole fermeture

Une pile avec des symboles d’ouverture et le mot « check "}" ».

Structures de données et algorithmes en Python

Piles - cas réels

  • Vérificateur symboles : ( [ { } ] )
    • empiler symboles d’ouverture
    • vérifier symbole fermeture
    • retirer symbole d’ouverture correspondant

Une pile dont le symbole d’ouverture a été retiré du sommet de la pile.

Structures de données et algorithmes en Python

Piles - cas réels

  • Appels de fonction
    • empiler bloc de mémoire
    • retirer après fin d’exécution
Structures de données et algorithmes en Python

Piles - implémentation avec listes simplement chaînées

Une pile représentée sous forme de liste chaînée.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None
Structures de données et algorithmes en Python

Piles - implémentation avec listes simplement chaînées

Une pile représentée sous forme de liste chaînée avec les noms des parties des nœuds.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None
Structures de données et algorithmes en Python

Piles - implémentation avec listes simplement chaînées

Une pile représentée comme une liste chaînée avec le mot « TOP » pointant vers le sommet de la pile.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None
Structures de données et algorithmes en Python

Piles - empiler

Une représentation d’une pile vide et d’une pile avec des éléments.

def push(self, data):
Structures de données et algorithmes en Python

Piles - empiler

Une représentation d’une pile vide et d’une pile avec des éléments, où un nouveau nœud va être inséré.

def push(self, data): 
  new_node = Node(data)

  if self.top:
Structures de données et algorithmes en Python

Piles - empiler

Une représentation d’une pile vide et d’une pile avec des éléments, où le nouveau nœud est relié à l’élément situé en haut de la pile.

def push(self, data): 
  new_node = Node(data)
  if self.top:

    new_node.next = self.top
Structures de données et algorithmes en Python

Piles - empiler

Une représentation d’une pile vide et d’une pile avec des éléments, où le nouveau nœud a été inséré.

def push(self, data): 
  new_node = Node(data)
  if self.top:
    new_node.next = self.top
  self.top = new_node
Structures de données et algorithmes en Python

Piles - retirer

def pop(self):

  if self.top is None:

    return None

  else:

Une représentation d’une pile avec le mot « TOP » pointant vers le nœud situé en haut.

Structures de données et algorithmes en Python

Piles - retirer

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top

Une représentation d’une pile avec le mot « popped_node » pointant vers le nœud situé au sommet de la pile.

Structures de données et algorithmes en Python

Piles - retirer

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next

Une représentation d’une pile avec le mot « popped_node » pointant vers le nœud situé en haut de la pile et le mot « TOP » pointant vers le deuxième nœud.

Structures de données et algorithmes en Python

Piles - retirer

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None

Une représentation d’une pile avec le mot « popped_node » pointant vers un nœud déconnecté de la pile et le mot « TOP » pointant vers le nœud situé en haut de la pile.

Structures de données et algorithmes en Python

Piles - retirer

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None
    return popped_node.data

Une représentation d’une pile avec le mot « TOP » pointant vers le nœud situé en haut de la pile.

Structures de données et algorithmes en Python

Piles - aperçu

def peek(self):

  if self.top:

    return self.top.data

  else:

    return None
Structures de données et algorithmes en Python

LifoQueue dans Python

  • LifoQueue :
    • Module queue Python
    • se comporte comme pile
import queue


my_book_stack = queue.LifoQueue(maxsize=0)

my_book_stack.put("The misunderstanding")
my_book_stack.put("Persepolis")
my_book_stack.put("1984")


print("The size is: ", my_book_stack.qsize())

The size is: 3

print(my_book_stack.get())
print(my_book_stack.get())
print(my_book_stack.get())

1984
Persepolis
The misunderstanding

print("Empty stack: ", my_book_stack.empty())

Empty stack: True
Structures de données et algorithmes en Python

Passons à la pratique !

Structures de données et algorithmes en Python

Preparing Video For Download...