PDA

View Full Version : c++ queue template program




bravens52
Apr 20, 2011, 07:10 PM
hello im working on a program that is quite difficult for me and i need some help going in the right direction.. ill post the directions, the driver test program..what i have so far.. thanks!! ... feel free to revise ..


#ifndef QUEUE_H
#define QUEUE_H

#include <iostream>
#include <stdexcept>

using std::ostream;
using std::out_of_range;

template <class T>
struct QNode
{
QNode(const T & X)
T storeitem;
T * next;
};

QNode::QNode(const T & x)
{
x = QNode;
next = '\0';

}

template <class T>
class Queue
{
private:
T qfront;
T qrear;

public:
Queue(); //default constructor
~Queue(); // destructor
Queue(const Queue& s); //copy constructor
Queue& operator=(const Queue& rightOp);
friend ostream& operator<< <>(ostream&, const Queue<T>&);
void clear();
int size();
bool empty();
bool front();
bool back();
void push();
void pop();
};

template <class T>
Queue<T>::Queue()
{
qfront = '\0';
qrear = '\0';
}

template <class T>
Queue<T>::~Queue()
{
clear();
}

template <class T>
Queue<T>::Queue(const Queue& s)
{
qront = '\0';
qrear = '\0\';
}



subsonix
Apr 20, 2011, 07:30 PM
So is this a queue data structure? What exactly are you having problems with, and where is the implementation?

It's probably easier to implement one function at the time and test it, and leave out stuff like operator overloading until you have the basic functionality down. i.e create a queue, add an item, remove and so on.

bravens52
Apr 20, 2011, 07:46 PM
So is this a queue data structure? What exactly are you having problems with, and where is the implementation?

It's probably easier to implement one function at the time and test it, and leave out stuff like operator overloading until you have the basic functionality down. i.e create a queue, add an item, remove and so on.

yes it is a a queue data structure.. im having problems implementing the functions..those are my attempts above but i dont know if i am doing they right based off the directions i attached below

subsonix
Apr 20, 2011, 07:51 PM
What you have posted looks like a header file, i.e no implementation just a description of the interfaces. You also have include guards in place which indicates that. But you should use code tags and indent the code then it's easier to read it. I'm not going to read you assignment directions.

bravens52
Apr 20, 2011, 08:17 PM
What you have posted looks like a header file, i.e no implementation just a description of the interfaces. You also have include guards in place which indicates that. But you should use code tags and indent the code then it's easier to read it. I'm not going to read you assignment directions.

yeah this is the headerfile... all of the implementations and declarations are going into the header file in this assignment...

This is where im stuck

class Queue
Data members
This class should have two data members, both pointers to QNodes. The pointer qFront will point to the front node in the queue (or be NULL if the queue is empty); the pointer qRear will point to the rear node in the queue (or be NULL if the queue is empty).
Methods and associated functions
Constructor
The class should have a default constructor that takes no arguments. The constructor should set both pointer data members to NULL.
Destructor
The class should have a destructor. The destructor can simply call the clear() method described below.
Copy constructor
The class should also have a proper copy constructor. If you choose to make a copy of the linked list by using the push method, make sure you set both the front and rear pointers for the new queue to NULL before you attempt to insert any nodes into it.
operator=
The assignment operator should be properly overloaded.
operator<<
The output operator should be overloaded so that an entire Queue can be sent to the standard output. As usual, this function will need to be a friend rather than a method. Declaring a template function to be a friend of a template class requires some special syntax - see the Implementation Hints below.
clear()
This method takes no arguments and returns nothing. It should properly set the queue back to the empty state. That means deleting all of the nodes in the queue and setting the front and rear pointers back to NULL.
size()
This method takes no arguments and returns an integer. It should return the current size of the queue; i.e., the number of data items currently stored in the queue. Since this is not stored as a data member of the queue class, you will have to traverse the linked list and count the nodes.
empty()
Returns true if there are no data items currently stored in the queue; otherwise returns false.
front()
This method takes no arguments and returns the template parameter type. If the queue is empty, this method should throw an out_of_range exception. Otherwise, it should return the data stored in the front node of the queue.
back()
This method takes no arguments and returns the template parameter type. If the queue is empty, this method should throw an out_of_range exception. Otherwise, it should return the data stored in the rear node of the queue.
push()
This method takes a reference to a constant item of the template parameter type as its argument (the item to insert into the queue). It returns nothing. The method should insert the item at the rear of the queue.
pop()
This method takes no arguments and returns nothing. If the queue is empty, this method should throw an out_of_range exception. Otherwise, it should remove the item at the front of the queue.
If you like, you may write private methods for the Queue class in addition to the methods described above. For example, you may want to write a copyList() method that can be called by both the copy constructor and overloaded assignment operator.

subsonix
Apr 20, 2011, 08:40 PM
I think you will have to make a bigger effort. You have the two data members, but they are not pointers, and not of type QNode. Your default constructor sets these to '\0' (not NULL however) so that part can be checked of the list.

What you must do, is to strip down the requirement to the bare minimum and get that to work first. i.e forget about operator overloading, copy constructors and perhaps even templates to begin with.

Edit:

Examples of the essential functionality you should start with.
push()
pop()
back()
front()
empty()

The nodes suggest that the implementation is going to be based around a linked list internally. Luckily it's easier to do this in C++ since your nodes will be visible inside your object, unlike in C. Have you done this before? To add an item, create a new node, link it with the base node, or previous node, store the value in storeitem.

bravens52
Apr 20, 2011, 09:54 PM
I think you will have to make a bigger effort. You have the two data members, but they are not pointers, and not of type QNode. Your default constructor sets these to '\0' (not NULL however) so that part can be checked of the list.

What you must do, is to strip down the requirement to the bare minimum and get that to work first. i.e forget about operator overloading, copy constructors and perhaps even templates to begin with.

Edit:

Examples of the essential functionality you should start with.
push()
pop()
back()
front()
empty()

The nodes suggest that the implementation is going to be based around a linked list internally. Luckily it's easier to do this in C++ since your nodes will be visible inside your object, unlike in C. Have you done this before? To add an item, create a new node, link it with the base node, or previous node, store the value in storeitem.

okay im going through those methods and i notice alot of them say if QUEUE for example #

size()

This method takes no arguments and returns an integer. It should return the current size of the queue; i.e., the number of data items currently stored in the queue. Since this is not stored as a data member of the queue class, you will have to traverse the linked list and count the nodes.

how would i go about writing this statement out..?

bravens52
Apr 20, 2011, 09:58 PM
also for example
#

clear()

This method takes no arguments and returns nothing. It should properly set the queue back to the empty state. That means deleting all of the nodes in the queue and setting the front and rear pointers back to NULL.

i wrote


template <class T>
void Queue<T>::clear()
{
data=0;
qfront='\0';
qrear='\0';
}


is this correct? .. im just not understanding what QUEUE means or is referring to?

bravens52
Apr 20, 2011, 10:06 PM
this is my current progress


#ifndef QUEUE_H
#define QUEUE_H

#include <iostream>
#include <stdexcept>

using std::ostream;
using std::out_of_range;

template <class T>
struct QNode
{
QNode(const T & X)
T data;
QNode *next;
};

QNode::QNode(const T & x)
{
x = QNode;
next = NULL;

}

template <class T>
class Queue
{
private:
QNode *qfront;
QNode *qrear;

public:
Queue(); //default constructor
~Queue(); // destructor
Queue(const Queue& s); //copy constructor
Queue& operator=(const Queue& rightOp);
friend ostream& operator<< <>(ostream&, const Queue<T>&);
void clear();
int size();
bool empty();
bool front();
bool back();
void push();
void pop();
};

template <class T>
Queue<T>::Queue()
{
qfront = '\0';
qrear = '\0';
}

template <class T>
Queue<T>::~Queue()
{
Queue.clear();
}

template <class T>
Queue<T>::Queue(const Queue& s)
{
qront = '\0';
qrear = '\0';
}

template <class T>
Queue& Queue<T>::operator=(const Queue& rightOp)
{
if(this == &rightOp)
{
return *this;
}
}

template <class T>
ostream & operator<<(ostream & leftOp, const Queue<T> & rightOp)
{
}


template <class T>
void Queue<T>::clear()
{
data=0;
qfront='\0';
qrear='\0';
}

template <class T>
int Queue<T>::size()
{
return data;
}

template <class T>
bool Queue<T>::empty()
{
}

subsonix
Apr 20, 2011, 10:11 PM
okay im going through those methods and i notice alot of them say if QUEUE for example #

size()

This method takes no arguments and returns an integer. It should return the current size of the queue; i.e., the number of data items currently stored in the queue. Since this is not stored as a data member of the queue class, you will have to traverse the linked list and count the nodes.

how would i go about writing this statement out..?

Create a private variable of say size_t type, then as soon as you add a new node do a: size++;
And similarly when you remove a node, size--; Edit: remember that in your constructor you will need to initialize that size variable to 0.

That way you will keep track of your current size without having to traverse the list. Then in your size() function simply return size.

also for example
#

clear()

This method takes no arguments and returns nothing. It should properly set the queue back to the empty state. That means deleting all of the nodes in the queue and setting the front and rear pointers back to NULL.

i wrote


template <class T>
void Queue<T>::clear()
{
data=0;
qfront='\0';
qrear='\0';
}


is this correct? .. im just not understanding what QUEUE means or is referring to?

You will need to traverse all your nodes and delete them, or you will have a memory leak. Given that when you add a new node you will need to do something like this:


node *n = new node;
n->data = indata;
// further linking here with your previous nodes.


But when you have deleted all your nodes you should set the front and rear pointers to NULL. Basically you could implement your pop() function first. Then in your clear function you call pop() until size == 0.

jiminaus
Apr 20, 2011, 10:57 PM
QNode::QNode(const T & x)
{
x = QNode;
next = '\0';

}


I'm struggle to get what the actually effect of this code would be. I know it's meant to be a constructor for QNode, but it's not doing that. The first statement overwrites the passed in x with a default constructed QNode. It would globber x, except x is const and T is unlikely to be QNode.