Chapitre 2: Structures linéaires: piles, files


Programme Officiel

Contenus

Capacités attendues

Commentaires

Structures de données, interface et implémentation.

Spécifier une structure de données par son interface.

Distinguer interface et implémentation.

Écrire plusieurs implémentations d’une même structure de données.

L’abstraction des structures de données est introduite après plusieurs implémentations d’une structure simple comme la file (avec un tableau ou avec deux piles).

Listes, piles, files : structures linéaires.

Distinguer des structures par le jeu des méthodes qui les caractérisent.

Choisir une structure de données adaptée à la situation à modéliser.

On distingue les modes FIFO(`first_ in first out) et LIFO (last in first out) des piles et des files.

Lien vers le programme complet

Les piles

Les piles(stacks en anglais) correspondent exactement à la notion de pile dans la vie courante:

  • une pile de cartes,
  • une pile d'assiettes...

Data stack

Pour ajouter un élément on l'empile, il se retrouve donc au-dessus, et pour retirer un élément on ne peut retirer que l'élément se trouvant au sommet de la pile.

En anglais on dit last in, first out ou LIFO pour dire: dernier arrivé premier sorti.

Méthodes

Une pile est une liste sur laquelle on autorise seulement 4 opérations:

  1. Consulter le dernier élément de la pile(le sommet)
  2. Tester si la pile est vide
  3. Empiler un élément pour le mettre au sommet de la pile(PUSH)
  4. dépiler un élément pour le retirer du sommet de la pile(PULL)

Implémentation en Python

L'objet `list en Python présente deux méthodes qui lui permettent d'implémenter la pile:

  • list.append(el): ajoute l'élément en fin de liste.
  • list.pop(): supprime le dernier élement de la liste et le renvoie.
>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

Documentation de Python

Les files

Les files(queues en anglais) correspondent également à la notion de file dans la vie courante:

  • une file d'attente à la caisse,
  • à un feu rouge...

Data Queue.svg
By This Image was created by User:Vegpuff. If you are using the image under the creative commons share alike license please credit the photo Vegpuff/Wikipedia and include a link to this page. No explicit permission is needed from me, but an email if my work has been of help to you. If you dont want to release your work under a creative commons license, please mail me at vegpuff@gmail.com or catch me at my twitter stream for a custom license. - Own work, CC BY-SA 3.0, Link

Lorsqu'on ajoute un élément, celui-ci se retrouve à la fin de la queue, et on retire les éléments dans l'ordre dans lequel ils sont arrivés.

En anglais on on dit first in, first out ou FIFO pour dire: premier arrivé premier sorti.

Méthodes

Une file est une liste sur laquelle on autorise seulement 4 opérations:

  1. Consulter le premier élément de la file: la tête.
  2. Tester si la file est vide
  3. enfiler un nouvel élément: le mettre en dernier(ENQUEUE)
  4. défiler un élément, le premier (le supprimer) (DEQUEUE)

Implémentation en Python

L'objet `list en Python présente deux méthodes qui lui permettent d'implémenter la file:

  • list.append(el): ajoute l'élément en fin de liste.
  • list.pop(0): supprime le premier élément de la liste et le renvoie.

Toutefois, les listes ne sont pas très efficaces pour réaliser ce type de traitement. Alors que les ajouts et suppressions en fin de liste sont rapides, les opérations d'insertions ou de retraits en début de liste sont lentes (car tous les autres éléments doivent être décalés d'une position).

Pour implémenter une file, utilisez la classe collections.deque qui a été conçue pour réaliser rapidement les opérations d'ajouts et de retraits aux deux extrémités. Par exemple :

>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry")           # Terry arrives
>>> queue.append("Graham")          # Graham arrives
>>> queue.popleft()                 # The first to arrive now leaves
'Eric'
>>> queue.popleft()                 # The second to arrive now leaves
'John'
>>> queue                           # Remaining queue in order of arrival
deque(['Michael', 'Terry', 'Graham'])

Documentation de Python -->