/* Name	       : extds.h  (externe Datenstrukturen)                    */
/* Autor       : Michael Feist					       */
/* erstellt am : 2.5.98						       */
/* letzte Änd. : 8.6.98						       */
/* Beschreibung: Header-Datei mit den Datenstrukturen 'STACK' (Stapel)
   und 'QUEUE' (Schlange) sowie Operationen auf diesen Datentypen      */
/*-------------------------------------------*/
#include <malloc.h>
#include <stdio.h>
/*-------------------------------------------*/
/* Definition der Struktur eines 'stack'-Elements */
typedef struct _el_stack
{
  struct _el_stack *next; /* Zeiger auf nächstes und vorhergehendes Stackelement */
  struct _el_stack *prev; 
  int data;	/* 'stack'-Inhalt */
} *el_stack;   /* Zeiger auf 'stack'-Element wird 'el_stack' "getauft" */

/* Definition des 'stack'-Kopfes */
typedef struct
{
  el_stack first; /* Zeiger auf erstes bzw. letztes 'stack'-Element */
  el_stack last;
} stack; /* neuer Typ: stack */

typedef stack *p_stack; /* neuer Typ: p_stack (Zeiger auf stack) */

/* Definition der Struktur eines 'queue'-Elements */
typedef struct _el_queue
{
  struct _el_queue *next; /* Zeiger auf nächstes Element der Schlange */
  int data;	/* Inhalt des Schlangenelements */
} *el_queue; /* Zeiger auf solch ein Element heißt el_queue */

/* Deklaration des Schlangenkopfes (analog zu 'stack' */
typedef struct
{
  el_queue first;
  el_queue last;
} queue;

typedef queue *p_queue; /* der zugehörige Zeiger */

/*-------------------------------------------*/
p_stack create_stack ()
/* Funktion: Erstellen eines neuen Stapels   */
/* Übergabe: nichts							 */
/* Rückgabe: Zeiger auf Stapel				 */
{
  p_stack temp;
  temp = (p_stack)malloc (sizeof (stack));
  temp->last=NULL; /* NULL-Zeiger bedeuten: leerer Stapel */
  temp->first=NULL;
  return temp;
}

/*-------------------------------------------*/
void push_stack (p_stack z_stapel, int element)
/* Funktion: ganze Zahl auf Stapel legen     */
/* Übergabe: Zeiger auf Stapelkopf, int-Wert */
/* Rückgabe: nichts           				 */
{
  stack stapel=*z_stapel;
  el_stack temp=(el_stack)malloc(sizeof(struct _el_stack));
  temp->data=element;
  temp->next=NULL;
  temp->prev=stapel.last;
  if (stapel.last!=NULL) stapel.last->next=temp;
  stapel.last=temp;
  if (stapel.first==NULL) stapel.first=temp;
  *z_stapel=stapel;
}
/*-------------------------------------------*/
int empty_stack (p_stack z_stapel)
/* Funktion: Test, ob Stapel leer ist        */
/* Übergabe: Zeiger auf Stapelkopf			 */
/* Rückgabe: bool'scher Ausdruck			 */
{
  stack stapel=*z_stapel;
  if (stapel.first==NULL) return 1;
  return 0;
}
/*-------------------------------------------*/
int pop_stack (p_stack z_stapel)
/* Funktion: oberstes Element vom Stapel zurückgeben   */
/* Übergabe: Zeiger auf Stapelkopf			 */
/* Rückgabe: oberstes Element oder 0 falls Stapel leer */
{
  stack stapel=*z_stapel;
  el_stack zeiger;
  int wert;
  if (empty_stack (z_stapel)) return 0;
  wert=stapel.last->data;
  zeiger=stapel.last->prev;
  free (stapel.last);
  stapel.last=zeiger;
  if (zeiger==NULL) stapel.first=NULL;
  *z_stapel=stapel;
  return wert;
}
/*-------------------------------------------*/
void delete_stack (p_stack z_stapel)
/* Funktion: Stapelkopf sowie alle Elemente löschen und Speicher freigeben */
/* Übergabe: Zeiger auf Stapelkopf           */
/* Rückgabe: nichts           				 */
{
  while (!empty_stack (z_stapel)) pop_stack (z_stapel);
  free (z_stapel);
}
/*-------------------------------------------*/
p_queue create_queue ()
/* Funktion: leere Schlange erzeugen         */
/* Übergabe: nichts							 */
/* Rückgabe: Zeiger auf Schlangenkopf		 */
{
  p_queue temp;
  temp = (p_queue)malloc (sizeof (queue));
  temp->last=NULL;
  temp->first=NULL;
  return temp;
}
/*-------------------------------------------*/
void push_queue (p_queue z_schlange, int element)
/* Funktion: ganze Zahl an Schlangenende anhängen */
/* Übergabe: Zeiger auf Schlangenkopf, int-Wert   */
/* Rückgabe: nichts           				 */
{
  queue schlange=*z_schlange;
  el_queue temp=(el_queue)malloc(sizeof(struct _el_queue));
  temp->data=element;
  temp->next=NULL;
  if (schlange.last!=NULL) schlange.last->next=temp;
  schlange.last=temp;
  if (schlange.first==NULL) schlange.first=temp;
  *z_schlange=schlange;
}
/*-------------------------------------------*/
int empty_queue (p_queue z_schlange)
/* Funktion: Test, ob Schlange leer          */
/* Übergabe: Zeiger auf Schlangenkopf		 */
/* Rückgabe: 1,falls Schlange leer; 0,sonst  */
{
  queue schlange=*z_schlange;
  if (schlange.first==NULL) return 1;
  return 0;
}
/*-------------------------------------------*/
int pop_queue (p_queue z_schlange)
/* Funktion: erstes Element aus Schlange entfernen und zurückgeben */
/* Übergabe: Zeiger auf Schlangenlkopf		 */
/* Rückgabe: erstes Element   				 */
{
  queue schlange=*z_schlange;
  el_queue temp=schlange.first;
  int wert;
  if (empty_queue (z_schlange)) return 0;
  wert=schlange.first->data;
  schlange.first=schlange.first->next;
  if (schlange.first==NULL) schlange.last=NULL;
  *z_schlange=schlange;
  free (temp);
  return wert;
}
/*-------------------------------------------*/
void delete_queue (p_queue schlange)
/* Funktion: Schlange und alle enthaltenen Elemente löschen */
/* Übergabe: Zeiger auf Schlangenkopf		 */
/* Rückgabe: nichts           				 */
{
  while (!empty_queue (schlange)) pop_queue (schlange);
  free (schlange);
}
/*---(C)-1998-Michael-Feist------------------*/