How to Search a item from a stack?

Question

When i'm reading some books, I saw, Time complexity of searching an item from the stack is O(n).But i'm confused with, how can i search a middle value from a stack since it is a LIFO.

Answer 1

As very astutely described Duekling / Duncan , may be you would want to create a a stack with a count, and then breaking into two. Let s1 and s2 point to two stacks, so when you push two items in s1, the first node becomes the top of s2 , and the last entered node becomes top of s1. then again two more items are added with the count becoming 4 , push the item3 on s2 and item 4 remains on s1 ..

Answer 2

A stack is usually implemented as an array or a linked-list, you can iterate though either of those.

If you have a pure stack API that doesn't provide you with an iterator:

You have to pop elements on to a different stack until you find the element, then push them back.

After this we'll have the stack back to the way it was.

Answer 3

Because O(n) is linear complexity, so you'd have to pop every element until you found your match. Therefore, the time to search grows in line with the number of elements.