IFT 2015
Démonstration 2 : Piles et début Listes
1
Piles
2
Rappel (1/5)
• Une pile (Stack) est une structure de données linéaire qui suit le principe LIFO
(Last-In-First-Out).
• Un seul pointeur pointant vers l'élément le plus haut de la pile. Chaque fois qu'un
élément est ajouté dans la pile, il est ajouté en haut de la pile et l'élément ne peut
être supprimé que de la pile.
3
Rappel : Opérations (2/5)
• push( e ) : ajoute l’élément e sur le haut de la pile
• pop( ) : retire et retourne l’élément sur le haut de la pile, null si vide
• top( ) : retourne l’élément sur le haut de la pile, null si vide
• size( ) : retourne le nombre d’éléments dans la pile
• isEmpty( ) : retourne un booléen indiquant si la pile est vide
4
Rappel : Opérations (3/5)
5
Rappel : Opérations (4/5)
6
Rappel : Opérations (5/5)
7
Exercices
8
Exercise 1 :
Supposons qu'une pile S initialement vide ait effectué un total de 25
opérations push, 12 opérations top et 10 opérations pop, dont 3 ont
renvoyé null pour indiquer une pile vide.
Quelle est la taille actuelle de S ?
9
Exercise 2 :
Supposons qu'une pile S initialement vide ait effectué dans l’ordre les
opérations suivantes : 1 pop ; 3 push ; 1 len ; 2 pop ; 1 isEmpty ; 5 push ; 2
top ; 7 pop ; 2 push ; 3 top.
Quelle est la taille actuelle de S ?
10
Exercise 3 :
Quelles valeurs sont renvoyées lors de la série suivante d'opérations de pile?
push(5), push(3), pop(), push(2), push(8), pop(), pop(), push(9), push(1),
pop(), push(7), push(6), pop(), pop(), push(4), pop(), pop().
11
Exercise 4 :
Montrez l'état de la pile S après les opérations suivantes :
S.pop() -> S.top() -> S.pop() -> S.push(45) -> S.top() -> S.pop() -> S.push(99)
-> S.push(18) -> S.top() -> S.top() -> S.push(55) -> S.push(83) -> S.pop()
32
12
25 12
Exercise 5 :
Donnez un pseudo code avec la signature transfer(S,T) qui transfère tous les
éléments de la pile S vers la pile T, de sorte que l'élément qui commence en
haut de S soit le premier à être inséré sur T et l'élément en bas de S se
termine en haut de T
13
Exercise 6 :
Donnez une méthode récursive pour supprimer tous les éléments d'une pile.
14
Exercise 7 :
Donnez une méthode “swap” qui échange les deux premiers éléments du
haut de la pile.
5 18
18 5
99 99
12 12
25 25
15
Exercise 8 :
Donnez une méthode qui renverse les éléments d’un tableau en utilisant une
pile.
16
Exercise 9 :
Implémentez une méthode qui permet de vérifier le balancement de parenthèses
• Chaque "(", "{", ou "[" doit être associé à ")", "}" ou “]”
• correct : ( )(( )){([( )])}
• correct : ((( )(( )){([( )])}))
• Incorrect : )(( )){([( )])}
• Incorrect : ({[ ])}
• Incorrect : (
17
Exercise 10 :
Implémentez une méthode qui permet de vérifier le balancement de “tags” HTML
18
Exercise 11 :
Supposons qu'Alice ait choisi trois entiers distincts et les ait placés dans une pile
S dans un ordre aléatoire.
Ecrivez une fonction en pseudo-code (sans boucles ni récursivité) qui utilise une
seule comparaison et une seule variable x, avec une probabilité de 2/3.
Expliquez pourquoi votre méthode est correcte.
19
Exercise 12 :
La notation postfixée est une manière non ambiguë d'écrire une expression
arithmétique sans parenthèses. Il est défini de sorte que si "(exp1)op(exp2)" est
une expression normale entièrement entre parenthèses dont l'opération est op,
la version postfixée de celle-ci est "pexp1 pexp2 op".
Décrivez une manière non récursive d'évaluer une expression en notation
postfixée en utilisant une pile. Déterminer la complexité.
20
Exercise 13 :
Implémentez un algorithme qui permet de convertir une expression infixée en
une expression postfixée en utilisant une pile.
Supposons que l'expression infixée est une string sans espace.
Par exemple,
Input: A*B+C
Output: AB*C+
Input: (A+B)*(C/D)
Output: AB+CD/*
21
Exercise 14 :
Implémentez un algorithme qui permet de convertir une expression prefixée en
une expression postfixée en utilisant une pile.
Par exemple,
Input : Prefix : *+AB-CD
Output : Postfix : AB+CD-*
22
Lists
23
Array Lists
Un choix évident pour implémenter la liste ADT est d'utiliser un tableau A, où A[i] stocke (une référence à)
l'élément d'indice i.
Implementer la class ArrayList qui implémente l'interface List de Java avec capacité = 16, ainsi que les
méthodes suivantes:
• Public int size(): Renvoie le nombre d'éléments dans ArrayList.
• Public Boolean isEmpty(): Retourne si ArrayList est vide.
• Public E get(int i): Renvoie (mais ne supprime pas) l'élément à l'index i
• Public E set(int I , E e) : Remplacer l'élément à l'index i par e ,et renvoie l'élément remplacé.
• Public void add(int i, E e): Insérer l'élément e pour qu'il soit à l'index i, en décalant tous les
• éléments suivants plus tard
• Public E remove(int i): Supprime et renvoie l'élément à l'index i, décalant les éléments
suivants plus tôt
Discuter la complexité de ces méthodes.
24
25
26
27
28
29
La complexité
30
