Structure de file

04-03-2023

Objectifs

  • connaître la structure de données file

  • savoir en donner une implantation

  • savoir l’utiliser

Motivation

Structure de données importante en informatique :

  • file d’attente d’impression

  • utile pour parcours de graphes (trouver un chemin)

Opérations primitives sur les files

Les files sont des structures de données linéaires admettant les opérations primitives suivantes :

  • création d’une file ;

  • enfilement d’un élément sur une file ;

  • défilement d’une file ;

  • test de vacuité d’une file.

Note

Les files peuvent contenir en principe autant d’éléments qu’on veut (cependant en réalité elles sont en général limitées par la mémoire disponible). Mais il n’est pas possible d’accéder directement à n’importe lequel de ces éléments : seul l’élément qui y a été placé en premier est accessible, les autres ne l’étant pas tant que ce premier élément n’a pas été sorti de la file. C’est le principe du premier entré, premier sorti ou First In First Out (FIFO en abrégé).

Constructeurs

La construction d’une nouvelle file ne nécessite aucun paramètre :

ApQueue.__init__()
Build

a new empty queue

UC

none

>>> q = ApQueue()
>>> q
<apqueue.ApQueue at 0x7fbc840b4190>

Modificateurs

La structure de file est une structure de données mutable. Cela signifie que sa valeur ou son état peut changer au cours du temps.

Deux opérations primitives permettent cette mutabilité :

  • l’enfilement ;

  • et le défilement.

La méthode d’enfilement :

ApQueue.enqueue(x)
Paramètres

x (any) – a value

Renvoie

None

Type renvoyé

Nonetype

Side effect

queue self contains a new value : x

UC

none

::
>>> qu.enqueue(42)
>>> qu.enqueue(3)
>>> qu.enqueue(14)

et celle de défilement :

ApQueue.dequeue()
Renvoie

element on top of self

Side effect

self contains an element less

UC

self must be non empty

::
>>> qu.dequeue()
42
>>> qu.dequeue()
3

Prédicat

Un prédicat permettant de tester la vacuité d’une file :

ApQueue.is_empty()
Renvoie

  • True if s is empty

  • False otherwise

Type renvoyé

bool

UC

none

::
>>> qu.is_empty()
False
>>> qu.dequeue()
14
>>> qu.is_empty()
True

Une nouvelle exception

Le modificateur dequeue est soumis à une contrainte de non vacuité de la file à laquelle ils s’appliquent. Le non respect de cette contrainte déclenche une exception définie par le

class apqueue.ApQueueEmptyError(msg)

Exception for empty stacks

::
>>> qu.dequeue()
ApQueueEmptyError: empty queue, nothing to dequeue