Piles, Files, and Deques

TAD Piles (Stack)

Implémentation avec tableau
Implémentation avec liste simplement chaînée

TAD Files (Queue)

Implémentation avec tableau
Implémentation avec liste simplement chaînée

TAD Deques (Files à deux bouts)

Implémentation avec liste doublement chaînée

1
 Piles
PUSH

POP

2
 Piles
• Une pile contient des objets insérés et retirés selon le principe du
dernier arrivé, premier sorti (last-in-first-out LIFO)

• Les objets peuvent être insérés à tout moment, mais seulement le

dernier (le plus récemment inséré) peut être retiré

• Insérer un objet dans la pile correspond à l’empiler (pushing).

Dépiler la pile (popping) correspond au retrait d’un objet .

• Analogie: distributeur de bonbons

3
 Le TAD Pile (Stack)

• Méthodes fondamentales:
– push(e): Insérer l’objet e sur le dessus de la pile
(Empiler l’objet e)
– pop(): Retirer l’objet se situant sur le dessus de la pile et le
retourner (dépiler la pile); une erreur survient lorsque la pile est
vide.
• Méthodes secondaires
- size(): Retourne le nombre d’objets dans la pile
– isEmpty():Retourne un booléen indiquant si la pile est vide
– top(): Retourne l’objet du dessus de la pile, sans le retirer; une
erreur survient lorsque la pile est vide.
4
 Applications de Piles
• Applications directes
– L'historique des pages visitées dans un navigateur web
– Défaire la séquence écrite dans un éditeur de texte
(touche ‘supprimer’)
– La chaîne d’appel des méthodes dans la machine virtuelle
Java

• Applications indirectes
✓ Une structure de données auxiliaire
– Une composante d'autres structures de données

5
 Exemples

Évaluer une expression avec deux piles

( ( (10+5) + 5) / ( (2+3) * 2))

Comment nous le résolvons ?

6
Une séquence possible d'opérations

( ( ( 10+5 ) + 5) / (( 2+3 ) * 2))

( ( 15 + 5) / ( 5 * 2))

( 20 / 10 )

7
 Autre

( ( ( 10+5 ) + 5) / (( 2+3 ) * 2))

( ( 15 + 5) / (( 2+3 ) * 2))

( 20 / (( 2+3 ) * 2))

( 20 / ( 5 * 2))

( 20 / 10 )

2 8
 Avec deux Piles
une pour les opérandes
une pour les opérateurs

( ( (10+5) + 5) / ( (2+3) * 2))

5
10 +

S1 S2 9
 Avec deux Piles
une pour les opérandes
une pour les opérateurs
quand on trouve une parenthèse fermée
( ( 15 + 5) / (( 2+3) * 2))
( ( (10+5) + 5) / ( (2+3) * 2))

POP S1 5

POP S2 +
5
10 POP S1 10
15 +
Évaluer: 10 + 5 = 15
S1 S2 10
PUSH S1 le résultat
 Avec deux Piles
une pour les opérandes
une pour les opérateurs
une parenthèse fermée
( 20 / (( 2+3) * 2))
( ( (10+5) + 5) / ( (2+3) * 2))

POP S1 5

POP S2 +
5
POP S1 15
20
15 +
Évaluer: 15 + 5 = 20
S1 S2 11
PUSH S1 le résultat
 Avec deux Piles
une pour les opérandes
une pour les opérateurs
une parenthèse fermée
( 20 / (( 2+3) * 2))
( ( (10+5) + 5) / ( (2+3) * 2))

POP S1 3

POP S2 +
3
2
5 POP S1 2
+
20 /
Évaluer 2+ 3 = 5
S1 S2 PUSH S1 le résultat
12
 Avec deux Piles
une pour les opérandes
une pour les opérateurs

( 20 / ( 5 * 2))
( ( (10+5) + 5) / ( (2+3) * 2))

5
20 /

S1 S2 13
 Avec deux Piles
une pour les opérandes
une pour les opérateurs
une parenthèse
( 20 / ( 5 * 2)) fermée
( ( (10+5) + 5) / ( (2+3) * 2))

POP S1 2
POP S2 *
2 POP S1 5
10
5 *
Évaluer 5 * 2 = 10
20 /

S1 S2 PUSH S1 le résultat 14
 Avec deux Piles
une pour les opérandes
une pour les opérateurs
un parenthèse fermée
( 20 / 10 )
( ( (10+5) + 5) / ( (2+3) * 2))

10

10 /
20 / 20

S1 S2 20 / 10= 2 15
 Exemples

Vérifier équilibre des parenthèses

{ [ (a+b) -c]/d} { [ a+b) -c]/d}

16
 Réalisation d’une pile avec
tableau
La pile consiste en un tableau S de N-élément et une variable
entière t l'index du «premier» élément dans le tableau S (top de
la pile).

