Files (Queues)
Une file est FIFO
- Une file est First In, First Out (FIFO - Premier entré, premier sorti).
- Le premier élément ajouté est le premier à sortir.
- Pensez à une file de personnes : celle au début est servie en premier.
enqueue et dequeue avec une liste
- Nous pouvons construire une file à partir d'une liste Python.
- enqueue =
queue.append(x)— ajouter à l'arrière. - dequeue =
queue.pop(0)— retirer et retourner l'avant.
queue = []
queue.append("first")
queue.append("second")
print(queue.pop(0))
print(queue)
front et empty
- Regarder l'avant sans le retirer :
queue[0]. - Une file est vide quand
len(queue) == 0. - Vérifiez qu'elle n'est pas vide avant de faire un dequeue.
queue = [10, 20, 30]
print(queue[0]) # the front
print(len(queue) == 0) # is it empty?
Note sur la vitesse
pop(0)doit déplacer chaque autre élément d'une place vers l'avant.- Pour une grande file, c'est lent, donc cela consomme plus de temps.
- Les systèmes réels utilisent un tampon circulaire avec des pointeurs front et rear au lieu.
En pseudocode Cambridge
- L'examen construit une file à partir d'un tableau avec un pointeur
frontet un pointeurrear.
DECLARE queue : ARRAY[1:10] OF INTEGER
DECLARE front, rear : INTEGER
front ← 1
rear ← 0 // empty
// enqueue value
rear ← rear + 1
queue[rear] ← value
// dequeue into value
value ← queue[front]
front ← front + 1
Erreurs courantes
- Une file est first-in, first-out : rejoignez l'arrière, quittez depuis l'avant.
- Vérifiez qu'elle n'est pas vide avant de faire un dequeue.
À vous maintenant
- Utilisez une liste comme file (
appendpour enqueue,pop(0)pour dequeue). - Appuyez sur Vérifier la réponse pour tester votre code.
Une file est FIFO
Une file ajoute à l'arrière et retire à l'avant — premier entré, premier sorti.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Commencez avec une file vide. Enqueue "a", puis "b", puis "c". Ensuite, défiler une fois, stockant la valeur retirée dans first. (first doit être "a" et la file doit être ["b", "c"].)
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Enqueuez 1, 2, 3 dans une file, puis dequeuez-les tous dans result. Contrairement à une pile, une file conserve le même ordre. (result doit être [1, 2, 3].)
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Écrivez serve(queue) qui dequeues l'élément frontal : retirez-le de la liste et rendementlez-le. La liste de l'appelant devrait devenir plus courte.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Écrivez front(queue) qui retourne l'élément frontal sans le retirer, afin que la file reste inchangée. Si la file est vide, retournez None.
Cliquez sur Exécuter pour voir le résultat ici.