#include<iostream>
using namespace std;

//struct ListenElement
//{
//	int wert; // unser eigentlicher Datentyp
//	ListenElement *next; // Zeiger auf das nächste ListenElement
//	// Zeiger werden mit einem vorangestellten * markiert
//};

struct ListenElement; // dies kündigt dem Compiler an,
// dass es ein struct ListenElement geben wird
// die genaue Definition des structs kommt später

// damit ist jetzt folgendes typedef möglich
typedef ListenElement* ListenPtr;
// definiert uns ListenPtr als Typ eines Zeigers auf ein ListenElement

struct ListenElement
{
	int wert;
	ListenPtr next;
};


// letzte Woche ... (Termin 31.1.2012)
// ListenElement* zahlEinlesenMitListen(void)
//{
//	// liest Zahlen ein und gibt den Zeiger auf das erste Element zurück
//	// (Zahlen sind in der Liste in umgekehrter Reihenfolge der Eingabe)
//  ...
//  return anker;
//}

void ListeMitZahlenAusgeben(ListenElement *anker)
{
	// Idee: solange Elemente da sind, diese ausgeben, ansonsten jeweils auf das nächste Element
	// in der Liste vorrücken

	//ListenElement *aktElem = anker;
	ListenPtr aktElem = anker;
	while (aktElem != NULL)
	{
		cout << "Naechste Element ist die " << aktElem->wert << endl;
		// nun noch auf das nächste Element vorrücken
		aktElem = aktElem->next;
	}
	// alternative: rekursive Lösung
	// if (aktElem != NULL)
	// {
	//   cout << "Nächste Element ist die " << aktElem->wert << endl;
	// }
	// else
	// {
	//   ListeMitZahlenAusgeben(aktElement->next);
	// }
	// da aktElement nie was zugewiesen wird, könnte man bei der rekursiven Variante
	// auch die Variable anker direkt verwenden
}

void fuegeZahlAmAnfangDerListeEin(const int zahl, ListenPtr & anker)
// selbst ausprobieren, ob es ohne das typedef ListenElement* ListenPtr
// dann ListenElement * & anker oder ListenElement & * anker heißen müsste
{
	// fügt zahl als neues erstes Element der Liste ein, auf die anker zeigt
	// anker wird entsprechend verändert
	//
	// Idee: erzeuge neues ListenElement und füge dies als neues Element
	// mit der als Parameter übergebenen Zahl am Anfang der Liste, auf
	// die anker zeigt, ein
    ListenPtr neu = new ListenElement;
	neu->wert = zahl;
	neu->next = anker;
	anker = neu;
}

void fuegeZahlSortiertInDieListeEin(const int zahl, ListenPtr & anker)
// für die Fälle, dass die Liste vorher leer war oder zahl das neue kleinste
// Element ist, muss anker veränderbar sein
// Folgende Fälle sind zu untersuchen:
// - ist die Liste leer?
// - ist zahl das neue kleinste Element?
// - sonstiges
// wir gehen hier der Einfachheit halber davon aus, dass alle Element verschieden sind
// selbst überlegen, wie man das Einfügen gleicher Elemente verhindert
{
	if (anker == NULL)
	{ 
		// neues erstes Element erzeugen, Variable anker kann direkt verändert werden
		anker = new ListenElement; // erzeuge neues ListenElement
		anker->wert = zahl; // zahl in das ListenElement eintragen
		anker->next = NULL; // Element ist das einzige bis dahin
	}
	else if (zahl < anker->wert) // ist zahl das neue kleinste Element
	{
		// so ähnlich wie bei anker == NULL, aber bisherige Liste nicht verloren gehen darf
		ListenPtr neu = new ListenElement;
		neu->wert = zahl;
		neu->next = anker; // analog zum Einfügen am Anfang einer Liste
		anker = neu;
	}
	else
	{   // neues Element ist nicht zu Beginn der Liste, wir dürfen anker also nicht verändern
		// wir benötigen einen Pointer zum Durchlaufen der Liste
		ListenPtr current = anker->next; // das Element bei anker ist wie oben
		// festgestellt in jedem Fall kleiner als zahl, Test kann also bei der zweiten
		// Zahl beginnen
		//
		// while (current->wert < zahl) läuft ein Element zu weit ...
		// 1. Lösungsmöglichkeit: merke mit einer weiteren Variablen die Adresse,
		// auf die current zeigt, im jeweils vorherigen Schleifendurchlauf
		ListenPtr prev = anker;
		while (current!=NULL && current->wert < zahl) // Weiterlaufen, bis zum letzten ListenElement, das kleiner als zahl ist
		// aufpassen: dies funktioniert nur, weil der Compiler für den Fall,
		// dass current == NULL ist, den Ausdruck current->wert < zahl nicht mehr auswertet
		// und so also auf current->wert nicht zugreift!
		// die 4 Zeilen für das Erzeugen und "Einfügen" des neuen Elements funktionieren
		// gleichermaßen für die Fälle, dass ein Element eingefügt oder am Ende als neues
		// größtes Element angefügt wird (selbst nochmal überlegen)
		{
			prev = current;
			current = current->next;
		}
		// cout << "prev zeigt auf die " << prev->wert << endl;
		// prev zeigt auf das Element, hinter dem die neue zahl einzufügen ist
		// current zeigt auf das Element, was hinter der neuen zahl stehen soll
		ListenPtr neu = new ListenElement; // neues Element erzeugen, um dort zahl einzufügen
		neu->wert = zahl;
		neu->next = current;
		prev->next = neu;
	}
	// es gibt noch mindestens 2 sinnvolle weitere Möglichkeiten (und zwei Dutzend kompliziertere)
	// Aufgabe: finden Sie mindestens eine weitere und implementieren Sie diese
	// Ideen dazu: ersetze current durch prev->next
	// weitere Idee: sortiertesEinfügen(zahl,anker) = neues erstes Element oder sortiertesEinfügen(zahl,anker->next)
}


