Assignment 2 question 4: Queues

For question 4 (a), to find item n in a queue, how do you traverse to get through the queue? I cannot seem to find an example in the textbook (unless I'm missing it).

Or do you pop the front element if it is not n, and move through the queue by popping the front each time until you find n (or until front is NULL)?

The same would apply for (b), because you would need to traverse the queue to find the last instance of x.

Could someone please shed some light?

I am also a little stuck with this question. I think it is a bit silly as the whole point of a queue is an ordered list type, so it should not be required to access items out of sequence.

I used a loop to pop as many items as required from the list, and then used front() function to return the required item.
Although this works it is not elegant as the queue is destroyed, so I don't think it's right. It is possible to build a new queue as described below.

For the second part:
One way to do it will be to pop items from the queue, do the operation (compare and store position of last occurence in queue) and then immediately push items into other queue.
Then you can pop items from the new queue and push back into into the old queue, but replace with new value when the correct position is reached.

Hope this helps

Francois

Thanks Francois, I'll give it a go.