Algorithmen und Datenstrukturen

Queue

Die Queue (Warteschlange) ist eine der wichtigsten Datenstrukturen in vielen Algorithmen. Sie funktioniert ähnlich wie eine echte Warteschlange: Das erste Element, das hinzugefügt wird, ist auch das erste, das „bedient“ und entfernt wird.
Stell dir vor, eine Reihe von Ameisen steht in einer Schlange und wartet auf Kaffee. Die erste Ameise in der Reihe bekommt zuerst ihren Kaffee und verlässt danach die Schlange. Anschließend bekommt die nächste Ameise ihren Kaffee und verlässt die Schlange. Dieser Vorgang wird fortgesetzt, bis keine Ameisen mehr auf Kaffee warten und die Warteschlange leer ist.
notion image
Das Deklarieren und Verwenden einer Queue ist in den meisten Sprachen recht unkompliziert, da viele Allzweck-Programmiersprachen (wie Python, C++, Java usw.) bereits eine Queue-Datenstruktur zur Verfügung stellen. Trotzdem können wir eine Queue auch selbst mithilfe einer verketteten Liste implementieren. Hast du eine Idee, wie man das umsetzen könnte?
from queue import Queue

q = Queue()    # Erstelle eine neue Queue
q.put(1)       # Füge 1 an den Anfang der Queue
q.put(2)       # Füge als Nächstes 2 hinzu
q.put(3)       # Füge 3 nach 2 hinzu

# Entferne Elemente aus der Queue mithilfe von get()
print(q.get()) # gibt 1 aus
print(q.get()) # gibt 2 aus
print(q.get()) # gibt 3 aus

Herausforderung: Queue-Simulation

Du sollst ein System entwickeln, das die Kunden im Laden verwaltet. Es muss fähig sein, einen Kunden in die Warteschlange einzureihen und den ersten Kunden zu entfernen, sobald er bedient wurde. Jedes Mal, wenn ein Kunde entfernt wird, soll sein Name ausgegeben werden.

Eingabe

Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl n (1 ≤ n ≤ 100 000).
Die nächsten n Zeilen enthalten die Operationen – entweder add oder pop:
  • Die Operation add wird gefolgt von einem Namen, der zur Warteschlange hinzugefügt werden soll.
  • Die Operation pop enthält nur das Wort pop und weiter nichts.
Es ist garantiert, dass vor jeder pop-Operation bereits jemand in der Warteschlange steht, sodass die Operationen gültig sind.
Die Namen werden nicht länger als 20 Zeichen sein.

Ausgabe

Für jede pop-Operation soll das Programm den Namen des Kunden ausgeben, der sich gerade vorne in der Warteschlange befindet.

Beispiele

Eingabe
Ausgabe
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