//Eine Queue ist intern eine doppelt verkettete Liste, jedes Element repräsentiert dabei eine Instanz der Klasse "MyNode"
template <class T>
class MyQueue 
{
    private:
        MyNode<T>* head; //Der Head unserer Queue, hier beginnt sie
        MyNode<T>* tail; //Der Tail unserer Queue, hier endet sie
 
    public:
        MyQueue();
        ~MyQueue();
 
        void push(T value); //Mit der Push-Methode wird ein Element am Ende der Queue eingefügt (enqueue)
        void pop(); //Mit der Pop-Methode wird ein Element am Anfang der Queue gelöscht (dequeue)
 
        MyNode<T>* getHead(); //Mit dieser Methode bekommt man den Head geliefert
        MyNode<T>* getTail(); //Mit dieser Methode bekommt man den Tail geliefert
 
        bool isEmpty(); //Diese Methode checkt, ob unsere Queue leer ist und liefert dann einen Boolean Wert zurück 
        void deleteList(); //Diese Methode löscht unsere ganze Queue
 
        template <class T>
        friend ostream& operator << (ostream& os, const MyQueue<T>& queue); 
};
 
template <class T>
MyQueue<T>::MyQueue()   //Im Konstruktor werden nur der Head bzw. der Tail auf NULL gesetzt
{
    this->head = this->tail = NULL;
}
 
template <class T>
MyQueue<T>::~MyQueue() 
{//Im Destruktor wird einfach der Speicher den die einzelnen Elemente der Queue beanspruchen mithilfe der Methode "deleteList()" freigegeben
    this->deleteList();
}
 
template <class T>
void MyQueue<T>::deleteList() 
{//In dieser Methode wird die Liste vom ersten bis zum letzten Element durchlaufen, dabei wird immer das erste Element gelöscht
    MyNode<T>* help = this->head;
 
    while(!this->isEmpty()) //Solange "help" nicht NULL ist, können haben wir ein Element welches wir löschen können
    {
        this->pop();
    }
 
    this->head = this->tail = NULL; 
}//Zu guter Letzt setzten wir "head" und "tail" auf NULL um problemlos mit der Queue weiterarbeiten zu können
 
template <class T>
void MyQueue<T>::push(T value) //Dem Push wird der Wert übergeben, den das neue Queue-Element haben soll
{
    MyNode<T>* help = new MyNode<T>(value); //Mit dem übergebenen Wert wird ein neues Element angelegt
 
    if(this->isEmpty())  //Hier wird überprüft, ob die Queue bereits ein Element beinhaltet
        this->head = help; //Wäre dies nicht der Fall, so wird der Head unserer Queue auf das neue Element gesetzt
 
    else
        this->tail->setNext(help);  //Beinhaltet unsere Queue mind. 1 Element so wird das neue Element hinten drangehängt
 
    help->setPrev(this->tail); //Zum Schluss noch die Pointer des neuen (letzten) Elements auf das vorletzte Element zeigen lassen
    this->tail = help;//Das neue Element ist nun das Letzte, deshalb unseren Tail (zeigt immer auf letztes Element) auf das neue Element zeigen lassen
}
 
template <class T>
void MyQueue<T>::pop() //Das Pop enfernt das 1. Element der Queue
{
    if(!this->isEmpty())      //Es wird überprüft ob sich ein Element in der Queue befindet
    {
        MyNode<T>* help = this->head;//Falls wir ein Element haben, setzten wir unseren Hilfszeiger help auf dieses und unseren "head" auf das Nächste
        this->head = this->head->getNext(); //Wenn kein Element mehr da ist, wird "head" AUTOMATISCH auf NULL gesetzt
 
        if(this->head != NULL)
            this->head->setPrev(NULL);  //Der Zeiger zum vorderen Element wird gekappt
 
        else
            this->tail = NULL; //Wenn "head" NULL ist, wird "tail" auch auf NULL gesetzt
 
        help->setNext(NULL); //Nur noch "help" zeigt auf das zu löschende Element"
        delete help; //Der Speicher den das Element beansprucht wird freigegeben
    }
}
 
template <class T>
MyNode<T>* MyQueue<T>::getHead()
{
    return this->head; //Diese Methode liefert einfach den Beginn der Queue (head) zurück
}
 
template <class T>
MyNode<T>* MyQueue<T>::getTail()
{
    return this->tail; //Diese Methode liefert einfach das Ende der Queue (tail) zurück
}
 
template <class T>
bool MyQueue<T>::isEmpty() //Diese Methode checkt, ob die Queue leer ist
{                          //Ist sie leer, wird "true" zurückgeliefert, enthält sie mindestens ein Element, wird "false" geliefert
    bool ret = false;
 
    if(this->head == NULL && this->tail == NULL)
        ret = true;
 
    return ret;
}
 
template <class T>
ostream& operator << (ostream& os, const MyQueue<T>& queue) 
{//Mit dem überladenen Output-Operator kann man unsere Queue ganz einfach ausgegeben werden
    MyNode<T>* help = queue.head;
 
    while(help != NULL) 
    {//Wir durchlaufen einfach die Queue vom ersten bis zum letzten Element und geben dabei den Wert jedes einzelnen Elements aus
        cout << help->getValue() << " ";
        help = help->getNext();
    }
 
    return os;
}

template <class T>
class MyNode //Eine Node ist ein Element der Queue
{
    private:
        MyNode<T>* next;  //Pointer der auf das folgende Element zeigt
        MyNode<T>* prev;  //Pointer der auf das vorhergehende Element zeigt
        T value;
 
    public:
        MyNode(T value);
        void setValue(T value); //Methode um explizit den Wert eines Elements neu zu setzten
        T getValue();       //Liefert den Wert des aktuellen Elements
 
        MyNode<T>* getNext(); //Liefert das nächste Element
        MyNode<T>* getPrev(); //Liefert das vorhergehende Element
 
        void setNext(MyNode<T>* node); //Biegt den Zeiger, der auf das nächste Element zeigt, auf das übergebene Element um
        void setPrev(MyNode<T>* node); //Biegt den Zeiger, der auf das vorhergehende Element zeigt, auf das übergebene Element um
};
 
template <class T>
MyNode<T>::MyNode(T value) //Im Konstruktor wird dem Element ein Wert (value) zugewiesen, 
                           //"next" und "prev" werden dabei auf NULL gesetzt
{
    this->next = NULL;
    this->prev = NULL;
    this->value = value;
}
 
template <class T>
void MyNode<T>::setValue(T value)
{
    this->value = value; //Methode um den Wert des Elements neu zu setzen
}
 
template <class T>
T MyNode<T>::getValue()
{
    return this->value; //Liefert den Wert des Elements
}
 
template <class T>
MyNode<T>* MyNode<T>::getNext()
{
    return this->next; //Liefert das Element auf das der "next"-Pointer verweist
}
 
template <class T>
MyNode<T>* MyNode<T>::getPrev()
{
    return this->prev; //Liefert das Element auf das der "prev"-Pointer verweist
}
 
template <class T>
void MyNode<T>::setNext(MyNode<T>* node)
{
    this->next = node; //Diese Methode setzt den "next"-Pointer auf ein neues Element
}                      
 
template <class T>
void MyNode<T>::setPrev(MyNode<T>* node)
{
    this->prev = node; //Diese Methode setzt den "prev"-Pointer auf ein neues Element
}