Travailler avec des piles

Structures de données et algorithmes en Python

Miriam Antona

Software Engineer

Piles

LIFO : Last-In First-Out
- Le dernier inséré est le premier à être retiré

Une pile de livres.

Piles

LIFO : Last-In First-Out
- Le dernier inséré est toujours le premier à être retiré
Ajout uniquement au sommet
- Empiler sur la pile

Une pile de livres avec un nouveau livre ajouté au sommet.

Piles

LIFO : Last-In First-Out
- Le dernier inséré est toujours le premier à être retiré
Ajout uniquement au sommet
- Empiler sur la pile
Retrait uniquement au sommet
- Dépiler la pile

Une pile de livres avec un livre pris au sommet.

Piles

LIFO : Last-In First-Out
- Le dernier inséré est toujours le premier à être retiré
Ajout uniquement au sommet
- Empiler sur la pile
Retrait uniquement au sommet
- Dépiler la pile
Lecture uniquement du dernier élément
- Jeter un coup d'œil au sommet

Une pile de livres avec une flèche pointant la couverture du livre au sommet.

Piles – usages réels

Fonction « Annuler »

Une pile avec un élément.

Piles – usages réels

Fonction « Annuler »
- empiler chaque frappe

Une pile avec un nouvel élément ajouté au sommet.

Piles – usages réels

Fonction « Annuler »
- empiler chaque frappe

Une pile avec un nouvel élément ajouté au sommet.

Piles – usages réels

Fonction « Annuler »
- empiler chaque frappe

Une pile avec un nouvel élément ajouté au sommet.

Piles – usages réels

Fonction « Annuler »
- empiler chaque frappe

Une pile avec un nouvel élément ajouté au sommet.

Piles – usages réels

Fonction « Annuler »
- empiler chaque frappe
- dépiler la dernière frappe insérée

Une pile d'où un élément a été retiré du sommet.

Piles – usages réels

Vérification de symboles : ( [ { } ] )
- empiler les symboles ouvrants

Une pile avec un symbole ouvrant.

Piles – usages réels

Vérification de symboles : ( [ { } ] )
- empiler les symboles ouvrants

Une pile avec un nouveau symbole ouvrant ajouté au sommet.

Piles – usages réels

Vérification de symboles : ( [ { } ] )
- empiler les symboles ouvrants

Une pile avec un nouveau symbole ouvrant ajouté au sommet.

Piles – usages réels

Vérification de symboles : ( [ { } ] )
- empiler les symboles ouvrants
- vérifier le symbole fermant

Une pile avec des symboles ouvrants et le mot "check "}"".

Piles – usages réels

Vérification de symboles : ( [ { } ] )
- empiler les symboles ouvrants
- vérifier le symbole fermant
- dépiler le symbole ouvrant correspondant

Une pile d'où un symbole ouvrant a été retiré du sommet.

Piles – usages réels

Appels de fonction
- empiler un bloc mémoire
- dépiler à la fin de l'exécution

Piles – implantation avec listes chaînées simples

Une pile représentée comme une liste chaînée.

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

Piles – implantation avec listes chaînées simples

Une pile représentée comme une 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

Piles – implantation avec listes chaînées simples

Une pile représentée comme une liste chaînée avec le mot « TOP » pointant 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

Piles – push

Représentation d'une pile vide et d'une pile avec des éléments.

def push(self, data):

Piles – push

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:

Piles – push

Représentation d'une pile vide et d'une pile avec des éléments, où le nouveau nœud est relié à l'élément au sommet.

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

    new_node.next = self.top

Piles – push

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

Piles – pop

def pop(self):

  if self.top is None:

    return None

  else:

Représentation d'une pile avec le mot « TOP » pointant le nœud au sommet.

Piles – pop

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

Représentation d'une pile avec le mot « popped_node » pointant le nœud au sommet.

Piles – pop

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

Représentation d'une pile avec le mot « popped_node » pointant le nœud au sommet et le mot « TOP » pointant le deuxième nœud.

Piles – pop

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

Représentation d'une pile avec le mot « popped_node » pointant un nœud détaché de la pile et le mot « TOP » pointant le nœud au sommet.

Piles – pop

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

Représentation d'une pile avec le mot « TOP » pointant le nœud au sommet.

Piles – peek

def peek(self):

  if self.top:

    return self.top.data

  else:

    return None

LifoQueue en Python

LifoQueue :
- Module queue de Python
- se comporte comme une 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

Passons à la pratique !

Structures de données et algorithmes en Python