Was ist eine Queue?<\/h2>\n\n\n\n
Eine Queue ist eine Liste von Elementen, bei der die Elemente auf einer Seite eingef\u00fcgt und in derselben Reihenfolge auf der anderen Seite wieder entnommen werden.<\/p>\n\n\n\n
Man kann sich das wie eine Warteschlange an einer Kasse oder bei einer Beh\u00f6rde vorstellen:<\/p>\n\n\n\n
![\"Warteschlange\"](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/queue-of-people.v2-600x143.png\")
Ankommende Personen stellen sich am Ende der Schlange (rechts im Bild) an. Sobald ein Kunde abgefertigt wurde, kommt der n\u00e4chste Kunde vom Kopf der Schlange (links) an die Reihe.<\/p>\n\n\n\n
Die Person, die sich zuerst<\/em> angestellt hat, kommt somit auch zuerst<\/em> an die Reihe. Daher sprechen wir vom First-in-First-out-Prinzip (FIFO).<\/p>\n\n\n\n Beim abstrakten Datentyp \"Queue\" kann das wie im folgenden Beispiel aussehen:<\/p>\n\n\n\n Die Grafik zeigt eine Queue, die die Elemente 6, 7, 8, usw. bis 13 enh\u00e4lt. Die 5 wurde gerade vom Kopf der Queue (englisch \"Front\" oder \"Head\", links im Bild) entnommen und die 14 wird gerade an das Ende der Queue (\"Back\", \"Tail\" oder \"Rear\" im englischen, rechts im Bild) eingef\u00fcgt.<\/p>\n\n\n\n Die Operationen der Queue bezeichnen wir wie folgt:<\/p>\n\n\n\n (Die entsprechenden Methoden der Java-Queue-Implementierungen hei\u00dfen \u00fcbrigens anders; mehr dazu im n\u00e4chsten Teil des Tutorials, \"Java Queue-Interface<\/a>\".)<\/p>\n\n\n\n Ein Anwendungsbereich von Queues, den wir alle kennen, ist die Druckerwarteschlange. Verschiedene Programme stellen dort Druckauftr\u00e4ge ein. In der Regel gibt es nur einen Drucker, der diese dann der Reihe nach abarbeitet.<\/p>\n\n\n\n Ein technisches Anwendungsbeispiel ist die Verarbeitung von HTTP-Requests in einem Webserver. Ein Webserver arbeitet in der Regel mit einem Threadpool f\u00fcr gleichzeitig abzuarbeitende Requests. Wenn mehr Anfragen hereinkommen als gleichzeitig abgearbeitet werden k\u00f6nnen, ist der Threadpool ausgelastet. Zus\u00e4tzliche Requests werden dann in eine Warteschlange gestellt und in First-in-First-out-Reihenfolge abgearbeitet, sobald wieder Threads zur Verf\u00fcgung stehen.<\/p>\n\n\n\n Eine Einf\u00fchrung in das Thema Zeitkomplexit\u00e4t findest du im Artikel \"O-Notation und Zeitkomplexit\u00e4t \u2013 anschaulich erkl\u00e4rt<\/a>\".<\/em><\/p>\n\n\n\n Queues werden in der Regel mit Arrays<\/a> oder verketteten Listen<\/a> implementiert. Bei beiden Varianten ist der Aufwand f\u00fcr die Enqueue- und Dequeue-Operationen jeweils konstant, d. h. der Aufwand \u00e4ndert sich nicht mit der L\u00e4nge der Queue.<\/p>\n\n\n\n Die Zeitkomplexit\u00e4t dieser Operationen lautet also: O(1)<\/em>.<\/p>\n\n\n\n Zu \u00dcbungszwecken kann man eine Queue auch mit Stacks implementieren<\/a> (dazu mehr in einem sp\u00e4teren Teil des Tutorials). Die Zeitkomplexit\u00e4t ist dann allerdings h\u00f6her.<\/p>\n\n\n\nFIFO-Prinzip bei Queues<\/h2>\n\n\n\n
![\"Queue-Datenstruktur\"](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/queue-data-structure.v2-600x174.png\")
Queue Operationen: Enqueue und Dequeue<\/h2>\n\n\n\n
Anwendungsgebiete f\u00fcr Queues<\/h2>\n\n\n\n
Zeitkomplexit\u00e4t der Queue-Operationen<\/h2>\n\n\n\n