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;
}
}
#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;
}
}
ASKER
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.
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.
What does it take to close the previous question? If the questions are different, then this question is Ok to keep.
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.
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.
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.
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;
}
}
The first time you call insert, the queue is empty; last is NULL, so you execute this code:
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?
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
} 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?
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.
>> 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?
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.
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?
ASKER
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?
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.
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.
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.
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++
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);
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);
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?
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;
}
}
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.
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.
ASKER
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.
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.
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.
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.
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.
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
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
https://www.experts-exchange.com/questions/27039390/Help-on-insert-function.html
and
https://www.experts-exchange.com/questions/27034354/Insert-Remove-and-Print-functions.html