рекурсия — двойное освобождение или повреждение (fasttop) при использовании рекурсивного метода в переполнении стека

Я реализовал класс Stack и попытался использовать этот класс для решения Ханойской проблемы. Вот мой код:

template<class Datatype>
class Node
{
public:
Node()
{
next = NULL;
prev = NULL;
}
Node* getNext()
{
return next;
}
Node* getPrev()
{
return prev;
}
Datatype* getData()
{
return &data;
}
void changeNext()
{
next = NULL;
}
void changeNext(Node& nextNode)
{
next = &nextNode;
}
void changePrev()
{
prev = NULL;
}
void changePrev(Node& prevNode)
{
prev = &prevNode;
}
Node* addNext(Node &);
Node* addPrev(Node &);
void nodeDel();
void addData(Datatype &);
private:
Node* next;
Node* prev;
Datatype data;
};

template<class Datatype>
class Stack
{
public:
Stack() : head( NULL )
{

}
virtual ~Stack()
{
Datatype temp;
while (pop(temp));
cout << "Stack released all spaces" << endl;
}
public:
virtual int push(Datatype &);
virtual int pop(Datatype &);
virtual Datatype* peek();
protected:
Node<Datatype> *head;
};
template <class Datatype>
int Stack<Datatype>::push(Datatype &new_data)
{
Node<Datatype> *pt_node = new Node<Datatype>;
if (pt_node == NULL)
return -1;

pt_node -> addData(new_data);

if (head == NULL)
head = pt_node;
else
{
pt_node -> addPrev(*head);
head = pt_node;
}

//cout << *(head -> getData()) << endl;

return 0;
}

template <class Datatype>
int Stack<Datatype>::pop(Datatype &pop_data)
{
if (head == NULL)
return 0;

pop_data = *(head -> getData());

if (head -> getNext() == NULL)
{
delete head;
head = NULL;
}
else
{
Node<Datatype>* temp = head;
head = head -> getNext();
delete temp;
}

return 1;
}

Выше объявить Stack class а также реализовать pop() а также push() функции.
Теперь я объявляю свой класс в Ханое и реализую функции.

class Hanoi
{
public:
Hanoi(int num) : a_tower(), b_tower(), c_tower()
{
deep = num;
int i;
for (i = num; i != 0; i --)
a_tower.push(i);
}
public:
void workdone(int, Stack<int>&, Stack<int>&, Stack<int>&);
void showret();
public:
Stack<int> a_tower;
Stack<int> b_tower;
Stack<int> c_tower;
int deep;
};

void Hanoi::workdone(int deep_num, Stack<int>& A, Stack<int>& B, Stack<int>& C)
{
int temp;
if (deep_num == 1)
{
A.pop(temp);
C.push(temp);
}
else
{
Hanoi::workdone(deep_num - 1, A, C, B);
A.pop(temp);
C.push(temp);
Hanoi::workdone(deep_num - 1, B, A, C);
}
}

void Hanoi::showret()
{
int temp;
while (c_tower.pop(temp) != 0)
cout << temp << endl;
}

Вот мой тестовый код:

int main()
{
Hanoi test(STACK_DEEP);
test.workdone(STACK_DEEP, test.a_tower, test.b_tower, test.c_tower);
test.showret();

return 0;
}

Выход:

*** glibc detected *** ./3_4: double free or corruption (fasttop): 0x090c0038 ***

Я думаю, что эта проблема возникает, когда ~ Ханой звонят, но я действительно не знаю, почему это произойдет.

Здесь я публикую весь код, который может получить такой результат:
my_node.h

#include <iostream>

using namespace std;

template<class Datatype>
class Node
{
public:
Node()
{
next = NULL;
prev = NULL;
}
Node* getNext()
{
return next;
}
Node* getPrev()
{
return prev;
}
Datatype* getData()
{
return &data;
}
void changeNext()
{
next = NULL;
}
void changeNext(Node& nextNode)
{
next = &nextNode;
}
void changePrev()
{
prev = NULL;
}
void changePrev(Node& prevNode)
{
prev = &prevNode;
}
Node* addNext(Node &);
Node* addPrev(Node &);
void nodeDel();
void addData(Datatype &);
private:
Node* next;
Node* prev;
Datatype data;
};