Algorithm size():
return t +1
Algorithm isEmpty():
return (t < 0)
Algorithm top():
if isEmpty() then
ERROR
return S[t] 17
Algorithm push(obj):
if size() = N then
ERROR
tt+1
S[t]  obj Algorithm pop():
if isEmpty() then
ERROR
e  S[t]
S[t]  null
t  t-1
return e

18
 Performance et Limitations
Time
• Performance size() O(1)
isEmpty() O(1) Espace: O(n)
top() O(1)
n = taille de le tableau
push(obj) O(1)
pop() O(1)

• Limitations

Structure statique

19
Réalisation d’une Pile à l’aide d’une
liste simplement chaînée
TOP

taille = 4

-Liste simplement chaînée avec un variable contenir la

taille actuelle de la liste

Structure Dynamique

20
 PUSH: Ajouter au devant

POP: Prendre le premier

21
 top

Algorithm push(obj):
n  new Node n
n.item  obj
n.setNext(top)
top  n
size++

Algorithm pop():
if isEmpty() then
ERROR
top
temp  top.item
top  top.getNext()
size- -
return temp
temp 22
 Performance

Temps:

size() O(1)
isempty() O(1)
top() O(1)
push(obj) O(1) Espace: Variable
pop() O(1)

Limitations: ?

23
La File (The Queue)

24
 La File (Queue)

first-in-first-out (FIFO)

Une file contient des objets insérés et retirés selon le

principe du premier arrivé, premier sorti (first-in-first-
out FIFO)

Les éléments sont enfilés (insérés) du coté arrière et

défilés (retirés) du coté avant

25
 Applications des files

• Applications directes
– Les listes d'attentes
– L'accès aux ressources partagées (ex.
imprimer)
– Multi-programmation
• Applications indirectes
– Les données auxiliaires structurent pour les
algorithmes
– Le composant d'autres structures de données

26
 Exemple: Palindromes

“non” “Rions noir”

“radar”
“Engage le jeu que je le gagne”

Lire la ligne dans une pile et dans une file

Comparer les résultants de la file et la pile

r
r a d a r a
Q d
a
S
r 27
 Le TAD File (Queue)

• Méthodes fondamentales:
enqueue(o): Insérer l’objet o à l’arrière de la file
dequeue(): Retirer l’objet qui est au début de la file et le retourner;
une erreur survient lorsque la file est vide

• Méthodes secondaires:
size(): Retourne le nombre d’objets dans la file
isEmpty(): Retourne un booléen indiquant si la file est vide
front(): Retourne l’objet qui est au début de la file sans le retirer;
une erreur survient lorsque la file est vide

28
 Implementation d’une file avec
tableau

0 1 2 3 4 5 6 7 8 9 10

• • • •
FRONT
REAR
Inserer REAR enlever de:
FRONT

0 1 2 3 4 5 6 7 8 9 10

• • • •
FRONT REAR

29
 Implementation d’une file avec
tableau
0 1 2 3 4 5 6 7 8 9 10

• • • •
FRONT REAR

0 1 2 3 4 5 6 7 8 9 10

• • • •
n-1 0
• • Insert ? FRONT REAR
1
• •
• 2
• • • • •
REAR
FRONT
30
 Implementation d’une file avec
tableau
0 1 2 3 4 5 6 7 8 9 10

• • • •
FRONT REAR

0 1 2 3 4 5 6 7 8 9 10

• • •
n-1 0 REAR FRONT
• • 1
• •
• 2
Remove: Front = (Front+1) mod n
Insert: Rear = (Rear+1) mod n
31
• configuration circulaire (“wrapped around”)
• Une taille fixée au début

•La file est composée d’un tableau Q de N éléments et de

deux variables entières:
-f, l’index de l’élément du devant
-r, l’index de l’élément suivant celui de l’arrière qui doit
toujours pointer à une case vide (donc la file ne peut
contenir que N-1 éléments)

n-1 0
1

32
 0 1 2 3 4 5 6 7 8 9 10

• • • •
f r
Questions:

Que veut dire f = r?

La File est vide.

Si la file est pleine, f est juste devant r.
Comment calculer le nombre d'éléments dans la
file ?

33
0 1 2 3 4 5 6 7 8 9 10

• • • • • • •

r f

(N - f + r) mod N

exemple:
(11 - 8 + 4) mod 11 = 7

34
 Algorithm dequeue():
Algorithm size(): if isEmpty() then
return (N - f + r) mod N ERROR
temp  Q[f]
Q[f]  null
Algorithm isEmpty(): f  (f + 1) mod N
return (f = r) return temp

Algorithm front(): Algorithm enqueue(o):

if isEmpty() then if size = N - 1 then
ERROR ERROR
return Q[f] Q[r]  o
r  (r+1) mod N

35
 Performance

temps:
espace: O(N)
size() O(1)
isempty() O(1)
front() O(1)
enqueue(o) O(1)
dequeue() O(1)

36
 Réalisation d’une File à l’aide d’une
liste simplement chaînée

Nœuds connectés en chaîne par de liens (links)

