Hello,

So I am editing a project I had where I was creating a queue. In my pop() method I am having an issue and I am not sure why. I am trying to free the memory of the Node I am popping from the queue and also returning the data from that Node to the user before it is deleted. When I comment out the free() method in the pop() method it works and when I uncomment the free() call I get heap memory crashes. Can anyone please help me see what I am doing wrong?

Queue.inl

template <typename T>
T Queue<T>::pop()
{
	if (isEmpty())
	{
		std::cout << "pop() was used, but the Queue is empty.\n\n";

		return NULL;
	}
	else
	{
		Node * temp = headNode;

		T removedItem = temp->data;

		headNode = headNode->nextNode;

		std::cout << "pop() was used and " << temp->data << " was removed from the Queue.\n\n";

		free(temp);

		size--;

		return removedItem;
	}
}

Queue.h

#pragma once

template <class T>
class Queue
{
	public:
		Queue();
		Queue(T newItem);
		void push(T newItem);
		void pop_all();
		T pop();
		T peek();
		bool isEmpty();
		int getSize();
	private:
		struct Node
		{
			T data;
			Node * nextNode;
		};

		Node LinkedList;
		Node * headNode; // front of the queue
		Node * tailNode; // End of the Queue
		int size;
};

#include "Queue.inl"

Is IsEmpty() working correctly?

Are objects created with malloc?

is headNode a valid value?

Are the Nodes initialized to sensible values?

Check all everything is initialised to a sensible value (probably NULL).

T is not necessarily a pointer. T* is a pointer.

Is IsEmpty() working correctly?

Are objects created with malloc?

is headNode a valid value?

Are the Nodes initialized to sensible values?

Check all everything is initialised to a sensible value (probably NULL).

yes isEmpty() is working correctly and yes the objects are created using malloc.

T is not necessarily a pointer. T* is a pointer.

which portion were you referring to?

return NULL;

Should tailNode be updated in pop()? What happens if tailnode is pointing at headNode?

Should tailNode be updated in pop()? What happens if tailnode is pointing at headNode?

thanks, I totally forgot about that condition. No luck solving the heap corruption though :unsure:

return NULL;

You're right, that is an issue. However, I dont think thats it will solve this particular issue with my program though because when I call pop(), I make sure the function is not empty so return NULL isnt ever called. I even tried changing return NULL to return -1 and the same issue happened. Everything is working properly with no crash up until I add the free(temp) statement in the pop() method. If I uncomment that statement, it works perfect besides the fact that the memory leak isnt solved when popping.

Main.cpp

//////////////////////////////////
//                              //
//   Data Structures - Queues   //
//   ------------------------   //
//                              //
//   Creating a queue system    //
//   using linked lists and     //
//   C++ (FIFO)                 //
//                              //
//////////////////////////////////

#include "LibIncludes.h"

void displayQueueSize(Queue<int> queue)
{
	std::cout << "Queue Size = " << queue.getSize() << "\n\n";
}

int main()
{
	Queue<int> myQueue;

	myQueue.push(2);
	myQueue.push(3);
	myQueue.push(5);

	displayQueueSize(myQueue);

	int removed = myQueue.pop();

	if (removed < 0)
		std::cout << "\n*** pop() was unsuccessful. Queue is empty.\n";
	else
		std::cout << "\n*** pop() was successful. " << removed << " was removed.\n";

	system("PAUSE");

	return 0;
}

Queue.h

#pragma once

template <class T>
class Queue
{
	public:
		Queue();
		Queue(T newItem);
		void push(T newItem);
		void pop_all();
		T pop();
		T peek();
		bool isEmpty();
		int getSize();
	private:
		struct Node
		{
			T data;
			Node * nextNode;
		};

		Node LinkedList;
		Node * headNode; // front of the queue
		Node * tailNode; // End of the Queue
		int size;
};

#include "Queue.inl"

Queue.inl

#include "LibIncludes.h"

template <typename T>
Queue<T>::Queue()
{
	headNode = nullptr;
	tailNode = nullptr;

	size = 0;

	std::cout << "*** A new empty Queue was created ***\n\n";
}

///////////////////////////////////////////////////////////////////////////////

template <typename T>
Queue<T>::Queue(T newItem)
{
	Node * temp = (struct Node *)malloc(sizeof(struct Node *));

	temp->data = newItem;
	temp->nextNode = nullptr;

	headNode = temp;
	tailNode = temp;

	size = 1;

	std::cout << "*** A new Queue with starting item " << headNode->data << " was created ***\n\n";
}

///////////////////////////////////////////////////////////////////////////////

template <typename T>
bool Queue<T>::isEmpty()
{
	if (headNode == NULL)
		return true;
	else
		return false;
}

///////////////////////////////////////////////////////////////////////////////

template <typename T>
T Queue<T>::peek()
{
	if (isEmpty())
		return NULL;
	else
		return headNode->data;
}

///////////////////////////////////////////////////////////////////////////////

template <typename T>
void Queue<T>::pop_all()
{
	if (isEmpty())
		std::cout << "pop_all() was used, but the Queue is already empty.\n\n";
	else
	{
		std::cout << "pop_all() was used and destroyed the Queue.\n\n";

		Node temp = headNode;

		for (int i = 0; i < size; i++)
		{
			pop();
		}

		headNode = nullptr;
		tailNode = nullptr;

		size = 0;
	}
}

///////////////////////////////////////////////////////////////////////////////

template <typename T>
void Queue<T>::push(T newItem)
{
	Node * temp = (struct Node *)malloc(sizeof(struct Node *));

	temp->data = newItem;
	temp->nextNode = nullptr;

	if (isEmpty())
	{
		headNode = temp;
		tailNode = temp;
	}
	else
	{
		tailNode->nextNode = temp;
		tailNode = temp;
	}

	size++;
	std::cout << "push() was called and " << newItem << " was added to the Queue.\n\n";
}

///////////////////////////////////////////////////////////////////////////////

template <typename T>
T Queue<T>::pop()
{
	if (isEmpty())
	{
		std::cout << "pop() was used, but the Queue is empty.\n\n";

		return -1;
	}
	else
	{
		Node * temp = (struct Node *)malloc(sizeof(struct Node *));
		
		temp = headNode;

		T removedItem = headNode->data;

		headNode = headNode->nextNode;

		std::cout << "pop() was used and " << temp->data << " was removed from the Queue.\n";

		free(temp);
		temp = nullptr;

		size--;

		if (size == 0)
		{
			free(tailNode);
			tailNode = nullptr;
		}

		return removedItem;
	}
}

///////////////////////////////////////////////////////////////////////////////

template <typename T>
int Queue<T>::getSize()
{
	return size;
}

Why are you allocating sizeof(struct Node *) bytes?

Also, if you want to make sure your queue class works, try compiling a queue of something like std::string instead of int, and fix all of the compilation errors you'll get from that.

Your class should have a destructor, a copy constructor and assignment operator.

I'd recommend not having both a head and tail pointer to start, it should be simpler to implement a queue as a singly linked list (in reverse, push creates a new "head"). It complicates things to maintain both correctly.

Consider using new/delete for the nodes, at least to start. Complex classes like std::string will break unless you account for how malloc() separates allocation from C++ object life cycle management.

sizeof(struct Node *) <- isn't this wrong??

for a node you should allocate sizeof(struct node) otherwise you allocate only pointer size space (4 or 8 bytes?)