Algorithmes et Structures de Données

Queue

La structure de données appelée “queue” (file d’attente) est l’une des plus fondamentales dans de nombreux algorithmes. Elle ressemble beaucoup à une file d’attente dans la vie de tous les jours. Le premier élément inséré dans la file sera le premier à être “servi” et à en être retiré.
Imaginez une rangée de fourmis qui attendent dans une file pour prendre un café. La première fourmi de la file prend son café puis quitte la file, ensuite la fourmi suivante fait de même, et ainsi de suite jusqu’à ce que la file soit vide et qu’il n’y ait plus de fourmis en attente de café.
notion image
Déclarer et utiliser une queue est très simple dans la plupart des langages, car la plupart des langages généralistes (comme Python, C++, Java, etc.) ont déjà implémenté la structure de données “queue” pour faciliter son utilisation. Nous pouvons néanmoins l’implémenter nous-mêmes en utilisant une liste chaînée. Avez-vous une idée de la façon de procéder 🤔?
from queue import Queue

q = Queue()    # Create a new queue
q.put(1)       # Add 1 to the front of the queue
q.put(2)       # Add 2 next
q.put(3)       # Add 3 after 2

# Remove elements from the queue using get()
print(q.get()) # prints 1
print(q.get()) # prints 2
print(q.get()) # prints 3

Défi : Simulation d’une file d’attente

Vous mettez en place un système qui doit suivre les clients présents dans le magasin. Deux opérations doivent être gérées par votre système : ajouter un client dans la file d’attente et retirer le premier client de la file d’attente quand il a été servi. À chaque fois que vous retirez un client, vous devez afficher son nom.

Entrée

La première ligne de l’entrée contient un entier n (1 ≤ n ≤ 100 000).
Les n lignes suivantes décrivent les opérations - soit add soit pop :
  • L’opération add est suivie d’un nom, ce qui signifie que vous devez ajouter ce client dans la file d’attente.
  • L’opération pop ne contient rien de plus que son nom, et permet de retirer le premier client de la file.
On vous garantit qu’il y a toujours au moins une personne dans la file avant chaque opération pop, donc les opérations sont valides.
Les noms ne dépasseront pas 20 symboles.

Sortie

Pour chaque opération pop, votre programme doit afficher le nom du client en tête de la file.

Exemples

Input
Output
9 add Steven add Sam pop add Sergio add Don pop add John pop pop
Steven Sam Sergio Don
4 add John Ford add Tom Ford pop pop
John Ford Tom Ford
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue