Memory Allocation

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?)

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?)

Yes, this is the problem, you should be calling malloc(sizeof(struct Node)) .

However, you can make life easier using new and delete, like this

// in push()
Node* temp = new Node;
 
// later, in pop()
delete temp;

And, I just noticed, in pop(), why are you calling malloc() on temp again, then immediately assigning temp to headNode? Don't malloc temp in pop().

You need to understand memory allocation a little more, then you should be able to tackle this problem fine.

sizeof(Node)

Don't repeat the struct keyword everywhere or I will hunt you down and take all the vowels from your keyboard.

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.

Will node solve your issue but FYI, the correct solution in this case is quite simple:

template<typename T>
T returnDefault(void)
{
    return T();
}

This will return a specified default value for all types (int = 0, T* = nullptr, custom type = default-ctor, ...), so just replace return NULL by return T() and you should be fine in this regard.

sizeof(Node)

Don't repeat the struct keyword everywhere or I will hunt you down and take all the vowels from your keyboard.

lol

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.

Will node solve your issue but FYI, the correct solution in this case is quite simple:

template<typename T>
T returnDefault(void)
{
    return T();
}

This will return a specified default value for all types (int = 0, T* = nullptr, custom type = default-ctor, ...), so just replace return NULL by return T() and you should be fine in this regard.

Thank you, I never learned this

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?)

Yes, this is the problem, you should be calling malloc(sizeof(struct Node)) .

However, you can make life easier using new and delete, like this

// in push()
Node* temp = new Node;
 
// later, in pop()
delete temp;

And, I just noticed, in pop(), why are you calling malloc() on temp again, then immediately assigning temp to headNode? Don't malloc temp in pop().

You need to understand memory allocation a little more, then you should be able to tackle this problem fine.

Yeah I def needed to learn about memory allocation more haha I looked up some tutorials and watched some video explanations and I think I am understanding it better now.

PS - Thank you to everyone that helped me out, I got it working now!

malloc works well with the term pod which is short for plain old data.

Here malloc reserve some amount of space and return it to you as a (void*). Why void* because malloc is from the days of c not c++. In those days we didn't have templates and casting was need to convert void* to something understandable. I see that you are mixing up c++ and c while it is possible, I would advise you to use the newer c++ concept instead of c, the reason is it makes coding easier to understand and work with.

The only time malloc should really be used in C++ is if you're writing a specialized allocator (like overloading new or something), lol. Even 'new' should be avoided in application code, but I think OP is still learning the bare basics, so 'new' is probably okay for now.