Advanced   Java   Services

Stack

Ein Stack ist eine Reihe von Elementen, die nach dem LIFO-Prinzip (Last In First Out) geordnet ist. Einen Stack kann man sich etwa vorstellen wie einen Bücherstapel. Man legt die Bücher übereinander. Das zuletzt abgelegte Buch wird als erstes wieder entnommen usw.

Das Aufnehmen eines Elements findet also ebenso wie das Entnehmen immer am gleichen Ende statt, nämlich an der Spitze des Stapels. Hier verändert sich der Kopf der Liste also sowohl beim Aufnehmen als auch beim Entnehmen. In diesem Zusammenhang wird das Aufnehmen eines Elements gerne push oder put genannt, das Entnehmen meist pop oder pull seltener auch get.

Neu ist lediglich die Funktion push. Die Funktion pop ist die Funktion poll von Queue.

Einfügen an der Spitze.

/*
 * Auf den Stapel legen heißt einen neuen Kopf anlegen
 * Ist *pHead == NULL, so wird ein neuer Stack angelegt
 */
int push(node** pHead, int data)   // drauflegen
{
   if ( pHead == NULL ) return 0;

   node *newhead = malloc(sizeof(node));
   if (newhead == NULL) return 0;  // kein Speicher

   newhead->data = data;
   newhead->next = *pHead;
   *pHead = newhead;
   return 1; // OK
}

/*
 * Oberstes vom Stapel nehmen
 * Kopf wegnehmen, neuen Kopf setzen
 */
node* pop(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

/*
 * Headelement eines Stack 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 freeStack 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 freeStack(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 einen Stack keine typische Situation.