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 retiré

Une pile de livres.

Piles

LIFO : Last-In First-Out
- Le dernier inséré est toujours le premier retiré
Ajout uniquement en haut
- Push sur la pile

Pile de livres avec un nouveau livre ajouté en haut.

Piles

LIFO : Last-In First-Out
- Le dernier inséré est toujours le premier retiré
Ajout uniquement en haut
- Push sur la pile
Retrait uniquement en haut
- Pop de la pile

Pile de livres avec un livre retiré du haut.

Piles

LIFO : Last-In First-Out
- Le dernier inséré est le premier retiré
Ajout uniquement en haut
- Push sur la pile
Retrait uniquement en haut
- Pop de la pile
Lecture uniquement du dernier élément
- Peek de la pile

Pile de livres avec une flèche pointant la couverture du livre en haut de la pile.

Piles - cas réels

Fonction Annuler

Une pile avec un élément.

Piles - cas réels

Fonction Annuler
- push de chaque frappe

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

Piles - cas réels

Fonction Annuler
- push de chaque frappe

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

Piles - cas réels

Fonction Annuler
- push de chaque frappe

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

Piles - cas réels

Fonction Annuler
- push de chaque frappe

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

Piles - cas réels

Fonction Annuler
- push de chaque frappe
- pop de la dernière frappe

Une pile où un élément a été retiré du haut.

Piles - cas réels

Vérif. de symboles : ( [ { } ] )
- push des symboles ouvrants

Une pile avec un symbole ouvrant.

Piles - cas réels

Vérif. de symboles : ( [ { } ] )
- push des symboles ouvrants

Une pile avec un nouveau symbole ouvrant ajouté en haut.

Piles - cas réels

Vérif. de symboles : ( [ { } ] )
- push des symboles ouvrants

Une pile avec un nouveau symbole ouvrant ajouté en haut.

Piles - cas réels

Vérif. de symboles : ( [ { } ] )
- push des symboles ouvrants
- check du symbole fermant

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

Piles - cas réels

Vérif. de symboles : ( [ { } ] )
- push des symboles ouvrants
- check du symbole fermant
- pop du symbole ouvrant correspondant

Une pile où un symbole ouvrant a été retiré du haut.

Piles - cas réels

Appels de fonctions
- push d’un bloc mémoire
- pop après exécution

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

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

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

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

Une pile en 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 - implémentation avec listes simplement chaînées

Une pile en liste chaînée avec le mot « TOP » pointant le sommet.

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 éléments.

def push(self, data):

Piles - push

Pile vide et pile avec éléments où un nouveau nœud va être inséré.

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

  if self.top:

Piles - push

Pile vide et pile avec éléments, où le nouveau nœud est relié à l’élément du sommet.

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

    new_node.next = self.top

Piles - push

Pile vide et pile avec é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:

Pile avec le mot « TOP » pointant le nœud en haut.

Piles - pop

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

Pile avec « popped_node » pointant le nœud en haut.

Piles - pop

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

Pile avec « popped_node » pointant le nœud du haut et « 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

Pile avec « popped_node » pointant un nœud déconnecté et « TOP » pointant le 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

Pile avec le mot « TOP » pointant le nœud du 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