template<class Datatype>
class Stack
{
public:
Stack() : head( NULL )
{

}
virtual ~Stack()
{
Datatype temp;
while (pop(temp));
cout << "Stack released all spaces" << endl;
}
public:
virtual int push(Datatype &);
virtual int pop(Datatype &);
virtual Datatype* peek();
protected:
Node<Datatype> *head;
};

template <class Datatype>
Node<Datatype>* Node<Datatype>::addNext(Node<Datatype>& exi_node)
{
if (exi_node.getNext() == NULL)
{
changePrev(exi_node);
exi_node.changeNext(*this);
}
else
{
Node* next = exi_node.getNext();
changePrev(exi_node);
changeNext(*next);
exi_node.changeNext(*this);
next -> changePrev(*this);
}
return &exi_node;
}

template <class Datatype>
Node<Datatype>* Node<Datatype>::addPrev(Node<Datatype>& exi_node)
{
if (exi_node.getPrev() == NULL)
{
changeNext(exi_node);
exi_node.changePrev(*this);
}
else
{
Node* prev = exi_node.getPrev();
changePrev(*prev);
changeNext(exi_node);
exi_node.changePrev(*this);
prev -> changeNext(*this);
}
return &exi_node;
}

template<class Datatype>
void Node<Datatype>::nodeDel()
{
if (prev == NULL && next == NULL)
;
else if (prev == NULL)
{
Node* next = getNext();
next -> changePrev();
}
else if (next == NULL)
{
Node* prev = getPrev();
prev -> changeNext();
}
else
{
Node* next = getNext();
Node* prev = getPrev();
next -> changePrev(*prev);
prev -> changeNext(*next);
}
delete this;
return;
}

template <class Datatype>
void Node<Datatype>::addData(Datatype &new_data)
{
data = new_data;
}

template <class Datatype>
int Stack<Datatype>::push(Datatype &new_data)
{
Node<Datatype> *pt_node = new Node<Datatype>;
if (pt_node == NULL)
return -1;

pt_node -> addData(new_data);

if (head == NULL)
head = pt_node;
else
{
pt_node -> addPrev(*head);
head = pt_node;
}

//cout << *(head -> getData()) << endl;

return 0;
}

template <class Datatype>
int Stack<Datatype>::pop(Datatype &pop_data)
{
if (head == NULL)
return 0;

pop_data = *(head -> getData());

if (head -> getNext() == NULL)
{
delete head;
head = NULL;
}
else
{
Node<Datatype>* temp = head;
head = head -> getNext();
delete temp;
}

return 1;
}

template <class Datatype>
Datatype* Stack<Datatype>::peek()
{
if (head == NULL)
return NULL;
return (this->head)->getData();
}

3_4.h

#include <iostream>
#include "my_node.h"
using namespace std;

class Hanoi
{
public:
Hanoi(int num) : a_tower(), b_tower(), c_tower()
{
deep = num;
int i;
for (i = num; i != 0; i --)
a_tower.push(i);
}
public:
void workdone(int, Stack<int>&, Stack<int>&, Stack<int>&);
void showret();
public:
Stack<int> a_tower;
Stack<int> b_tower;
Stack<int> c_tower;
int deep;
};

void Hanoi::workdone(int deep_num, Stack<int>& A, Stack<int>& B, Stack<int>& C)
{
int temp;
if (deep_num == 1)
{
A.pop(temp);
C.push(temp);
}
else
{
Hanoi::workdone(deep_num - 1, A, C, B);
A.pop(temp);
C.push(temp);
Hanoi::workdone(deep_num - 1, B, A, C);
}
}

void Hanoi::showret()
{
int temp;
while (c_tower.pop(temp) != 0)
cout << temp << endl;
}

3_4.cpp

#include <iostream>
#include "3_4.h"
using namespace std;

#define STACK_DEEP 4

int main()
{
Hanoi test(STACK_DEEP);
test.workdone(STACK_DEEP, test.a_tower, test.b_tower, test.c_tower);
test.showret();

return 0;
}

Команда, которую я использую:

g++ -Wall 3_4.cpp -o 3_4