Les dèques

\(\newcommand{\ds}{\displaystyle}\) \(\newcommand{\Frac}{\ds\frac}\) \(\renewcommand{\r}{\mathbb{ R}}\) \(\newcommand{\C}{\mathbb{ C}}\) \(\newcommand{\n}{\mathbb{ N}}\) \(\newcommand{\z}{\mathbb{ Z}}\) \(\newcommand{\Q}{\mathbb{ Q}}\) \(\newcommand{\N}{\mathbb{ N}}\) \(\newcommand{\n}{\mathbb{ N}}\) \(\newcommand{\ol}{\overline}\) \(\newcommand{\abs}[1]{\left| \,{#1} \right|}\) \(\newcommand{\pv}{\;;\;}\) \(\newcommand{\ens}[1]{\left\{ {#1} \right\}}\) \(\newcommand{\mens}[1]{\setminus\left\{ {#1} \right\}}\) \(\newcommand{\Par}[1]{\left({#1}\right)}\) \(\newcommand{\pe}[1]{\left\lfloor {#1} \right\rfloor}\) \(\newcommand{\trans}[1]{\,^t\!{#1}}\)

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)}\)\(\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.