If you have a queue and are only permitted to do enqueues and dequeues on it, then the only way you can find an arbitrary value in the queue is to perform as many dequeues are necessary to find that particular value. If you don't know where in the queue that value is, then in the worst case you might have to inspect all n elements of the queue, which takes Θ(n) time. So in that sense, any solution we come up with has to always do at least Θ(n) work in the worst case.
One way that you can go about doing this is to imagine treating the queue as if it's a ring of elements with a cursor in some position indicating the front. If you dequeue an element and then immediately re-enqueue it, it's as if you've moved the cursor one spot clockwise (or counterclockwise - this is just a metaphor, after all). So you could consider solving this problem by moving the cursor around the queue until you find the element to delete, then dequeue it without re-enqueuing it, then moving the cursor around to back where you started. Here's one way to do this:
/* Store the number of elements in the queue, since it will change as
* the loop runs. We want to visit each element exactly once.
*/
int numElems = queue.size();
for (int i = 0; i < numElems; i++) {
ValueType elem = queue.dequeueMin();
/* Remove the element if it matches the thing to get rid of, or,
* equivalently, preserve the element if it isn't.
*/
if (elem != theThingToRemove) {
queue.enqueue(elem);
}
}
This algorithm always does Θ(n) work - the loop visits each element exactly once and does O(1) total work - and O(1) total queue operations - per element.
Fun fact: this metaphor for a queue is exactly the idea behind a circular buffer, which is often used to implement fixed-sized queues.
