insert implementation

chetmunk700
chetmunk700 used Ask the Experts™
on
Ok so ive tried to implement a insert functions for the value at the end of the queue but i keep getting a mismatch error. If someone could check what i have and relay and changes i need to make that would be great. Also i am trying to remove the front item from queue and im not sure how to go about doing this.



#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()                                                      
            {
                  last = NULL;
                  count = 0;
            }

            cQueue( const cQueue& q )                              
            {
                  copyQueue(q);
            }

            virtual ~cQueue()                                          
            {
                  deleteQueue();
            }

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

            size_t size() const                                    
            {
                  return count;
            }

            void insert( const T& v )                              // insert an value at the end of the queue
            {
                  if(last == NULL)
      {
            node<T>* last;
            //last = new node<T>*;
            last->next = last;
      }
      else if(v > last->data)
      {
            node<T>* node2 = new node<T>(v,last->next);
            last->next = node2;
            last = node2;
      }
      else
      {
            node<T>* temp;
            temp = last;
            while (v > temp->next->data)
            {
                  temp = temp->next;
            }
            node<T>* temp2 = new node<T> (v, temp->next);
            temp->next = temp2;
      }
            }

            T remove()                                                      // remove the front item from the queue
            {
                  
                  return last->data;
            }

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

            void print( ostream& os = cout ) const            // print the contents of the list
            {
                  node<T>* temp = last->next;
            while(temp != last)
            {
                  cout<< temp->data << " ";
                  temp = temp->next;
            }
            cout<< temp->data << endl;
            }

      private:
            void deleteQueue()                                          
            {
                  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 )                  
            {
                  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;                                          
            size_t            count;                                          
};

template <typename T>                                                
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;

      }
}
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®

Author

Commented:
same topic different question.
Please clarify.. What exactly is the question in the other Q and this Q. We haven't completed the other Q yet, so maybe we don't really understand the Q properly. And if I continue in this Q, I may end up repeating comments.
C++ 11 Fundamentals

This course will introduce you to C++ 11 and teach you about syntax fundamentals.

Author

Commented:
I can post my new code in the old question if that would be better? just need help getting those last couple functions to work right.
What does it take to close the previous question? If the questions are different, then this question is Ok to keep.

Author

Commented:
I closed the other question. This one mainly pertains to my code in the insert. I can't figure out what is wrong with it and if it is even correct.
Ok, the other question was about getting the program to compile. I see that you have given up on the recursion. (But if you have questions on infinite recursion after reviewing the course videos on recursion, then be sure to ask.)

