3. Template-Queue funktioniert nicht richtig

Template-Queue funktioniert nicht richtig

  • W

    Hi,
    ich hab ein Template geschrieben was wie eine Queue funktionieren soll.
    Doch irgendiwe stimmt das mit den Zeigern noch nicht so richtig.
    Das Queue hängt die Elemente nicht ans ende der Schlange sonder an Anfang 😡
    Jemand ne idee??

    #include <iostream>

using namespace std;

#ifndef _QUEUE_H
#define _QUEUE_H

template <class T>
class Queue
{
public:
	Queue(): counter(0), topp (0){}		//Konstruktor
	~Queue(){}				//Destruktor

//Funktionsprototypen

	void deque();		//löschen des ersten Elements
	bool enque(const T&);	//einfügen eines Elements ans Ende

	T& first()const;		//Zugriff auf das erste Element
	bool isEmpty()const;		//Test ob Queue leer ist

private:
			class qNode
				{
				public:
				T data;
				qNode *next_element;
				};	

			qNode *topp;		//Zeiger auf erstes Element
			int counter;	//zählt wie viel elemente in Queue

};

//Funktionen

//prüft ob Queue leer ist, 0 Queue ist nicht leer und 1 Queue ist leer
template <class T> bool Queue<T>::isEmpty()const
	{
	if(counter == 0)
	return true;
	else
	return false;
	}	

//fügt Element am Ende an
template <class T> bool Queue<T>::enque(const T& einzufuegendes_element)
{
	qNode *node = new qNode;
	node->data = einzufuegendes_element;
	node->next_element = topp;
	topp = node;
	++counter;
	return true;
}

//löscht erstes element
template <class T> void Queue<T>::deque()
{
	qNode *old_element = topp;
	topp = topp->next_element;
	delete old_element;
	--counter;
}

//gibt erstes element zurück
template <class T> T& Queue<T>::first()const
{
	return topp->data;
}

#endif

int main()
{
	Queue<int> intQueue;
	cout << "Queue leer? 0->nein....1->ja    " << intQueue.isEmpty() << endl;
	for(int index = 0; index <= 5; index++)
	{
		if(intQueue.enque(index))
		cout << index << " " << "Element auf Queue abgelegt" << endl;
		else
		cout << "Es konnte nichts abgelegt werden !" << endl;
	}
	cout << "Queue leer? 0->nein....1->ja    " << intQueue.isEmpty() << endl;
	cout << intQueue.first();

}

    Gruß steve

    0
  • A

    > Das Queue hängt die Elemente nicht ans ende der Schlange sonder an Anfang

    Ist ja auch logisch. So ist der Prozess:

    1. Aufruf von ennode

    qNode *node = new qNode; // neuer, 1. Node
    node->data = einzufuegendes_element; // Node bekommt Daten
    node->next_element = topp; // node zeigt auf 0
    topp = node; // Anfang zeigt auf den Node
    ++counter;
    return true;

    2. Aufruf:

    qNode *node = new qNode; // neuer, 2. node
    node->data = einzufuegendes_element; // daten einfügen
    node->next_element = topp; // 2. node zeigt auf den 1. node
    topp = node; // der anfang ist der 2. node, (FIFO-Prinzip)
    ++counter;
    return true;

    Konzeptvorschlag: Bau die Klassen um. Erstelle ein Interface (Queue), ein Anfangsknoten, der implizit erstellt wird und der erstellt automatisch einen Endknoten, der einfach nur die Nodes alloziiert. Die Nodes entscheiden dann, ob sie selber einen neuen Node erzeugen und den an ihren Vorgänger zurückgeben oder dass sie das erzeugen dem Nachfolger überlassen, bis spätestens Endnode eh alles alloziiert.
    Ein Beispiel meine Doppelt-Verketteten Liste (für dein Beispiel wäre das qNode):

    #ifndef DEFNODE_HPP
#define DEFNODE_HPP

template <class T>
class DefNode : public Node<T> {

private:
	Node<T> *next;
	Node<T> *prev;
	T *data;
	DefNode(const DefNode<T>&);

public:
	DefNode() { }
	DefNode(Node<T>*, Node<T>*, T*);
	~DefNode();
	Node<T>* Append(T*, Node<T>*);
	void Read() const;

	DefNode<T> operator =(DefNode<T> &dn) {
		if(this == &dn) return *this;
		delete next;
		next = dn.next;
		prev = dn.prev;
		data = dn.data;
		return *this;
	}

};

template <class T>
DefNode<T>::DefNode(Node<T> *n, Node<T> *p, T *d)
	: next(n), prev(p), data(d)
{
}

template <class T>
DefNode<T>::DefNode(const DefNode<T> &dn) {
	next = dn.next;
	prev = dn.prev;
	data = dn.data;
}

template <class T>
DefNode<T>::~DefNode() {
	delete data;
	delete next;
}

template <class T>
Node<T>* DefNode<T>::Append(T *data, Node<T> *p) {
#define FIFO3
#ifdef FIFO
	DefNode<T> *newNode = new DefNode<T>(this, p, data);
	prev = newNode;
	return newNode;
#else

	next = next->Append(data, this);
	return this;
#endif
}

template <class T>
void DefNode<T>::Read() const {
	cout << *data << endl;
	next->Read();
}

#endif
    0
  • W

    Mhh jetzt wo du es sagst,stimmt jetzt seh ich es auch.
    Kann ich evtl. die Zeiger irgendwie umbiegen?
    Gruß steve

    0
  • A

    Es gibt sehr viele Möglichkeiten. Entweder du machst eine Struktur wie ich (sehr dynamisch, schönes C++) oder eine Fast-Variante. Überlass es - wie gesagt - qNode, weitere Nodes zu kreieren. Schreibe für qNode folgende Methode enque():

    template <class T>
qNode<T>* qNode<T>::enque(T *data) {
   if(next_element == 0) { // Zeiger auf 0, ich bin der letzte, ich muss neuen Node erstellen
      qNode<T> *newNode = new qNode<T>; // newNode->next_element zeigt implizit auf 0, wird letzter
      newNode->data = data; // fülle den letzten
      return newNode; // Adresse zurückgeben vom letzten
   }
   else {
      next_element = next_element->enque(data); // lass das den nächsten Node machen, gib mir nur die Adresse vom ggf. neuen Node (nur, wenn ich vorletzter bin)
      return this; // gib mich selber zurück, ich erstelle keinen neuen Node, Kette bleibt gleich!
   }
}

    Die rekursive Schleife im else muss irgendwann unterbruchen werden, d.h. irgendein qNode muss die Drecksarbeit erledigen, einen neuen qNode zu erstellen, das macht die IF-Abfrage, wenn es kein next mehr gibt, wenn doch, dann überlass es dem nächsten. Wenn der einen next hat, dann überlässt der es wiederrum den nächsten usw. und gibt sich selbst zurück, was dann der Vorgänger als next nimmt, das bleibt logischerweise auch gleich. Wenn jedoch der letzte Node aufgefordert wird, der einen neuen Node zurückgibt, dann wird er eben auch next zugewiesen und der neue Node zeigt implizit auf 0. 😉
    Das Thema ist nicht so einfach, hat bei mir auch eine Weile gedauert, mal dir das am besten mal alles auf, das hilft extrem. 😉

    0
  • W

    hab es mir schon ma aufgemalt werd es nochma neu machen.
    Trotzdem danke.
    Gruß Steve

    0
Anmelden zum Antworten