Registered: 14 years ago
I don't seem to get this question. The question is that you must write a function to remove all occurences of an item in a queue without changin the order of the other elements in the queue.
template < class Type >
void removeX ( queueType< Type > & Q, const Type &x)
Once again, as Rob said, maybe I am too concerned about the implementation, but I don't want to loose marks due to incorrect interpretation of a question. So once again, my question is ... should we be using the array or linked list based queue here?
Personally I feel that this implementation is much easier with the linked list based queue but the provided header shows queueType ... which according to the textbook is the array based queue, or does the header only show that that a queue must be provided as a paramater, whether it is array based or linked list based ?
Registered: 14 years ago
Stop worrying about how the queue is implemented and worry about how you're best going to use it.
My understanding of the problem is that if you have a queue that has the elements:
and you want to remove all of the D's then the requirements state that all the other elements should remain in the same order that they were in originally.
Now the hardest decision you need to take is whether to use the textbook's version of the queue or to use the STL version. This is not a difficult decision because the STL has been designed to be very efficient. If you don't need any other functionality, always go for the STL version.
BUT, since the question uses the queueType class, I suppose we must use that instead.
Now, you have the following methods available:
addQueue(const Type &newElement);
You seem pre-occupied with how the data are stored so I ask you this, does it make any difference whether its an array-based queue or a linked-list queue? Will it make any more difference if the data were stored in some other manner?
If you answered, "yes" to any of these questions, write versions of your programme for each type of queue and you'll see that your algorithm won't change at all.
Take this analogy:
If I go to a fishmonger and say that I have a fancy dinner party planned at the end of the month and I need 1000 top quality New Zealand mussels. Will I really care whether they are flown in, shipped on a boat or grown locally here by a mussel farmer?
With a queue, it's the same. If it can tell you what's at the front and back, adds elements to the back and takes them off at the front, can tell you the queue size, and can initialise and destroy itself, I don't really care if the data are stored in an array, linked-list, six million internal variables, etc. As long as it does the job its supposed to. That is the whole point of object-orientated programming.