How to determine if an element is in a stack?

[daviddoria]

With std::queue I've been using this:

std::queue<int>::iterator pos = std::find( q.begin(), q.end(), 5);

But when I try that with std::stack :

std::stack<int>::iterator pos = std::find( s.begin(), s.end(), 5);

I get

error: ‘iterator’ is not a member of ‘std::stack<int, std::deque<int, std::allocator<int> > >’

Anyone know how to do this?

Thanks,

Dave

[Aranarth]

You're meant to only access the top element of a stack, so std::stack provides no way to iterate over its elements.
But you could keep removing elements from the stack until you find the value you're looking for or the stack is empty, then push all elements back on the stack (possibly excluding the one you found, if any).

[Lerner]

The stack class doesn't have to have a front or a back, it just has to have a top, which may be the first or last (or some other) element of a list or vector (or some other container). So it doesn't make sense to have an iterator or a find() function that looks for front or back to allow you to loop through the container from begin() to end(). If you want random access in a container, to see what is in there without waiting to pop the top, then I suggest you use a different container.

[daviddoria]

You are only supposed to access the front and back of a queue too right? So why does queue get an iterator but stack does not?

[Lerner]

In queues you add at one end and remove from the other, so keeping track of both ends is handy/necessary. That can allow for iteration over the container, though it doesn't mean you should, or can, in all implementations of the container. Stacks add and remove from the same spot (usually an end), so there is no reason to keep track of anything but the one spot.

[AuburnMathTutor]

Just write your own code, using a stack like it's meant to be used.
You have your search stack. Empty it into a temp stack until you find what you want or hit the end.
Then take your temp stack contents and empty into the search stack. Voila! O(n) search algorithm for a stack.

You probably should do the same for a queue. It's kind of weird to be (mis)using data structures like this. You only need the search queue and a reference to the first thing.

Make a record of the first thing in the queue in the beginning.
Dequeue and enqueue every element until you get back to the very first thing initially in the queue.
If you happened to come across your search thing, excellent. Make a note of this.

O(n) search algorithm for a queue.

Note that O(n) is as good as you can hope to do on an unsorted collection of things anyway, and since stacks and queues aren't sorted according to the data but according to the order they are inserted, the find() thing can only do better by a constant factor. Don't worry about it.