c - 从堆栈中搜索

Question

我正在实现一个堆栈，虽然实现基本操作 push 和 pop 很简单，但我想知道如何实现更高效的搜索。底层结构是一个链表

Answer 1

在其基本形式中，堆栈只允许较慢的线性搜索。即，如果堆栈有 n 个元素，则需要搜索所有 n 个(平均 1/2 n 个)才能找到匹配项。如果您的堆栈相对较小，则这种线性(一个接一个)搜索可能无关紧要。

但是，如果您有一个更大的集合，您可以将两个数据结构组合在一起以提高搜索效率:例如，除了堆栈之外，您还可以有一个哈希表:每次你把东西压入堆栈时，你也可以将它添加到哈希表中。相反，当您将它从堆栈中移除时，您可以将它从表中移除。哈希表允许相对快速的查找，即使是非常大的数据集——因此，您的搜索可能会非常快。

我提出的解决方案的一个问题是如何正确处理重复项:堆栈可以保存重复项，但哈希表通常不能。因此，您可能需要在哈希表中实现一些简单的引用计数:每次弹出时，递减哈希表中的计数——当计数降为零时，您可以将其从哈希中删除。

另一种类似的可能性是使用“multimap”——这类似于哈希表，但可以更轻松地处理重复项。