void fuegeZahlSortiertInDieListeEin_rekursiv(const int zahl, ListenPtr & anker)
// Prosa: selbst ausfüllen
{
	if (anker == NULL || zahl < anker->wert) // zahl ist das neue kleinste Element
	{
		ListenPtr neu = new ListenElement;
		neu->wert = zahl;
		neu->next = anker;
		anker = neu;
	}
	else
	{
		fuegeZahlSortiertInDieListeEin_rekursiv(zahl, anker->next);
	}
}

struct Queue;
typedef Queue* PtrQueue;
struct Queue {
	int wert;
	PtrQueue first;
};

void enqueue(const int zahl, PtrQueue & q)
{
	// zwei Fälle zum Hinten-Einfügen:
	// erste Fall: Queue war vorher leer, dann neu erzeugen, sonst hinten einfügen
	if (q == NULL)
	{
		q = new Queue;
		q->wert = zahl;
		q->first = q;
	}
	else
	{
		PtrQueue neuq = new Queue; // soll hinten angefügt werden
		neuq->wert = zahl;
		neuq->first = q->first; // erstes Element der Queue bleibt wie gehabt
		q->first = neuq; // neue Element kommt hinter das bisher letzte Element
		q = neuq; // neue Element ist nun das letzte der Queue
	}
}

int dequeue(PtrQueue & q)
{	// zu beachten: q muss als Referenz übergeben werden für den Fall,
	// dass wir das letzte (und einzige) Element entfernen
	int erg = q->first->wert; // Wert, der im ersten Element eingetragen ist (q->first wäre das erste Element)
	// Fall, dass letztes Element gelöscht wird, abfangen
	if (q == q->first) // das hintere und erste Element der Queue sind identisch (aus speichertechnischer Sicht)
	{
		// Speicher freigeben:
		delete q;
		q = NULL;
	}
	else
	{
		// Speicher freigeben
		PtrQueue toBeDeleted = q->first;
		q->first = q->first->first;
		delete toBeDeleted;
	}
	return erg;
}

bool isEmpty(PtrQueue q)
{
	return q == NULL;
}


int main(void)
{
	//ListenPtr anker = NULL; // WICHTIG: initialieren der Liste nicht vergessen!
    PtrQueue q = NULL;
	int zahl;
	cout << "Gib eine Zahl ein (Abbruch mit 0): ";
	cin >> zahl;
	while (zahl != 0)
	{
		// fuegeZahlAmAnfangDerListeEin(zahl,anker);
		// fuegeZahlSortiertInDieListeEin(zahl,anker);
		// fuegeZahlSortiertInDieListeEin_rekursiv(zahl,anker);
		enqueue(zahl,q);
		cout << "Gib eine Zahl ein (Abbruch mit 0): ";
		cin >> zahl;
	}
    // ListeMitZahlenAusgeben(anker);
	while (!isEmpty(q))
	{
		cout << "Naechster Wert der Queue: " << dequeue(q) << endl; // das dequeue entfernt der Wert gleichzeitig aus der Queue
	}

	return 0;
}