Queues · Files (Queues)
A queue is FIFO
- A queue is First In, First Out (FIFO).
- The first item you add is the first one to leave.
- Think of a line of people: the person at the front is served first.
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 and dequeue with a list
- We can build a queue from a Python list.
- enqueue =
queue.append(x)— add to the back. - dequeue =
queue.pop(0)— remove and return the front.
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 and empty
- Look at the front without removing it:
queue[0]. - A queue is empty when
len(queue) == 0. - Check it is not empty before you dequeue.
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?
A note on speed
pop(0)has to shift every other item forward by one place.- For a big queue that is slow, so it uses more time.
- Real systems use a circular buffer with front and rear pointers instead.
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.
In Cambridge pseudocode
- The exam builds a queue from an array with a
frontand arearpointer.
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
Common mistakes
- A queue is first-in, first-out: join the back, leave from the front.
- Check it is not empty before you dequeue.
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.
Now you try
- Use a list as your queue (
appendto enqueue,pop(0)to dequeue). - Press Check answer to test your code.
À vous maintenant
- Utilisez une liste comme file (
appendpour enqueue,pop(0)pour dequeue). - Appuyez sur Vérifier la réponse pour tester votre code.
A queue is FIFO · Une file est FIFO
A queue adds at the back and removes at the front — first in, first out. · Une file ajoute à l'arrière et retire à l'avant — premier entré, premier sorti.
Start with an empty queue. Enqueue "a", then "b", then "c". Then dequeue · défiler once, storing the removed value in first. (first should be "a" and the queue should be ["b", "c"].) · Commencez avec une file vide. Enqueue "a", puis "b", puis "c". Ensuite, dequeue · défiler une fois, stockant la valeur retirée dans first. (first doit être "a" et la file doit être ["b", "c"].)
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Enqueue 1, 2, 3 onto a queue, then dequeue them all into result. Unlike a stack, a queue keeps the same · même order. (result should be [1, 2, 3].) · 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].)
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Write serve(queue) that dequeues the front item: remove it from the list and return · rendement it. The caller's list should get shorter. · Écrivez serve(queue) qui dequeues l'élément frontal : retirez-le de la liste et return · rendementlez-le. La liste de l'appelant devrait devenir plus courte.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Write front(queue) that returns · rendements the front item without removing it, so the queue is unchanged. If the queue is empty, return None. · É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.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.