La tête de la liste (head) est le début de la file, la queue de la

liste (tail) constitue l’arrière de la file.
Pourquoi pas le contraire?
37
 Rappel : Suppression
r
(suppression de l’élément après r)
h
NULL

Premier élément (facile) h  h.getNext()

w  r.getNext()
Élément après r (facile)
r.setNext(w)
• Utiliser un pointeur à l’élément précédant, ou
Élément à r (difficile) • Échanger les contenus de l’élément à r avec les
contenus de l’élément suivent, et effacer l’élément
après r. **Très difficile si r indique dernier élément!

38
 Retirer l’élément de tête

Avancez la référence de la tête

Insérer un élément à la tête est tout aussi facile

39
Insérer un élément à la queue

Créez un nouveau nœud

Enchaînez-le et déplacez la référence à la queue

40
 Performance

temps:

size() O(1)
isempty() O(1)
front() O(1) Espace: Variable
enqueue(o) O(1)
dequeue() O(1)

41
Si une limite supérieure raisonnable est
connue à l’avance pour le nombre d'éléments
dans la file, alors

Tableau
Autrement

Listes

42
 TAD plus général TAD:
Files à deux bouts (Deque)

Une file à double têtes ou Deque (Double-ended queue) est une généralisation des types
files et piles. Les insertions et les suppressions d’éléments dans une Deque peuvent
s’effectuer aux deux bouts avant et arrière
•Méthodes fondamentales:
insertFirst(e): Insérer l’objet e au début de la Deque
insertLast(e): Insérer l’objet e à l’arrière de la Deque
removeFirst(): Supprimer et retourner l’objet qui est au début de la Deque *
removeLast(): Supprimer et retourner l’objet qui est à l’arrière de la Deque*
•Méthodes secondaires:
getfirst(): Retourne l’objet qui est au début de la Deque sans le retirer*
getlast(): Retourne l’objet qui est a l’arrière de la Deque sans le retirer*
size(): Retourne le nombre d’objets dans la Deque
isEmpty(): Retourne un booléen indiquant si la Deque est vide
* Erreur si Deque vide
43
 Réalisation des Deques à l’aide d’une liste
doublement chaînée

Effacer l’élément de queue d’une liste simplement chaînee

ne peut pas être fait en un temps constant

header trailer

Pour réaliser une deque, nous utilisons une liste

doublement chaînée avec des nœuds spéciaux pour l’avant
(header) et l’arrière (trailer)

44
 •Le nœud header est placé avant le premier élément de la liste. Sa
référence ‘suivant’ est valide tandis que sa référence ‘précédent’ est
null

•Le nœud trailer est placé après le dernier élément de la liste. Sa

référence ‘suivant’ est null tandis que sa référence ‘précédent’ est
valide

header trailer

NOTE: Les nœuds header et trailer sont des sentinelles ou nœuds

“bidons” parce qu’ils ne contiennent pas d’éléments.

45
 insertFirst(v):

insertFirst(v)
w
header trailer

wheader.getNext()
v.setNext(w)
v.setPrev(header)
w.setPrev(v)
header.setNext(v)
Size  size+1

46
 removeFirst():

removeFirst()
u v w

header trailer

u v.getPrev()
w v.getNext()
w.setPrev(u)
u.setNext(w)
v.setPrev(null)
v.setNext(null)
size size-1

47
visualisons le
code de
removeLast().

Avec cet réalisation, toutes les méthodes ont un temps

d’exécution constant (c’est-à-dire O (1))!
48
Réalisation de piles et de files à l’aide de
Deques

Méthodes de Pile Implémentation en Deque

isEmpty() isEmpty()
top() getLast()
push(e) insertLast(e)
Piles avec Deques:
pop() removeLast()
size() size()

Méthodes de Implémentation en Deque

Files avec Deques: File
isEmpty() isEmpty()
front() getFirst()
enqueue(e) insertLast(e)
dequeue() removeFirst()
size() size() 49
 Application 1 – Gestion d’un Annuaire de
contacts
On souhaite concevoir et implémenter une application C pour la
gestion d’un annuaire de contacts (contact directory) selon la
structure suivante :
:dir_t
: node_t : node_t : node_t
lists
Nbre
…
T
: contact_t
0 Nbre : contact_t
name : contact_t
phone name
. phone
name
. email
phone
. email
email
list_t=node_t*

T
…
i Nbre name name
phone phone
. email
. email
. prev ptrC next
… name
T phone
26 Nbre email 50
 Application 1 – Gestion d’un Annuaire de
contacts
Implémenter en langage C les types abstraits de données :
▪ contact_t, node_t, list_t, repo_t
Pour chaque type prévoir les opérations de bases nécessaires :
▪ Pour tous les types :
▪ constructeur, destructeur, toString
▪ Pour contact_t
▪ compare, print, …
▪ Pour la liste :
▪ add, delete, search, print, update
▪ Pour l’annuaire :
▪ add, delete, search, print, update

51