Les dèques¶
Rappel sur les dèques¶
Un dèque est une structure de données de type conteneur et qui s’utilise à la fois comme
- une pile (stack)
- une file d’attente (queue).
Le terme anglais de deque est un acronyme pour double-ended queue.
Usuellement, une fois un dèque créé, il s’utilise soit comme une pile soit comme une file mais pas les deux simultanément, bien que ce soit possible. Les opérations usuelles sur un dèque s’effectuent sur les extrémités droite et gauche de la structure de données et consistent en
- la lecture des extrémités
- des adjonctions (souvent traduites par
push
) - des suppressions (souvent traduites par
pop
)
Ces opérations de lecture, d’adjonction ou de suppression aux extrémités sont censées être efficaces, c’est-à-dire qu’elle ont un coût qui est un \(\mathtt{O(1)}\). En revanche, une lecture, une adjonction ou une suppression ailleurs qu’en une extrémité a un coût important qui est un \(\mathtt{O(n)}\) où \(\mathtt{n}\) est le nombre d’éléments du dèque. De toutes façons, en principe, aucune méthode d’un dèque ne permet d’effectuer des opérations sur des éléments différents des extrémités car un dèque n’est pas prévu pour cela.
Quelques algorithmes peuvent utiliser des dèques, par exemple les parcours d’un graphe en profondeur et en largeur.
Les dèques en Python¶
La bibliothèque standard Python propose la structure de données nommée deque
(sans accent et au singulier) via le module collections
. L’implémentation en CPython de ce module est écrite en C et non en Python, ce qui lui assure une bonne efficacité d’exécution.
Voici un exemple simple d’utilisation d’un dèque avec la bibliothèque standard :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | from collections import deque
t=[17, 87, 14, 18, 19]
# création d'un deque
d= deque(t)
print("création :", d)
# suppression à droite
d.pop()
print("suppression à droite :", d)
# suppression à gauche
d.popleft()
print("suppression à gauche :", d)
# insertion à droite
d.append(42)
print("insertion à droite :", d)
# insertion à gauche
d.appendleft(10)
print("insertion à gauche :", d)
|
26 27 28 29 30 | création : deque([17, 87, 14, 18, 19])
suppression à droite : deque([17, 87, 14, 18])
suppression à gauche : deque([87, 14, 18])
insertion à droite : deque([87, 14, 18, 42])
insertion à gauche : deque([10, 87, 14, 18, 42])
|
On trouvera un tableau des performances algorithmiques des opérations sur un dèque dans le wiki Python.
Création d’un dèque¶
Pour utiliser un dèque, il faut importer la structure de données deque
depuis le module standard collections
.
Un dèque est créé avec le constructeur deque
. On peut donner en argument à deque
n’importe quel itérable :
1 2 3 4 5 6 7 | from collections import deque
d= deque(range(10,15))
print(d)
d= deque("orange")
print(d)
|
8 9 | deque([10, 11, 12, 13, 14])
deque(['o', 'r', 'a', 'n', 'g', 'e'])
|
- Ligne 3 : le dèque est initialement formé de la liste des entiers de 10 à 14
- Ligne 6 : le dèque est initialement formé des lettres du mot
orange
.
Il est aussi possible de créer un dèque vide et de lui adjoindre des éléments par la suite, soit par la droite, soit par la gauche.
Taille d’un dèque¶
On peut connaître à tout moment le nombre d’élément d’un dèque avec la fonction standard len
:
1 2 3 4 5 6 | from collections import deque
L=[17, 87, 14, 18, 19]
d= deque(L)
print(len(d))
|
7 | 5
|
Adjonction et insertion¶
En dehors de la création, les opérations fondamentales d’un dèque sont :
- l’insertion à droite ou à gauche
- la suppression à droite ou à gauche
Les deux méthodes d’insertion sont : append
et appendleft
Les deux méthodes de suppression sont : pop
et popleft
Les méthodes append
et appendleft
prennent un argument qu’elles adjoignent à l’extrémité du dèque. Ces méthodes ne renvoient rien :
1 2 3 4 5 6 | from collections import deque
t=[17, 87, 14, 18, 19]
d= deque(t)
print(d.append(42))
|
7 | None
|
Les méthodes pop
et popleft
ne prennent aucun argument, retirent un élément à une extrémité du dèque et renvoient l’élément retiré :
1 2 3 4 5 6 7 8 | from collections import deque
t=[17, 87, 14, 18, 19]
d= deque(t)
print(d)
print(d.pop(), d.popleft())
print(d)
|
9 10 11 | deque([17, 87, 14, 18, 19])
19 17
deque([87, 14, 18])
|
Tenter de retirer un élément, d’un côté ou de l’autre, d’un dèque vide lève une exception de type IndexError
:
1 2 3 4 5 6 7 8 | from collections import deque
t=[17]
d= deque(t)
print(d)
d.pop()
d.pop()
|
9 10 11 12 | Traceback (most recent call last):
File "__.py", line 8, in <module>
d.pop()
IndexError: pop from an empty deque
|
Extension d’un dèque vide¶
Un procédé fréquent de remplissage d’un dèque est de partir d’un dèque vide et de lui rajouter soit par la droite, soit par la gauche des éléments :
1 2 3 4 5 6 7 8 | from collections import deque
d= deque()
print(len(d))
d.append(42)
d.appendleft(10)
print(d)
|
9 10 11 | deque([17, 87, 14, 18, 19])
0
deque([10, 42])
|
- Ligne 3 : création d’un dèque vide.
- Lignes 6-7 : on remplit le dèque, soit par la droite, soit par la gauche.
Création d’un dèque à partir d’un itérable¶
La création d’un dèque d
avec le constructeur deque
à partir d’un itérable t
, modifiable ou pas, entraîne la création de références vers les éléments de t
. En particulier, même si un itérable est modifiable, si un deque d
est construit à partir d’un itérable modifiable tel qu’une liste L
, toute modification de d
de type pop
ou append
est sans effet sur L
:
1 2 3 4 5 6 7 8 9 10 11 | from collections import deque
L=[17, 87, 14, 18, 19]
d= deque(L)
print("L :", L)
print("d :", d)
d.append(42)
print("d :", d)
print("L :", L)
|
12 13 14 15 | L : [17, 87, 14, 18, 19]
d : deque([17, 87, 14, 18, 19])
d : deque([17, 87, 14, 18, 19, 42])
L : [17, 87, 14, 18, 19]
|
Méthodes de dèque et méthodes de liste¶
Pour les deux méthodes qui agissent à droite (append
et pop
), on notera leur analogie avec les méthodes du même nom agissant sur des listes :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | from collections import deque
t=[17, 87, 14, 18, 19]
d= deque(t)
print(d)
d.pop()
d.append(42)
print(d)
print(t)
t.pop()
t.append(10)
print(t)
|
15 16 17 18 | deque([17, 87, 14, 18, 19])
deque([17, 87, 14, 18, 42])
[17, 87, 14, 18, 19]
[17, 87, 14, 18, 10]
|
Méthode extend
d’un dèque¶
De la même façon qu’une liste admet une méthode extend
qui permet d’étendre une liste par un itérable, un dèque possède des méthodes extend
(extension par la droite) et extendleft
(extension par la gauche) :
1 2 3 4 5 6 7 8 9 10 | from collections import deque
L=[17, 87, 14, 18, 19]
d= deque(L)
print(d)
d.extend([10, 100])
d.extendleft([-10, -100])
print(d)
|
11 12 | deque([17, 87, 14, 18, 19])
deque([-100, -10, 17, 87, 14, 18, 19, 10, 100])
|
Remplacer un dèque par une liste¶
Le cas d’une pile¶
En Python, une liste peut remplacer sans dégradation de performance un dèque si le dèque est utilisé comme une pile. Les méthodes d’adjonction et de suppression portent les mêmes noms (pop
et append
).
La cas d’une file¶
On pourrait simuler par une liste L
un dèque utilisé comme file d’attente. La suppression de l’élément tout à fait à gauche de L
se ferait par L.pop(0)
. Mais les performances seront mauvaises voire catastrophiques. En effet, l’insertion ou la suppression dans une liste par la gauche entraînent la réindexation de tous les éléments suivants.