Queue data structure assignment

[rekrap99]

This assignment wants me to create a Queue data structure using a LinkedList data structure we used in class.
Here is the assignment:
1. Implement the Queue data structure using the Linked List data structure.
a. Your queue should be a template class.
b. The queue should have push, pop, and peek functions.
i. Pop and peek functions operate in the same way as in the Stack class.
ii. The push function adds elements to the beginning of a Queue, making it a FILO (First In, Last Out) data structure rather than a FIFO (First In, First Out) data structure like a stack.
1. In order to implement the Queue data structure, you will have to add a prepend function to the Linked List class that inserts elements at the beginning of the list rather than at the end of the list.
c. Add a copy constructor that can produce a copy of the Queue class.
d. Overload the << operator to print out the entire contents of the Queue.
e. Overload the + operator that adds the right queue to beginning of the left queue. For example:

Queue<int> * q1 = new Queue<int>();
Queue<int> * q2 = new Queue<int>();
q1.push(5);
q1.push(6);
q2.push(9);
q2.push(1);
Queue<int> * q3 = (*q1) + (*q2);
cout << q3 << endl;

should produce the following output:

9
1
5
6


While trying to figure this out,I have some questions that would like to be answered.
1. What functions should be replaced by the push pop and peek functions?
2. Does a Queue data structure use the node class or something else?

Here is what I have so far...
Main.cpp
#include <iostream>
#include "Queue.h"

using namespace std;

void main(void)
{
Queue<int> * q1 = new Queue<int>(); //Constructor triggered
Queue<int> * q2 = new Queue<int>(); //Pointer, but no instance

q1.push(5);
q1.push(6);

q2.push(9);
q2.push(1);



Queue<int> * q3 = (*q1)+(*q2); //create a new linkedlist that has in it the contents of L1 followed by the conents of L2


cout << q3 << endl;




system("pause");
}

node.h
#include <iostream>


template<class C>
class Node
{
private:
C data;
Node<C> * next;
public:
Node();
Node<C> * getNext(void);
void setNext(Node<C> * newNext);
C getData();
void setData(C d);

};

template<class C>
Node<C>::Node(void)
{
next=NULL;
}
template<class C>
Node<C> * Node<C>::getNext(void)
{
return next;
}
template<class C>
void Node<C>::setNext(Node<C> * newNext)
{
next = newNext;
}
template<class C>
C Node<C>::getData(void)
{
return data;
}
template<class C>
void Node<C>::setData(C d)
{
data = d;
}

queue.h
#include "node.h"

template <class Q>
class Queue
{
private:
int length;
Node <Q> * list;

public:
Queue();//Regular Constructor
Queue(Queue<Q> * right);//Copy Constructor
void addItem(Q data);
void delItem(Q data);
void printList(void);
Q findAt(int pos);
int getLength(void);


};

template <class Q>
Queue<Q>::Queue(void)
{
list = NULL;
length = 0;
}

template<class Q>
Queue<Q>::Queue(Queue<Q> * right)
{
//this will refer to the object on the left of the =
//right will refer to the object on the right of the =
list = NULL;
length = 0;
for(int i=0;i<right->getLength();i++)
{
this->addItem(right->findAt(i));
}
}

template<class Q>
void Queue<Q>::addItem(Q data)
{
if(length==0)
{
//Create the first node oin the list
list = new Node<Q>();
list->setData(data);
length++;
}
else
{
//Append at the end of the list
Node<Q> * temp = list; //Make a copy of the memory address of the first node on the heap
while(temp->getNext() != NULL)
{
temp = temp->getNext();
}
Node<Q> * newNode = new Node<Q>(); //Construct node to add to list
//newNode->setData(data);
temp->setNext(newNode);
temp->getNext()->setData(data); // same as line above(newNode->setData(data);)
length++;
}
}

template<class Q>
void Queue<Q>::printList(void)
{
Node<Q> * temp = list;
while(temp != NULL)
{
cout << temp->getData() << endl;
temp = temp->getNext();
}
}

template<class Q>
int Queue<Q>::getLength(void)
{
return length;
}

template<class Q>
Q Queue<Q>::findAt(int pos)
{
if(pos < 0 || pos >=length)
{
return NULL;
}
else
{
Node<Q> * temp = list;
for(int i=0;i<pos;i++)
{
temp=temp->getNext();
}

return temp->getData();
}
}

template<class Q>
void Queue<Q>::delItem(Q data)
{
if(length==0)
{
return;
}
else if(length==1)
{
delete list;
length--;
}
else
{
Node<Q> * cur = list;
Node<Q> * prev;

if(cur->getData() == data)
{
Node<Q> * temp = cur->getNext();
delete cur;
list = temp;
length--;
}
else
{
prev = cur;
cur = cur->getNext();

while(cur != NULL)
{
if(cur->getData() == data)
{
Node<L> * temp = cur->getNext();
prev->setNext(temp); //Reroute the linked list around cur
delete cur;
length--;
return;
}
prev = cur;
cur = cur->getNext();
}


}
}
};

template<class Q>
std::ostream& operator<<(std::ostream& left, Queue<Q> * right)
{
if(right!=NULL)
{
for(int i=0;i<right->getLength();i++)
{
left << right->findAt(i)<<endl;
}
}
else
{
cout << "List not initialized" << endl;
}
return left;
}

template<class Q>
Queue<Q> *operator+(Queue<Q> left, Queue<Q> right)
{
Queue<Q> * newList = new Queue<Q>();

//Add the items in left to new list
for(int i=0;i<left.getLength();i++)
{
newList->addItem(left.findAt(i));
}
//Add the items in right to new list
for(int i=0;i<right.getLength();i++)
{
newList->addItem(right.findAt(i));
}
return newList;
}