In this Q you say that you are running, but are getting wrong answers. However, I tried to build your program, but it does not build. It appears that what you are running is not what you posted. To get on the same page with you, please post exactly what you are running. (Also, it helps if you post code using the Code link.

Author

Commented:
This should compile now
#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()                                                      
            {
                  last = NULL;
                  count = 0;
            }

            cQueue( const cQueue& q )                              
            {
                  copyQueue(q);
            }

            virtual ~cQueue()                                          
            {
                  deleteQueue();
            }

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

            size_t size() const                                    
            {
                  return count;
            }

            void insert( const T& v )                              // insert an value at the end of the queue
            {
                  if(last == NULL)
      {
            node<T>* last;
            //last = new node<T>*;
            last->next = last;
      }
      else if(v > last->data)
      {
            node<T>* node2 = new node<T>(v,last->next);
            last->next = node2;
            last = node2;
      }
      else
      {
            node<T>* temp;
            temp = last;
            while (v > temp->next->data)
            {
                  temp = temp->next;
            }
            node<T>* temp2 = new node<T> (v, temp->next);
            temp->next = temp2;
      }
            }

            T remove()                                                      // remove the front item from the queue
            {
                  
                  return last->data;
            }

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

            void print( ostream& os = cout ) const            // print the contents of the list
            {
                  node<T>* temp = last->next;
            while(temp != last)
            {
                  cout<< temp->data << " ";
                  temp = temp->next;
            }
            cout<< temp->data << endl;
            }

      private:
            void deleteQueue()                                          
            {
                  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 )                  
            {
                  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;                                          
            size_t            count;                                          
};

template <typename T>                                                
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

The first time you call insert, the queue is empty; last is NULL, so you execute this code:
        if(last == NULL)
        {  
            node<T>* last;   // last not same as class member last; suggest name change
            //last = new node<T>*;  
            last->next = last;   // confusing - which last is local vs class member
        } 

Open in new window

The local last is not initialized. The class member last is NULL. So, whatever your intention was, neither will work. To make your intention clearer, do not use same name for local variable as for class member.

If the queue is empty, exactly what do you want to happen?

Your last class member is often called a tail in a linked list; and typically in a linked list, you have a head pointer. Do you think adding a head class member will be useful?

Author

Commented:
Maybe im going about this the wrong way. At this point im not sure how to write this correctly to be able to get this working. All i was trying to do was get this to insert a value at the end of the queue.
>> Maybe im going about this the wrong way.
There are many ways to implement a queue, and there are different kinds of queues. But you can continue with your current way. (To avoid going down the wrong path, in general, you should write down your requirements in bullets, and want to work out a schematic of the class operations and attributes in a design to make sure that you meet your requirements and performance expectations.)

>> All i was trying to do was get this to insert a value at the end of the queue.
Right, I see that. But how do you do that if the queue is empty?
In your requirements, do you have a need to access both ends of the linked list that you are creating? If so, how do you plan on doing this with just last? It is doable, provided that you have a clear definition of what last means. Requirements and definitions are for you to describe; then we can help with the design and implementation.

Author

Commented:
I see..So if the queue would be empty i would need to print that its empty untill the next call to insert an element?

Author

Commented:
Yes i do need to access the front and last ends of the linked list.
>> if the queue would be empty i would need to print that its empty
If we were talking about the print function, then that seems reasonable.

>> All i was trying to do was get this to insert a value at the end of the queue.
Right, I see that. But how do you insert a value at the end of the queue if the queue is empty?
>> i do need to access the front and last ends of the linked list.
You could define a head and tail pointers to quickly access both ends, and insert would update one or the other (or both) according to the sort results.
>> >> All i was trying to do was get this to insert a value at the end of the queue.
But your code is not trying to insert a value at the end of the queue. It is trying to insert based on a sort ordering.

Author

Commented:
Could you explain this in code? Im assuming doing this i cant use what i had already with last. Sorry for all the questions im new with c++
I don't know exactly what your requirements are with this queue. But, per EE policy, I am not permitted to write code for academic type problems (even is self-study).

Let's do this. After each of these opertions, show what the queue should look like. (Don't just show the final result - show how the queue grows with each insert. This will at least give us an idea of what the insert requirements are.

        q.insert(10);  
        q.insert(20);  
        q.insert(15);
        q.insert(18);
        q.insert(17);
        q.insert(5);
        q.insert(25);
One more thing. What do you do if you repeat an insert value?
e.g.
       q.insert(15);
       q.insert(18);
       q.insert(15);
 
When your queue is empty, and you do your first insert, then you just put the node into the queue so that there is now just one entry. Can you do that?

Author

Commented:
Ok ive updated my code and now i am getting a exception in my print statement
#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
		{
			 if (! last)
			{ 
				last = new node<T>(v, NULL);
			}
			 else 
				 {
					 node<T>* first;
					first = last->next;
					 node<T>* temp;
					temp = new node<T>(v, first);
					last = last->next;
				 }
		}

		T remove()									// remove the front item from the queue
		{
			node<T>* first;
			first = last->next;
			delete first;
			return last->data;
		}

		const T& front() const						// return a reference to the front item
		{
			return last->data;
		}

		void print( ostream& os = cout ) const		// print the contents of the list
		{
		node<T>* temp = last->next;
		while(temp != last->next)
		{
			cout<< temp->data << " ";
			temp = temp->next;
		}
		cout<< temp->data << endl;
		}

	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

I see that you are no longer inserting in sorted order. Your requirements are a moving target, and as such, difficult to work with. After you write down your requirements, you'll have a chance to design the program properly. Impossible to know whether the code is correct until we know what constitutes a valid test with a clear pass/fail criteria.

If you post what the queue will look like with the insert statements in http:#35766324 and http:#35766334, then at least we'll know what constitutes a passing test.

The good news is that you inserted the first item without a problem this time.

I wouldn't try printing anything until you are able to insert a 2nd item. The problem is with the insert. To fix insert and debug it, the easiest way is to use a GUI debugger.

Author

Commented:
I thought it might be something with the insert. Not sure how to debug this to fix my problem though.
Without requirements, it is not possible to debug.

If you post what the queue will look like with the insert statements in http:#35766324 and http:#35766334, then at least we'll know what constitutes a passing test.

Author

Commented:
Everything listed in Main should be there so              
              q. insert(10);
            q.insert(20);
            q.insert(30); . That is code given to me for the assignment.
What will the queue look like after this:
             q. insert(10);
            q.insert(20);
?
Post the link list of what you want after these two insert operations. After you post this, see if you can link up the queue so that in the GUI debugger, you can actually see that you have done this correctly. What OS and GUI Debugger are you currently using?

And then, what will the queue look like after this:
            q.insert(30);
Post the link list of what you want after this third insert operation. Back in an hour.
I'll be back tomorrow. Here's what I recommend. Since you already got q. insert(10) to insert 10 into the queue, try to get q. insert(20) to work. In order to do this without print statements, you need a GUI debugger. As you step through the insert routine when inserting 20, make sure that you understand each step, and are able to trace the linked list through the debugger.
To  understand how to manipulate pointers in linked lists, please review this Stanford University course video. The discussion on the blackboard is probably more important to understand than the actual code since it goes into the foundation of linked list design.
     http://www.academicearth.org/lectures/coding-with-linked-list

This lecture on linked list actually begins near the end of the previous lecture (starts at 29:45):
     http://www.academicearth.org/lectures/pointer-movie

You seem to have a good grasp of pointers, so you may wish to skip the first portion of this previous lecture.
Do you now understand how to get the q.insert(20) to work? Or, would you like to discuss the problem further? To analyze what happens, we just need to ask what happens starting at line 63 in http:#35766636:
node<T>* first; 
first = last->next;  // 10 is in the queue already. What value is last and last->next ?
node<T>* temp; 
temp = new node<T>(v, first);  // create a new node; but what do you do with it?
last = last->next;

Open in new window

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial