Link to home
Start Free TrialLog in
Avatar of chetmunk700
chetmunk700

asked on

Help on insert function.

Ok so ive tried to implement a insert fuction using nodes but i am having trouble getting it to compile. I have also tried to implement a remove() fuction using node T and just curious if that is how im supposed to do that.
#include <iostream>
#include <stdexcept>

using namespace std;

template <typename T>
class node
{
	private:
		node( const T& x, node* p = NULL )
		{
			data 	= x;
			next	= p;
		}
		T		data;
		node*	next;
	template<typename S> friend class cQueue;
};

template <typename T>
class cQueue
{
	public:
		cQueue()									// default constructor
		{
			last = NULL;
			count = 0;
		}

		cQueue( const cQueue& q )					// copy constructor
		{
			copyQueue(q);
		}

		virtual ~cQueue()							// queue destructor
		{
			deleteQueue();
		}

		cQueue& operator= ( const cQueue& q )		// overloaded assignment operator
		{
			if ( this != &q )
			{
				deleteQueue();
				copyQueue( q );
			}
			return *this;
		}

		size_t size() const							// return the size of the queue
		{
			return count;
		}

		void insert( const T& v )					// insert an value at the end of the queue
		{
			node<T>* last = tmp;
					
			insert( tmp->data );
					tmp = tmp->next;

		}

		T remove()									// remove the front item from the queue
		{
			delete node<T>* front;
		}

		const T& front() const						// return a reference to the front item
		{
			
		}

		void print( ostream& os = cout ) const		// print the contents of the list
		{
			
		}

	private:
		void deleteQueue()							// delete nodes in "this" queue
		{
			if ( last != NULL )
			{
				node<T>* tmp = last->next;
				while ( tmp != last )
				{
					node<T>* doomed = tmp;
					tmp = tmp->next;
					delete doomed;
				} 
				last = NULL;
				count = 0;
				delete tmp;
			}
		}

		void copyQueue( const cQueue& q )			// copy q queue into "this" queue ("this" queue must be empty)
		{
			last = NULL;
			count = 0;

			if ( q.last != NULL )
			{
				node<T>* tmp = q.last->next;
				for ( size_t i = 0; i < q.count; i++ )
				{
					insert( tmp->data );
					tmp = tmp->next;
				}
			}
			count = q.count;
		}

		node<T>*	last;							// a pointer to the last node in the list
		size_t		count;							// queue length
};

template <typename T>								// overloaded ostream operator<<
ostream& operator<< ( ostream& os, const cQueue<T>& q )
{
	q.print( os );
	return os;
}


template <typename T>
void passByValue( cQueue<T> q )
{
	q.insert( 40 );
	cout << "queue inside passByValue: " << q << endl;
}

int main()
{

	{
		cQueue<int> q;

		q.insert(10);
		q.insert(20);
		q.insert(30);

		cout << "initial queue: " << q << endl;

		passByValue( q );

		cout << "queue after call to passByValue: " << q << endl;

		cout << "front item: " << q.front() << endl;

		q.remove();

		cout << "front item removed: " << q << endl;

	}
}

Open in new window

Avatar of Kent Olsen
Kent Olsen
Flag of United States of America image

Hi Chet,

It looks to me like the insert method is recursively calling itself.  Probably not what you want to do....


Kent
Avatar of chetmunk700
chetmunk700

ASKER

So can i use last to get to the last item in the queue?

node<T>* last;                  
                  insert( last->data );
                              last = last->next;
Line 57: node<T>* last = tmp;
last is a class member. tmp is undefined. Did you mean:
     node<T>* tmp = last;

Line 64:
T remove()                                                      // remove the front item from the queue  
{  
      delete node<T>* front;  
}  

const T& front() const                                // return a reference to the front item  
{  
}

Open in new window

The following does not try to do functionally correct things. However, it does show you how to get your program to compile without errors:
    T remove()                                                                      // remove the front item from the queue  
    {  
        delete /*node<T>**/ front(); 
        return last->data;
    }  

    const node<T>* front() const                                          // return a reference to the front item  
    {  
        return last;
    }

Open in new window

yes i did not notice that. so instead i could say ...?

node<T>* tmp = last;            
                  insert( tmp->data );
                              tmp = tmp->next;

Whenever you use recursion, you must have a way to stop infinite recursion.
I built this on VS 2010, and after adding the code to get it to compile, there is a warning:
warning C4717: 'cQueue<int>::insert' : recursive on all control paths, function will cause runtime stack overflow

But at least we got this answered: "but i am having trouble getting it to compile"
Could you explain infinite recursion. not quite sure how that works. and i am also using VS 10 and for my T remove() im getting a error saying cannot delete objects that are not pointers      
Infinite is just that.  I goes forever.

Whenever a function calls itself (recursion) the code needs to have a way to determine when to stop calling itself.

In this case, checking for a NULL pointer is a good start.  Though if you want to delete the last item in the list, you'll need to know the address of the next-to-last item.


Kent
recursion is explained in these course videos:
   http://www.academicearth.org/courses/programming-abstractions

More specifically, recursion is introduced at 41:00
    http://www.academicearth.org/lectures/specific-plot-functions

Lecture 9 - Thinking Recursively
     http://www.academicearth.org/lectures/thinking-recursively

Lecture 8 also discusses recursion.
ASKER CERTIFIED SOLUTION
Avatar of phoffric
phoffric

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial