Avatar of chetmunk700
chetmunk700

asked on 

insert implementation

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;

      }
}
C++

Avatar of undefined
Last Comment
phoffric
Avatar of phoffric
phoffric

Avatar of chetmunk700
chetmunk700

ASKER

same topic different question.
Avatar of phoffric
phoffric

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.
Avatar of chetmunk700
chetmunk700

ASKER

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.
Avatar of phoffric
phoffric

What does it take to close the previous question? If the questions are different, then this question is Ok to keep.
Avatar of chetmunk700
chetmunk700

ASKER

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.
Avatar of phoffric
phoffric

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.

Avatar of chetmunk700
chetmunk700

ASKER

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

Avatar of phoffric
phoffric

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?
Avatar of chetmunk700
chetmunk700

ASKER

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.
Avatar of phoffric
phoffric

>> 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?
Avatar of phoffric
phoffric

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.
Avatar of chetmunk700
chetmunk700

ASKER

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?
Avatar of chetmunk700
chetmunk700

ASKER

Yes i do need to access the front and last ends of the linked list.
Avatar of phoffric
phoffric

>> 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?
Avatar of phoffric
phoffric

>> 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.
Avatar of phoffric
phoffric

>> >> 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.
Avatar of chetmunk700
chetmunk700

ASKER

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++
Avatar of phoffric
phoffric

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);
Avatar of phoffric
phoffric

One more thing. What do you do if you repeat an insert value?
e.g.
       q.insert(15);
       q.insert(18);
       q.insert(15);
 
Avatar of phoffric
phoffric

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?
Avatar of chetmunk700
chetmunk700

ASKER

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

Avatar of phoffric
phoffric

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.
Avatar of chetmunk700
chetmunk700

ASKER

I thought it might be something with the insert. Not sure how to debug this to fix my problem though.
Avatar of phoffric
phoffric

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.
Avatar of chetmunk700
chetmunk700

ASKER

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.
Avatar of phoffric
phoffric

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.
Avatar of phoffric
phoffric

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.
Avatar of phoffric
phoffric

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.
ASKER CERTIFIED SOLUTION
Avatar of phoffric
phoffric

Blurred text
THIS SOLUTION IS ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.
See Pricing Options
Start Free Trial
C++
C++

C++ is an intermediate-level general-purpose programming language, not to be confused with C or C#. It was developed as a set of extensions to the C programming language to improve type-safety and add support for automatic resource management, object-orientation, generic programming, and exception handling, among other features.

58K
Questions
--
Followers
--
Top Experts
Get a personalized solution from industry experts
Ask the experts
Read over 600 more reviews

TRUSTED BY

IBM logoIntel logoMicrosoft logoUbisoft logoSAP logo
Qualcomm logoCitrix Systems logoWorkday logoErnst & Young logo
High performer badgeUsers love us badge
LinkedIn logoFacebook logoX logoInstagram logoTikTok logoYouTube logo