Searching from a stack

Question

I am implementing a stack and while it was a no-brainer to implement the basic operations push and pop, I am wondering how to implement somewhat efficient searching. The underlying structure is a linked list

Answer 1

In its basic form, a stack would only allow slowish linear searches. I.e., if the stack has n elements, you would need to search through all n (1/2 n, on average) to find a match. If your stack is relatively small, this linear (one by one) search might not matter that much.

However, if you have a much larger set, you might be able to combine two data structures together to make searches more efficient: For example, you could have a hash table in addition to the stack: Each time you push something on the stack, you could also add it to the hash table. Conversely, when you remove it from the stack, you could remove it from the table. Hash tables allow relatively fast lookups, even with very large data sets-- therefore, your searches could be quite fast.

One problem with my proposed solution is how to properly handle duplicate items: Stacks can hold dups, but hash tables typically don't. Therefore, you might need to implement some simple reference counting in the hash table: Each time you pop, decrement the count in the hash table-- when the count drops to zero, you can remove it from the hash.

Another similar possibility is to use a "multimap"-- this is similar to a hash table, but would allow duplicates to be handled more easily.

Answer 2

You didn't mention if you implemented a persistent stack (push and pop returning new stacks while the argument stack continues to exist) or a mutable stack (the stack passed to push and pop is modified in-place).

In any case, the deepest values are those that change the least often, so a strategy to speed up searching would be to cache the results of previous searches on the deepest 2, 4, 8, ... elements of the stacks you handle. If you implemented a mutable stack, invalidate the cache as suitable (invalidate the cache entries for the first 2^n elements when the stack depth has come below 2^n).

Answer 3

A stack is not designed to be 'searchable'. Of course, you can easily implement searching on the underlying linked list and expose it to the user - but it's no stack anymore then.

Linear-time search in linked list could look like this:

listentry* first;

for(first = head; (first=first->next);) {
  if (first->val == value_to_search) {
     // have a match
     return 1;
  }
}
return 0;

The 'legal' way to search a stack is 'pop() until the value you're searching for is on the top of the stack'. Please don't do this if you need the stack afterwards.

Answer 4

If you need to examine any item in a stack other than the item at the top, you probably shouldn't be using a stack to contain your items. Rethink the choice of your data structure.