[JayhawkZombie]

Use the code tags, please.

Queue<int> * q1 = new Queue<int>();
Queue<int> * q2 = new Queue<int>();
q1.push(5);
q1.push(6);
q2.push(9);
q2.push(1);
Queue<int> * q3 = (*q1) + (*q2);
cout << q3 << endl;

should produce the following output :

9
1
5
6


While trying to figure this out, I have some questions that would like to be answered.
1. What functions should be replaced by the push pop and peek functions ?
2. Does a Queue data structure use the node class or something else ?

Here is what I have so far...
Main.cpp
#include <iostream>
#include "Queue.h"

using namespace std;

void main(void)
{
	Queue<int> * q1 = new Queue<int>();	//Constructor triggered
	Queue<int> * q2 = new Queue<int>();	//Pointer, but no instance

	q1.push(5);
	q1.push(6);

	q2.push(9);
	q2.push(1);



	Queue<int> * q3 = (*q1) + (*q2); //create a new linkedlist that has in it the contents of L1 followed by the conents of L2


	cout << q3 << endl;




	system("pause");
}

node.h
#include <iostream>


template<class C>
class Node
{
private:
	C data;
	Node<C> * next;
public:
	Node();
	Node<C> * getNext(void);
	void setNext(Node<C> * newNext);
	C getData();
	void setData(C d);

};

template<class C>
Node<C>::Node(void)
{
	next = NULL;
}
template<class C>
Node<C> * Node<C>::getNext(void)
{
	return next;
}
template<class C>
void Node<C>::setNext(Node<C> * newNext)
{
	next = newNext;
}
template<class C>
C Node<C>::getData(void)
{
	return data;
}
template<class C>
void Node<C>::setData(C d)
{
	data = d;
}

queue.h
#include "node.h"

template <class Q>
class Queue
{
private:
	int length;
	Node <Q> * list;

public:
	Queue();//Regular Constructor
	Queue(Queue<Q> * right);//Copy Constructor
	void addItem(Q data);
	void delItem(Q data);
	void printList(void);
	Q findAt(int pos);
	int getLength(void);


};

template <class Q>
Queue<Q>::Queue(void)
{
	list = NULL;
	length = 0;
}

template<class Q>
Queue<Q>::Queue(Queue<Q> * right)
{
	//this will refer to the object on the left of the =
	//right will refer to the object on the right of the =
	list = NULL;
	length = 0;
	for (int i = 0; i<right->getLength(); i++)
	{
		this->addItem(right->findAt(i));
	}
}

template<class Q>
void Queue<Q>::addItem(Q data)
{
	if (length == 0)
	{
		//Create the first node oin the list
		list = new Node<Q>();
		list->setData(data);
		length++;
	}
	else
	{
		//Append at the end of the list
		Node<Q> * temp = list;	//Make a copy of the memory address of the first node on the heap
		while (temp->getNext() != NULL)
		{
			temp = temp->getNext();
		}
		Node<Q> * newNode = new Node<Q>(); //Construct node to add to list
										   //newNode->setData(data);
		temp->setNext(newNode);
		temp->getNext()->setData(data); // same as line above(newNode->setData(data);)
		length++;
	}
}

template<class Q>
void Queue<Q>::printList(void)
{
	Node<Q> * temp = list;
	while (temp != NULL)
	{
		cout << temp->getData() << endl;
		temp = temp->getNext();
	}
}

template<class Q>
int Queue<Q>::getLength(void)
{
	return length;
}

template<class Q>
Q Queue<Q>::findAt(int pos)
{
	if (pos < 0 || pos >= length)
	{
		return NULL;
	}
	else
	{
		Node<Q> * temp = list;
		for (int i = 0; i<pos; i++)
		{
			temp = temp->getNext();
		}

		return temp->getData();
	}
}

template<class Q>
void Queue<Q>::delItem(Q data)
{
	if (length == 0)
	{
		return;
	}
	else if (length == 1)
	{
		delete list;
		length--;
	}
	else
	{
		Node<Q> * cur = list;
		Node<Q> * prev;

		if (cur->getData() == data)
		{
			Node<Q> * temp = cur->getNext();
			delete cur;
			list = temp;
			length--;
		}
		else
		{
			prev = cur;
			cur = cur->getNext();

			while (cur != NULL)
			{
				if (cur->getData() == data)
				{
					Node<L> * temp = cur->getNext();
					prev->setNext(temp); //Reroute the linked list around cur
					delete cur;
					length--;
					return;
				}
				prev = cur;
				cur = cur->getNext();
			}


		}
	}
};

template<class Q>
std::ostream& operator<<(std::ostream& left, Queue<Q> * right)
{
	if (right != NULL)
	{
		for (int i = 0; i<right->getLength(); i++)
		{
			left << right->findAt(i) << endl;
		}
	}
	else
	{
		cout << "List not initialized" << endl;
	}
	return left;
}

template<class Q>
Queue<Q> *operator+(Queue<Q> left, Queue<Q> right)
{
	Queue<Q> * newList = new Queue<Q>();

	//Add the items in left to new list
	for (int i = 0; i<left.getLength(); i++)
	{
		newList->addItem(left.findAt(i));
	}
	//Add the items in right to new list
	for (int i = 0; i<right.getLength(); i++)
	{
		newList->addItem(right.findAt(i));
	}
	return newList;
}