Advanced   Java   Services

Queue

Eine Queue ist eine Reihe von Elementen, die nach dem FIFO-Prinzip (First In First Out) geordnet ist. Eine Queue kann man sich etwa vorstellen wie eine Warteschlange an der Supermarktkasse. Man betritt die Schlange als erster und verläßt sie als erster.

Das Aufnehmen eines Elements findet immer am Ende statt, das Entnehmen eines Elements immer an der Spitze. Diese Operationen kennen wir schon von der einfach verketteten Liste. In diesem Zusammenhang wird das Aufnehmen eines Elements gerne push oder put genannt, das Entnehmen meist poll oder pop oder auch get.

/*
 * Fügt ein neues Element am Ende ein
 * Gibt einen Zeiger auf das neue Endelement zurück oder NULL
 */
node* push(node* oldtail, int data)
{
   if (oldtail == NULL ) return NULL;

   node *newtail = malloc(sizeof(node));
   if (newtail==NULL) return NULL;

   while (oldtail->next != NULL)  // ans Ende
      oldtail = oldtail->next;

   // nun ist oldtail->next NULL
   oldtail->next = newtail;
   newtail->next = NULL;
   newtail->data = data;
   return newtail;
}

/*
 * Holt das erste aus der Schlange. Gibt den alten Kopf
 * zurück, neuer Kopf wird über den Parameter gesetzt.
 */
node* poll(node** pHead)
{
   if (pHead == NULL || *pHead == NULL ) return NULL;

   node* oldHead = *pHead; // alten kopf aufheben
   *pHead = oldHead->next; // neuen kopf setzen
   return oldHead;
   // oldHead muß vom Rufer freigegeben werden!
}

Hinter dem Namen createHead verbirgt sich die Funktion createRoot aus dem Kapitel über einfach verkettete Listen

/*
 * Kopf einer neuen Schlange erstellen
 */
node* createHead(int data)
{
   node *head = malloc(sizeof(struct node));
   if( head != NULL)
   {
      head->data = data;
      head->next = NULL;
   }
   return head;
}

Die Funktionen printList, listLength und seekList kann man direkt aus dem Kapitel über einfach verkettet Listen übernehmen, ebenso die Funktion freeList die jetzt den Namen freeQueue erhält.

Da eine Queue eine einfach verkettete Liste ist funktioniert das Freigeben wie vorher.

/*
 * Gibt den Speicher ab der Stelle curr frei. Ist der übergebene
 * Knoten der Wurzelknoten, so wird die ganze Liste gelöscht.
 */
void freeQueue(node* curr)
{
   if (curr == null) return;
   while (curr->next != null)
   {
      node *nextnode = curr->next;
      free(curr);
      curr = nextnode;
   }
   // jetzt muß noch das letzte gelöscht werden:
   free(curr);
}

Auch das Löschen funktioniert wie bisher, ist aber für eine Queue keine typische Situation.