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.
Studyflix vernetzt: Hier ein Video aus einem anderen Bereich
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!
Queues — häufigste Fragen
(ausklappen)
Queues — häufigste Fragen
(ausklappen)-
Was bedeutet queue auf Deutsch?„queue“ bedeutet auf Deutsch „Warteschlange“ oder kurz „Schlange“. Gemeint ist eine Datenstruktur, bei der Elemente wie in einer echten Warteschlange hinten hinzugefügt und vorne wieder entnommen werden. Dadurch passt auch die bildhafte Vorstellung, dass nur Anfang und Ende direkt zugänglich sind.
-
Wie implementiert man eine Queue in C mit first und last Zeigern?Eine Queue in C implementiert man mit einer Struktur, die zwei Zeiger speichert:
firstzeigt auf das erste Element undlastauf das letzte. Jedes Element ist einstructmit Nutzdaten und einemnext-Zeiger auf das nächste Element. Beim Einfügen wird am Ende angehängt undlastentsprechend weitergeschoben. -
Was müssen first und last sein, wenn die Queue leer ist?Bei einer leeren Queue muss man dafür sorgen, dass
firstundlastaufNULLzeigen. Dadurch ist eindeutig, dass kein Element vorhanden ist, und man kann vor dem Auslesen prüfen, ob die Queue leer ist. Sobald das erste Element eingefügt wird, zeigen beide Zeiger auf dieses eine Element. -
Wann muss man bei einer Queue in C malloc und free aufrufen?
mallocruft man auf, wenn beim Einfügen ein neues Queue-Element dynamisch erzeugt wird.freeruft man auf, wenn ein Element ausgelesen und aus der Queue entfernt wurde, damit der Speicher dieses Elements wieder freigegeben ist. Am Programmende müssen außerdem alle noch vorhandenen Elemente nacheinander freigegeben werden.
Nach Beantwortung speichern wir deine Antwort, um Studyflix zu verbessern. Mehr dazu erfährst du in unserer Datenschutzerklärung.
Datenstrukturen verstehen
Queues sind eine wichtige Datenstruktur in der Programmierung und ein typisches Beispiel für festen Zugriff auf gespeicherte Elemente. Du arbeitest mit verschiedenen Speicherformen wie Arrays oder verketteten Listen und legst fest, wie Einfügen und Entfernen im Code ablaufen. So erkennst du, welche Struktur zu einem Problem passt und worauf du bei Zeigern und Speicher achten musst. Weitere Videos dazu findest du in unserem Informatikbereich.