Queues
Du hast den Begriff Queue zwar schon mal gehört, da Daten aber nicht Schlange stehen, kannst du nichts damit anfangen? Kein Problem, wir zeigen dir hier alles, was du wissen musst.
Inhaltsübersicht
Kettenartige Datenstruktur
Unter Queues in C versteht man eine Art von Datenstruktur, die nur eingeschränkten Eingriff auf die in ihr gespeicherten Werte gewährt. Konkret bedeutet das, dass wir immer nur auf das erste oder das letzte Element der Schlange Zugriff haben.
Funktion nach dem FIFO-Prinzip
Das kannst du dir vorstellen, wie eine Perlenkette. Wenn du Perlen auffädeln oder entfernen willst, geht das immer nur von den beiden Enden aus ohne die Kette zu zerstören. Genauso ist es auch mit den Datensätzen in einer Queue.
Aus genau diesem Grund arbeitet eine solche Datenstruktur auch nach dem First-in-first-out-Prinzip. Das limitiert den Zugriff auf diese Elemente noch stärker, da wir nun nur noch in derselben Reihenfolge auf sie zugreifen können, in der wir sie „eingereiht“ haben.
Queue Befehle
Eine Queue besitzt drei grundsätzliche Befehle: enter, mit dem wir ein neues Element hinzufügen, rem, mit dem wir das erste Element auslesen und löschen und first, mit dem wir das erste Element auslesen können, ohne es zu löschen.
Im Programmcode wirst du aber vermutlich niemals den Strukturtyp queue finden. Das liegt daran, dass diese Art von Datenstruktur meist als einfach verkettete Liste oder als dynamisches Feld realisiert wird.
Queue Schlange – Beispiel
Wollen wir nun als Beispiel einmal eine solche Schlange betrachten, sehen wir, dass sie einen Zeiger auf das erste und auf das letzte Element enthält.
Das Auslesen der Elemente funktioniert hier nur so reibungslos, da jedes Element jeweils auf das nächste in der Liste zeigt und du so alle nacheinander abarbeiten kannst. Das funktioniert also in etwa so, als würdest du einer Wegbeschreibung zu einem Coffee-Shop folgen, wo dich der Barista dann weiter zu einem Museum schickt, dort zeigt dir dann ein Mitarbeiter, wie du zu einer bestimmten Sehenswürdigkeit kommst, usw.
Hinzufügen und Auslesen eines Elements
Wollen wir ein Element hinzufügen, springen wir einfach zu dem Element, auf das last zeigt und ändern dieses Element, so dass es auf unser neues Element zeigt. Um jetzt aber weiterhin ein letztes Element zu haben, müssen wir jetzt noch last auf das NEUE, letzte Element zeigen lassen.
Mit dem Auslesen verhält es sich genauso. Du rufst das erste Element mittels first auf, löscht es und deklarierst das Element, auf das unser altes First zeigte als neues first.
Wie bei allen Datenstrukturen solltest du aber auch hier daran denken, am Ende immer wieder allen reservierten Speicherplatz freizugeben.
Jetzt weißt du auch was es mit den Queues auf sich hat und kennst dich nun mit Datenstrukturen in C bestens aus. Viel Erfolg beim Programmieren!