File (queue) avec collections.deque

Une file, c'est comme la file d'attente au cinema. Le premier arrive est le premier servi. On appelle ca FIFO : First In, First Out.

Les files sont utilisees partout : file d'attente d'impressions, messages a traiter, taches en attente d'execution.

Attention : avec une liste Python normale, retirer le premier élément (pop(0)) est O(n) car il faut decaler tous les éléments. C'est lent pour les grandes files. La solution : utiliser collections.deque, qui est optimise pour les opérations aux deux extremites en O(1).

Implemente une classe File avec les méthodes :
- enfiler(val) : ajoute un élément a la fin
- defiler() : retire et retourne l'élément du debut (leve IndexError si vide)
- tete() : retourne l'élément du debut sans le retirer (leve IndexError si vide)
- est_vide() : retourne True si la file est vide
- taille() : retourne le nombre d'éléments

Exemple :
f = File()
f.enfiler('A')
f.enfiler('B')
f.defiler() renvoie 'A'
f.tete() renvoie 'B'

Tests (3/4)

Enfiler/Defiler

f = File()
f.enfiler('A')
f.enfiler('B')
f.enfiler('C')
assert f.defiler() == 'A'
assert f.defiler() == 'B'

Tete

f = File()
f.enfiler(10)
f.enfiler(20)
assert f.tete() == 10
assert f.taille() == 2

Est vide

f = File()
assert f.est_vide() == True
f.enfiler(1)
assert f.est_vide() == False

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

from collections import deque

class File:
    def __init__(self):
        self._data = deque()

    def enfiler(self, val):
        self._data.append(val)

    def defiler(self):
        if self.est_vide():
            raise IndexError('File vide')
        return self._data.popleft()

    def tete(self):
        if self.est_vide():
            raise IndexError('File vide')
        return self._data[0]

    def est_vide(self):
        return len(self._data) == 0

    def taille(self):
        return len(self._data)

← Pile (stack) avec une liste Liste chainee simple →

solution.py

Bravo!

File (queue) avec collections.deque

Tests (3/4)

Indices (3 disponibles)

Solution officielle